Bounding the linear solution to an MIP.
Wayne Duff-Riddell
just over half the value of what I know to be the IP solution. I understand
that the Solver starts by finding the LP solution and then works from there.
In my particular problem, the LP and IP solutions appear to lie on the same
branch (if that's the right terminology?) and the result is that the model
tests every integer solution from the LP solution to the IP solution. I
have set the hurdle value, lowered the integrality requirements and tried
both the Flow cut and Gomory Cut alternatives. I do not have the Barrier
option.
I have yet to solve the problem because of the time it takes. (My longest
run yet is about 5.5 hours before I lost patience and tried something else.)
I am now using brute force and have allocated the problem to a 533Mhz, 128MB
ram machine until the problem is solved.
I would however prefer a more elegant solution and wonder if there is any
way of forcing the LP solution closer to the IP solution through improved
model structure.
Anyone with any ideas or who would be interested in looking at the problem?
Wayne Duff-Riddell
Department of Civil Engineering
University of Stellenbosch
South Africa
e-mail: ti...@intekom.co.za
Lutz Tautenhahn
could anybody please help with the following problem:
Given are N objects, each object has (the same) I properties, which value
can be 0 or 1 (false or true). The task is to select M objects (M<N), so
that for all i in [1..I] the sum of the property-values of the M selected
object is 'close' to a given z_i (if possible then equal to z_i).
At the present time I solve the problem in this way:
The problem can be transformed: There are J=2^I distinct sets with m_j
objects (j=1..J).
The aim is to find a vector n with 0<=n and n<=m, so that ||z-A*n|| =>Min.
(The norm is not strongly defined as Euclidean Norm or Manhattan Norm, you
could use what makes the problem easier to solve.)
The Matrix A has a special structure (it is a sparse 0-1 Matrix which is
self similar when changing I).
Academic example (real world is much bigger): There are 200 objects, 30 have
properties (1,1,1), 20 have properties (1,1,0) ...
Find 100 objects so that 75 have property 1, 80 have property 2, 50 have
property 3.
30 20 40 35 25 15 20 15 | y z
=============================
1 1 1 1 1 1 1 1 | 200 100
1 1 1 1 0 0 0 0 | 125 75
1 1 0 0 1 1 0 0 | 90 80
1 0 1 0 1 0 1 0 | 115 50
The optimum solution for this would be:
30 20 0 25 20 5 0 0 | x z
=============================
1 1 1 1 1 1 1 1 | 100 100
1 1 1 1 0 0 0 0 | 75 75
1 1 0 0 1 1 0 0 | 75 80
1 0 1 0 1 0 1 0 | 50 50
Note that the objective is not Maximize A*n under the restriction A*n<=z and
that the n_j are required to be integer.
Currently I use a modified simplex method to solve this, but I'm not
satisfied because I suppose that there must be a better algorithm for this
problem, which uses the special problem structure (similar to MODI-Method
for Transportian problem or Hungarian Method for Assignment problem). The
main problem is that the memory requirement increases too much (a problem
with I+1 properties needs 4 times the memory of a problem with I properties
in the simplex tableau).
Could anybody give me a hint where to find something about this in the
literature (classification or algorithm)?
Lutz Tautenhahn
lutz.ta...@wirtschaft.tu-chemnitz.de
www.tu-chemnitz.de/~luta/
Lutz Tautenhahn
branch),
could anybody please help with the following problem:
Given are N objects, each object has (the same) I properties, which value
can be 0 or 1 (false or true). The task is to select M objects (M<N), so
that for all i in [1..I] the sum of the property-values of the M selected
At the present time I solve the problem in this way:
The problem can be transformed: There are J=2^I distinct sets with m_j
objects (j=1..J).
The aim is to find a vector n with 0<=n and n<=m, so that ||z-A*n|| =>Min.
(The norm is not strongly defined as Euclidean Norm or Manhattan Norm, you
could use what makes the problem easier to solve.)
The Matrix A has a special structure (it is a sparse 0-1 Matrix which is
Academic example (real world is much bigger): There are 200 objects, 30 have
properties (1,1,1), 20 have properties (1,1,0) ...
Find 100 objects so that 75 have property 1, 80 have property 2, 50 have
property 3.
30 20 40 35 25 15 20 15 | y z
=============================
1 1 1 1 1 1 1 1 | 200 100
1 1 1 1 0 0 0 0 | 125 75
1 1 0 0 1 1 0 0 | 90 80
1 0 1 0 1 0 1 0 | 115 50
The optimum solution for this would be:
30 20 0 25 20 5 0 0 | x z
=============================
1 1 1 1 1 1 1 1 | 100 100
1 1 1 1 0 0 0 0 | 75 75
1 1 0 0 1 1 0 0 | 75 80
1 0 1 0 1 0 1 0 | 50 50
Note that the objective is not Maximize A*n under the restriction A*n<=z and
that the n_j are required to be integer.
Currently I use a modified simplex method to solve this, but I'm not
satisfied because I suppose that there must be a better algorithm for this
problem, which uses the special problem structure (similar to MODI-Method
for Transportian problem or Hungarian Method for Assignement problem). The
Peter Spellucci
"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> writes:
|> Hello (and sorry for the double post, I'm a newby and was in the wrong
|> branch),
|> could anybody please help with the following problem:
|> Given are N objects, each object has (the same) I properties, which value
|> can be 0 or 1 (false or true). The task is to select M objects (M<N), so
|> that for all i in [1..I] the sum of the property-values of the M selected
|> objects is 'close' to a given z_i (if possible then equal to z_i).
hence you have _two_ objective functions:
you want to have a small N _and_ a small deviation ||Ay-z||
you could do that by introducing zero-one variables
y_i in {0,1} i=1,..,N (*)
f1(y,eps)=M=\sum_{i=1}^N y_i first objective function
f2(y,eps)=eps
-eps*ones <= Ay-z <= eps*ones, (**)
where ones is a vector of all ones of length I.
minimize a scalarization
theta*f1(y,eps)+f2(y,eps)
subject to the constraints (*) and (**) and increase theta from zero to some
large value. for theta=zero you get the best possible fit possible at all
and you can see then how much loss you may tolerate. with better knowledge
of the problem you surely can do better with this scalarization.
for zero-one LP's there are several possibilities,
see e.g.
http://plato.la.asu.edu/guide.html
and also the other links given there.
hope that helps
peter
Lutz Tautenhahn
but I'm afraid this would blow up the problem, because (I had forgotten to
mention it) in general is N>>2^I, so I would get a problem with N binary
variables with your approach instead of a problem with 2^I real variables,
as I do it by now.
To prevent confusion: The Matrix A in your modell is not the same as it was
in my model. Your A has I rows and N cols and holds the data of the N
objects with I properties, while my A has I+1 rows and J=2^I cols and does
not dependent on the data, it can be calculated by a_ij =((J-j) >> (I-i)) &
1 (C++ syntax). So I hoped I could use this special A matrix for a 'simpler'
simplex algorithm (similar to the algorithms for Transportian and
Assignement problem).
I can't imagine that a problem with 400 binary variables could be solved as
fast as it does this JavaScript ( see
www.tu-chemnitz.de/~luta/plt/opt_script.html ) which uses a modification of
the simplex algorithm.
But anyway, there is something in your modell that needs to be discussed:
Assume there is an optimum solution with an eps>0 (as in the example from
the first post with eps=80-75=5), so with a scalar eps also the other bounds
would be 'softened' (in our example by 5). I think there should be used a
vector eps instead of a scalar with f2(y,eps)=||eps|| and -eps <= Ay-z
<=eps.
Another thing is, that zero-one LP's remind me of Knapsack which is NP hard,
so I probably couldn't achieve the optimum solution for large problems, or
am I wrong in this point?
Lutz (the double poster).
Peter Spellucci
there was a misinterpretation from my side. I thought you wanted also to minimize
the number of objects used at all. concerning the "eps" : one eps corresponds
to the max-norm and a vector of "eps_i" would correspond to the sum-norm .
but this is not essential. you are right: the problem as I posed it would be
NP hard.
peter