Re: [Help-glpk] glpsol (MIP) "-w" output specification, "-y" operation

[Michael Hennebry]

On Mon, 4 May 2009, Johannes Waldmann wrote:

> > To get tighter relaxations, use the smallest big M's that will work.
>
> This effectively limits the range of values for the unknowns.

No, it limits the ranges of the big M's:

Z = max(X, Y)

X in Lx..Ux
Y in Ly..Uy
b in 0..1

Z >= X
Z >= Y
Z <= X + (Uy-Lx)*b
Z <= Y + (Ux-Ly)*(1-b)

> If that range is very small, then I can directly use a binary encoding
> for numbers, and use a SAT solver - in fact that's what I've been doing
> for some time. I was hoping that MIP gives another feasible approach.

If the numbers are really small:

Z = SUM Bz[j, k]*max(j, k)
    j,k

X = SUM Bz[j, k]*j
    j,k

Y = SUM Bz[j, k]*k
    j,k

I think that this is *linearly* equivalent to the preceeding,
but it has a lot more binaries, so I can't recommend it.
Rather obviously (X, Y, Z) is constrained
to the convex hull of its feasible values.

> But as they say, "there's no free lunch".

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."