IntegerProgrammingWithAMPL < OpsRes

---+ Integer Programming with AMPL 

[[VariablesInAMPL#types][Specifying variables to be integer or binary]] in AMPL will cause the solver, e.g., CPLEX, to use mixed-integer programming. This will often be enough to solve many of the problems you will encounter. However, if your integer programmes are taking a long time to solve you can use some "tricks" to speed up the branch-and-bound process.

---++ A "Simple" Integer Programme

To demonstrate the techniques we can use to control integer programming we will look at a simple integer programming problem:

<blockquote>
Jim has three requests for frozen ice sculptures, his commission is $1000, $7000 and $5000 respectively. He must hire a refrigeration unit to transport each one. The units cost $4000 each. The sculptures will be transported on a truck with capacity 1.7 tonnes and he estimates the total weight of each sculpture (including the refrigeration unit) to be 1 tonne, half a tonne and a quarter of a tonne respectively. Jim must decide which sculptures to make to maximize his profit.
</blockquote>

The AMPL model and data files, [[%ATTACHURL%/ice.mod][<tt>ice.mod</tt>]] and [[%ATTACHURL%/ice.dat][<tt>ice.dat</tt>]] respectively, are attached.

Solving this problem with AMPL and CPLEX is very fast (it is only a small problem):

<img src="%ATTACHURLPATH%/ice_original.jpg" alt="ice_original.jpg" width='669' height='218' />

However, sometimes all the technology behind CPLEX does not work so well and we need to control the branch-and-bound tree. We will use this small example problem to demonstrate the effect of changing the default behaviour of CPLEX.

First, let's remove all the CPLEX technology and re-solve our problem using an AMPL script:
<pre>
reset;

model ice.mod;
data ice.dat;

option solver cplex;

option presolve 0;
option cplex_options ('timing 1 mipdisplay 5 mipinterval 1' &
                     'presolve 0 mipcuts -1 cutpass -1 ' &
                     'heurfreq -1');

solve;

display Fridges, Make;
</pre>

With all CPLEXs "bells and whistles" removed we get a slightly larger branch-and-bound tree:

<img src="%ATTACHURLPATH%/ice_nofrills.jpg" alt="ice_nofrills.jpg" width='669' height='518' />

Let's look at ways to reduce the size of this branch-and-bound tree.<br /><br /><h5>Looking at the LP Relaxation</h5><br />Often you can gain insight into the branch-and-bound process by considering the <a href="#relaxation">LP relaxation</a>. You can relax integrality without reformulating using<br /><p>\begin{verbatim}<br />option relax_integrality 1;<br />\end{verbatim}<p> <br /> <br />If we look at the variables we can see where our solution is fractional:<br /><p><img src="ice_relaxation.jpg" /><p><br /> <br />As you can see we are using 2.8 fridge units for our 2.8 sculptures. Also, if we check the {\tt TotalWeight} constraint ({\tt display TotalWeight.body;}) we can see that the truck is at its weight limit.<br /> <br />It looks likely that we should only use 2 fridges. We can create some new suffixes to experiment with our hypothesis.<br /><br /><h5>Priorities, Searching and Directions</h5><br />AMPL and CPLEX allow you to define a <i>priority</i> for your integer variables. This means that if more than one integer variable is fractional in a solution, CPLEX will branch on the highest priority variable first. Let&rsquo;s add the priority {\tt suffix} to our run file (before solving):<br><br /><p>\begin{verbatim}<br />suffix priority IN, integer, >= 0, <= 9999;<br />\end{verbatim}<p><br />(now we can assign variables priorities ranging from 0 &ndash; least &ndash; to 9999 &ndash; most). Let&rsquo;s give the {\tt Fridges} variable a priority of 100 and the {\tt Make} variables a priority of 0 (<a href="AMPL Process#script">using {\tt let} statements</a>).<br /><p>\begin{verbatim}<br />let Fridges.priority := 100;<br />let {s in SCULPTURES} Make[s].priority := 0;<br />\end{verbatim}<p><br /><p><img src="ice_nofrills.jpg" /><p><br /><br />The branch-and-bound tree appears unchanged, so perhaps CPLEX had already branched on {\tt Fridges} first earlier. However, we can try a <i>breadth-first search</i> of the tree, since this will try different values for {\tt Fridges} before performing branching on other variables. Setting {\tt nodeselect} to 2 (best estimate) and {\tt backtrack} to 0 makes CPLEX perform a search very close to breadth-first (see <a href="https://www.ampl.com/BOOKLETS/amplcplex100userguide.pdf">The AMPL CPLEX User Guide</a> for full details).<br /><p>\begin{verbatim}<br />option cplex_options ('timing 1 mipdisplay 5 mipinterval 1 ' &<br />                     'presolve 0 mipcuts -1 cutpass -1 ' &<br />                     'heurfreq -1 ' &<br />                     'nodeselect 2 backtrack 0');<br />\end{verbatim}<p><br /><p><img src="ice_breadth.jpg" /><p><br /> <br />Now the tree has been fathomed earlier (it only has 4 nodes instead of 6). However, we are not sure if CPLEX branched down to 2 fridges first (our hypothetical optimum).<br /><br />To control the direction of the branches we can create a new suffix for the direction we should branch on each variable (-1 for down, 0 for no preference, 1 for up).<br /><p>\begin{verbatim}<br />suffix direction IN, integer, >= -1, <= 1;<br />\end{verbatim}<p><br /><br />We can force a down branch first on {\tt Fridges}:<br /><p>\begin{verbatim}<br />let Fridges.direction := -1;<br />\end{verbatim}<p><br /><p><img src="ice_breadth.jpg" /><p><br /> <br />This doesn&rsquo;t seem to have decreased the size of the branch-and-bound tree. Let&rsquo;s try one more thing. We have given CPLEX a good branch to try first, but we have not carefully considered what to do next. Let&rsquo;s remove the breadth-first search option and let CPLEX decide how to proceed:<br /><code><br /><span style="font-family: monospace;">reset;<br><br /><br><br />model ice.mod;<br><br />data ice.dat;<br><br /><br><br />option solver cplex;<br><br /><br><br />option presolve 0;<br><br />option cplex_options ('timing 1 mipdisplay 5 mipinterval 1' &amp;<br><br />                     <br />'presolve 0 mipcuts -1 cutpass -1 ' &amp;<br><br />                     <br />'heurfreq -1');<br><br /><br><br />suffix priority IN, integer, &gt;= 0, &lt;= 9999;<br><br />suffix direction IN, integer, &gt;= -1, &lt;= 1;<br><br /><br><br />let Fridges.priority := 100;<br><br />let {s in SCULPTURES} Make[s].priority := 0;<br><br /><br><br />let Fridges.direction := -1;<br><br /><br><br />solve;<br><br /><br><br />display Fridges, Make;</span><span<br /> style="font-family: monospace;"></span><br /></code><br /><p><img src="ice_best.jpg" /><p><br /><br />Now we have reduced our branch-and-bound tree to a single node by making a good choice about our first variable branch.<br /><br />As stated earlier, CPLEX does a lot of good things automatically for you. Often, these &ldquo;tricks&rdquo; will be enough to solve your mixed-integer programming problems. However, if your problem is taking a long time to solve, you can experiment with adding some of your own control to the branch-and-bound process. History has shown that problem-specific approaches often work very well for hard integer programmes.<br /> 

-- Main.MichaelOSullivan - 23 Apr 2008
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
dat	ice.dat	r1	manage	0.2 K	2008-04-23 - 07:10	MichaelOSullivan
mod	ice.mod	r1	manage	0.4 K	2008-04-23 - 07:10	MichaelOSullivan
This topic: OpsRes > WebHome > MathematicalProgramming > IntegerProgramming > IntegerProgrammingWithAMPL
Topic revision: r2 - 2008-04-23 - MichaelOSullivan