Answers to: CPLEX: Strange behaviour with big M constraintshttp://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints<p>Dear,
Would you please help me answer some questions regard to using big M constraints in cplex solver?
I have an optimization problem containing big M constraints, such as, a - b - M*c >= -M. The purpose of the constraint is c = 1 -> a>=b; I set M as MAX_INT.
I observed that with default integrality tolerance value (1e-5), cplex solver produces solution but violates the constraint above, for example, c=0.99... and a < b (instead of a >= b).
Then I reduce the integrality tolerance (tol) value from 1e-5 to 1e-15, I observed that with tol= 1e-7 cplex produces solution that satisfies all constraints, but with tol=1e-10 cplex produces solution that does not satisfies the constraint above. I do not understand the behaviour. Can you please help me explain that ?
Additionally, with tol= 1e-7 and tol = 1e-14 cplex produces solutions that satisfy all constraints, but the optimal values that cplex produces in these two cases are different. I though there is only one optimal solution, but here cplex produces different optimal points with different integrality tolerance values. Would you please help me explain that ?</p>
<p>Thank you so much.</p>enSat, 07 Nov 2015 17:31:28 -0500Answer by Paul Rubinhttp://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints/12995<p>Ehsan is correct that large values of M are a known source of numerical instability. Also, you may need to worry about more than just the integrality tolerance; the constraint tolerance will determine whether a value of \(a\) <em>slightly</em> less than \(b\) is accepted as feasible.</p>
<p>If you cannot find a reasonably small value of M that is valid, you might want to do a search for "combinatorial Benders cuts" -- Benders decomposition to eliminate the need for big M versions of logical implication constraints.</p>Paul RubinSat, 07 Nov 2015 17:31:28 -0500http://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints/12995Answer by Ehsanhttp://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints/12990<p>Choosing very large big-M values could cause numerical instability. You should try finding the smallest value for each big-M constraint that would ensure accepting all the feasible solutions and rejecting the infeasible ones. This could be done either based on a structural property of the problem data or trial and error.</p>EhsanMon, 02 Nov 2015 11:54:08 -0500http://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints/12990