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

[Michael Hennebry]

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