Re: [Help-glpk] shiftcover.mod - generate different solutions

[Michael Hennebry]

On Mon, 21 Feb 2011, glpk xypron wrote:

> Hello Michael,
>
> > If all variables and constraint coefficients are integer,
> > a single constraint on the nonbasic variables will exclude the
> > current solution without excluding any other integer solutions.
> How do you define "nonbasic variable" in a MIP solution?
>
> > Add the constraint xj = xj + yj - (Hj+1-Lj)mj .
> I suppose mj has to be binary. yj and mj also introduce

Yes.  yj in 0..Hj-Lj and mj in 0..1 .

> "duplicate continuous representations".

Yes.  It's a matter of degree.

> Does each excluded solution require a new set of mj?

Sort of.
With slight modifications, omitted for ease of exposition,
one does not need to split a variable at a bound.
That includes binary variables.


I'm rather surprised by the result on bounded versus
binary knapsacks mentioned in your subsequent post.
It's not quite the same,
but it's close enough to make me doubt my reasoning.

Of course, for small enough problems,
ease of programming might trump efficiency.
In that case, conversion to binary is the winner.

> Possibly your approach is favorable for a small number of
> excluded solutions and a large number of integers with big
> number range in the original problem, while mine might work
> better for a large number of excluded solutions and a small
> number of integers with small number range in the original
> problem.
>
> Best regards
>
> Xypron
>
>
>
> -------- Original-Nachricht --------
> > Datum: Mon, 21 Feb 2011 12:15:51 -0600 (CST)
> > Betreff: Re: [Help-glpk] shiftcover.mod - generate different solutions
>
> > On Fri, 18 Feb 2011, Xypron wrote:
> >
> > > In the appendix the shiftcover model is changed to only use binary
> > variables.
> > > This makes excluding possible solutions much easier.
> > >
> > > The idea for the conversion is replacing integer variables (crew[s]) by
> > sums
> > > of powers of two times binary variables (sum{i in I} 2**i * crew[s, i]).
> >
> > I'd recommend against.
> > Such conversion not only increases the dimensionality,
> > it increases the number of duplicate continuous
> > representations of physically equivalent solutions.
> >
> > If all variables and constraint coefficients are integer,
> > a single constraint on the nonbasic variables will exclude the
> > current solution without excluding any other integer solutions.
> >
> > Otherwise, something trickier might be in order:
> >                                                 *
> > Suppose xj in Lj..Hj and we want to eliminate x .
> >                           *
> > Add the constraint xj = xj + yj - (Hj+1-Lj)mj .
> >
> > yj in 0..Hj-Lj and mj in 0..1 .
> >                            *
> > Add the constraint SUM yj >= 1
> >                      j
> >
> > Such trickery is not necessary for binary variables or for other variables
> > at their respective bounds though complementing might be needed.
> >
> > In future iterations,
> > regard yj and mj as variables that need additional constraining.
> > In principle, if xj reaches a bound, you could use it instead of yj and
> > mj,
> > but the algorithm might get tricky.
> >
> > --
> > 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."
>
> --
> Schon gehört? GMX hat einen genialen Phishing-Filter in die
> Toolbar eingebaut! http://www.gmx.net/de/go/toolbar

--
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."