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>enSun, 09 Aug 2015 19:05:08 -0400Comment by Ozzah on Joris Kinable's answerhttp://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds#12682<p>Thanks, I saw that blog post already but the C# API doesn't seem to expose an <code>Iterator</code> method. There is a <code>GetEnumerator()</code> method, but it only enumerates over the objective function and constraints. I haven't tried to go deeper to see if I can enumerate over the terms in the constraints.</p>OzzahSun, 09 Aug 2015 19:05:08 -0400http://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds#12682Comment by Joris Kinable on Joris Kinable's answerhttp://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds#12681<p>You can iterate over the variables, but it's a bit inefficient. See Paul's blog post for details: <a href="http://orinanobworld.blogspot.com/2010/08/iterating-over-cplex-model-sequel.html">http://orinanobworld.blogspot.com/2010/08/iterating-over-cplex-model-sequel.html</a>
Easier to keep track of your variables. I usually do something like this:</p>
<p>Map<edge, ilointvar=""> vars=new LinkedHashMap<>();</p>
<p>...</p>
<p>IntVar[] varsArray=vars.values().toArray(new IloIntVar[vars.size()]);</p>
<p>double[] values=cplex.getValues(varsArray);</p>
<p>List<edge> usedEdges=new ArrayList<>();</p>
<p>int index=0;</p>
<p>for(Edge e : vars.keySet()){</p>
<pre><code>if(doubleToBoolean(values[index]))
usedEdges.add(e);
index++;
</code></pre>
<p>}</p>Joris KinableFri, 07 Aug 2015 18:34:39 -0400http://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds#12681Comment by Ozzah on Joris Kinable's answerhttp://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds#12679<p>The Conversion method works well to find the LB via linear relaxation. I haven't found any way to enumerate all variables in the model, so I have to keep track of them manually in code. Is there a better way? As for the UB, yes I know it can be just as hard as finding an optimal solution. In most practical cases, however, a feasible solution can be found somewhat quickly, at least by my experience. Is there any way to invoke Node Select or RINS Heuristic manually? Right now I just set <code>IntSol</code> to 1 and then either just use that solution or use the Polishing heuristic on that.</p>OzzahFri, 07 Aug 2015 09:25:53 -0400http://www.or-exchange.com/questions/12671/cplex-finding-upper-and-lower-bounds#12679Answer 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