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

[glpk xypron]

Hello Michael,

in

Hans Kellerer, Ulrich Pferschy, und David Pisinger
Knapsack Problems, Springer, 2004

you can find the following on the conversion of bounded knapsack
problems (with integers) to knapsack problems (with binaries):

7.3.2 Branch-and Bound Algorithms
During the seventies many papers appeared on specialized branch-and-bound 
methods for various integer programming problems related to the knapsack 
family. A few of them dealt explicitly with (BKP). However, we are not aware of 
any relevant publication on this topic since 1979. It seems that further 
research was more or less stopped by the observation that these 
branch-and-bound algorithms customized for (BKP) were generally outperformed by 
the application of branch-and-bound methods to the instance of (KP) derived by 
the transformation of Section 7.1.1.

(Section 7.1.1 describes resplacing integer variables by
sums of powers of two.)

Please, observe that the binarize option of glpsol also implements
this substitution.

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