help-glpk
[Top][All Lists]

## [Help-glpk] MIP: Problem witch binary variables

 From: Nikolaus Sonnenschein Subject: [Help-glpk] MIP: Problem witch binary variables Date: Tue, 10 Jun 2008 12:28:24 +0200

Hi.

I have a problem with a mip and I am struggling now for quite a long time
to find a solution for it.

A short description of what I am doing:
1. I solve a lp in which I maximize the value of the structural variable z.
2. Then I reformulate the lp into a mip in which the bounds of z are fixed near the lp solution
and I utilize additional binary variables to switch between zero and default bounds for all structural variables.
The new objective function is just the sum over all binary variables.

I want to find the largest combination of structural variables that can be removed from the system/constrained to zero
without a decrease in z.

e.g. usage of of the binary variable y("R_PMDPHT") to switch between two behaviors.

U("R_PMDPHT"): R("R_PMDPHT") + 10000 y("R_PMDPHT") <= 10000
L("R_PMDPHT"): R("R_PMDPHT") >= 0
0 <= R("R_PMDPHT") <= 10000

If y("R_PMDPHT") becomes 1 than hopefully 0 <= R("R_PMDPHT") <= 0 .
But I get this strange solution when I solve the mip with
"glpsol --cpxlp --exact modelMaximalCombi.lp".

From the solution output:
...
479 U("R_PMDPHT")         10000                       10000
791 L("R_PMDPHT")          0.001             0
...
229 y("R_PMDPHT")         *              1             0             1
...
380 R("R_PMDPHT")        0.001             0         10000
...

So R("R_PMDPHT") has a value greater zero although it should not.
Yeah, I now the bounds are really big and surely mip rounding issues come
into play.
(I refer here to the "[Help-glpk] MIP rounding" email from Jean-Sebastien Roy. Date: Sun, 6 Jul 2003 22:55:23 +0200).

But even when I solve the problem with lp relaxation like this --
"glpsol --cpxlp --exact --nomip modelMaximalCombi.lp" --
I get the following result:
...
479 U("R_PMDPHT")         NU         10000                       10000        0.0001
791 L("R_PMDPHT")          B          0.001             0
...
229 y("R_PMDPHT")          B              1             0             1
...
380 R("R_PMDPHT")         B          0.001             0         10000
...

y("R_PMDPHT") is exactly 1 and so R("R_PMDPHT") should be zero.
Is this normal? Am I overseeing something?
Could it be that the normal boundary statement
0 <= R("R_PMDPHT") <= 10000
plays a role?

I attached the mip problem in cplex format.

Best,

Nikolaus Sonnenschein modelMaximalCombi.lp
Description: Binary data