Hi,

I am doing a LP with only continuous variables. Each continuous variable is bound by 0 and some upper value.

The original problem is like below with rhs known fixed values, we call it problem A:

x1 + x2 + x3 <= rhs1

x2 + x3 <= rhs2

x2 + x4 + x5 <= rhs3

objective maximize( p1x1 + p2x2 + p3x3 + p4x4 + p5x5 ) where p are just known weights

I can solve this problem with CPLEX easily. Given the solution, I have an optimal objective T

Now, I want to ask the question: suppose I want to still achieve objective T, but with a different set of rhs, what can the rhs be?  My objective is to minimize sum of rhs.

The new problem is now below with RHS as variables to be solved, we call it problem B

x1 + x2 + x3 - RHS1 <=0

x2 + x3 - RHS2  <= 0

x2 + x4 + x5 - RHS3 <= 0

p1x1 + p2x2 + p3x3 + p4x4 + p5x5 = T

objective: minimize( RHS1 + RHS2 + RHS3 )

With the prior knowledge of problem A, we know RHS1 + RHS2 + RHS3 can at least be as small as the values for rhs1 + rhs2 + rhs3

But when I solve problem B with CPLEX, I got a solution for RHS1 + RHS2 + RHS3 bigger than rhs1 + rhs2 + rhs3.

Any thoughts?

------------------------------
Fangya Li
------------------------------

It could conceivably be a scaling issue, or a tolerance issue with the equation constraint (or an error that crept into the formulation of the revised model). You might try adding a constraint that the sum of the RHS variables must be <= the sum of the original right hand sides, and then solve the modified LP. If CPLEX says the modified LP is infeasible, you can ask for an irreducible infeasible subset of constraints (which will include the added one) and then check to see which are violated by the original optimal solution and the original right-hand sides. That might give you a lead to go on.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

A bug is highly improbable. Try turning on the numerical precision emphasis parameter and see if results in different behavior in problem B. If so, it may indicate poor scaling (although even well-scaled problems occasionally have numerical stability issues).

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------