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

[glpk xypron]

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
"duplicate continuous representations".

Does each excluded solution require a new set of mj?

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