[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] shiftcover.mod - generate different solutions
From: |
glpk xypron |
Subject: |
Re: [Help-glpk] shiftcover.mod - generate different solutions |
Date: |
Mon, 21 Feb 2011 22:37:40 +0100 |
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