[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Michael Hennebry
Subject: Re: [Help-glpk] shiftcover.mod - generate different solutions
Date: Mon, 21 Feb 2011 12:15:51 -0600 (CST)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]