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>enMon, 09 Nov 2015 09:59:52 -0500Comment by Paul Rubin on Paul Rubin's answerhttp://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints#13004<p>The interactive optimizer is unsuitable for any sort of decomposition method, including Benders. You would have to use one of the programming APIs (or possibly OPL models and a script to let them interact). CPLEX ships with source code for a number of examples, and I believe there is at least one Benders example among them. A reference for combinatorial Benders cuts is "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming" by Gianni Codato and Matteo Fischetti (Operations Research vol. 54, no. 4, 2006).</p>Paul RubinMon, 09 Nov 2015 09:59:52 -0500http://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints#13004Comment by Nero on Paul Rubin's answerhttp://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints#13003<p>For example, I have a conditional constraint: if c = 1 --> a >= b Using big M-constraint the constraint will be modelled as: a - b + (1-c)*M >=0. Can you please give me an example about using combinatorial benders cuts to model the problem (in interactive optimizer)?</p>
<p>Thank you so much.</p>NeroMon, 09 Nov 2015 07:48:40 -0500http://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints#13003Answer 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