Answers to: CPLEX finding upper and lower boundshttp://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds<p>Given some minimisation ILP or MILP defined in CPLEX using Concert in C#, I wish to find a lower and upper bound to the model.</p>
<p>The lower bound can, of course, be found by solving the linear relaxation (ignore integrality constraints).
The upper bound can be found by running a heuristic. CPLEX has three general-purpose MIP heuristics that I know of: Node heuristic, RINS heuristic, and Solution polishing. There are parameters in CPLEX for how often to run these heuristic, i.e. every <code>n</code> nodes.</p>
<p>I am having some difficulty just getting an upper and lower bound. Even if I set the <code>NodeLim</code> parameter to <code>0</code>, CPLEX spends a significant amount of time at the root node. I'm not sure what it's doing, perhaps applying cuts or trying to improve the best bound. I don't want it to do any of this: I just want the optimal value for the linear relaxation at the root node, and some good initial upper bound.</p>
<p>What is the process for obtaining these values in CPLEX using Concert in C#?
Thank you.</p>enWed, 05 Aug 2015 13:50:31 -0400Answer by Joris Kinablehttp://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds/12674<p>When you solve the problem as a MIP with root node bound equal to 0, CPLEX will solve the LP and apply cuts. Although you can disable all these cuts, the easiest way is to replace all integer variables by continues variables. To do this without rewriting your model, I recommend using the <a href="http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.ide.help/refcppopl/html/classes/IloConversion.html">IloConversion</a> class. This class allows you to temporarily 'override' the definitions of your variables. CPLEX will not apply any cuts when all variables are continues. As a result, you'll solve a pure LP. Note however that, depending on the size of your problem, just solving an LP may be expensive.</p>
<p>Assuming that your problem is a minimization problem, then the upper bound is simply a feasible solution to your problem. Note however that, the decision problem "does there exist at least one feasible solution to my problem" may already be a very hard problem. In fact, this can be as hard as solving your problem to optimality. Furthermore, for certain optimization problems, Mixed Integer Programming is great for calculating bounds, but not particularly good in producing feasible solutions. In contrast, Constraint Programming often produces good primal feasible solutions, but struggles in providing strong bounds on these solutions.</p>
<p>So in summary, without knowing what you try to solve, it is rather difficult to make good suggestions.</p>Joris KinableWed, 05 Aug 2015 13:50:31 -0400http://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds/12674