[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[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


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.


Nikolaus Sonnenschein

Attachment: modelMaximalCombi.lp
Description: Binary data

reply via email to

[Prev in Thread] Current Thread [Next in Thread]