TWiki> OpsRes Web>MathematicalProgramming > IntegerProgramming>IntegerProgrammingWithAMPL (11 May 2008, MichaelOSullivan)EditAttach

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.

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

Jim has three requests for frozen ice sculptures, his commission is $10000, $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.

The AMPL model and data files, `ice.mod` and `ice.dat` respectively, are attached.

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

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:

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;

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

Let's look at ways to reduce the size of this branch-and-bound tree.

Often you can gain insight into the branch-and-bound process by considering the LP relaxation. You can relax integrality without reformulating using `option relax_integrality 1;`

.

If we look at the variables we can see where our solution is fractional:

As you can see we are using 2.8 fridge units for our 2.8 sculptures. Also, if we check the `TotalWeight`

constraint (`display TotalWeight.body;`) we can see that the truck is at its weight limit.

It looks likely that we should only use 2 fridges. We can create some new suffixes to experiment with our hypothesis.

AMPL and CPLEX allow you to define a *priority* 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's add the priority *suffix* to our run file (before solving):

suffix priority IN, integer, >= 0, <= 9999;(now we can assign variables priorities ranging from 0 - least - to 9999 - most). Let's give the

`Fridges`

variable a priority of 100 and the `Make`

variables a priority of 0:
let Fridges.priority := 100; let {s in SCULPTURES} Make[s].priority := 0;

The branch-and-bound tree appears unchanged, so perhaps CPLEX had already branched on `Fridges`

early in the branch-and-bound tree. However, we can try a *breadth-first search* of the tree, since this will try different values for `Fridges`

before performing branching on other variables. Setting `nodeselect`

to 2 (best estimate) and `backtrack`

to 0 makes CPLEX perform a search very close to breadth-first (see The AMPL CPLEX User Guide for full details).

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

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).

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).

suffix direction IN, integer, >= -1, <= 1;

We can force a down branch first on `Fridges`

:

let Fridges.direction := -1;

This doesn't seem to have decreased the size of the branch-and-bound tree.

Let'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's remove the breadth-first search option and let CPLEX decide how to proceed:

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'); suffix priority IN, integer, >= 0, <= 9999; suffix direction IN, integer, >= -1, <= 1; let Fridges.priority := 100; let {s in SCULPTURES} Make[s].priority := 0; let Fridges.direction := -1; solve; display Fridges, Make;

Now we have reduced our branch-and-bound tree to a single node by making a good choice about our first variable branch and letting CPLEX proceed from there.

As stated earlier, CPLEX does a lot of good things automatically for you. Often, these "tricks" 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.

-- MichaelOSullivan - 23 Apr 2008

I | Attachment | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|

dat | ice.dat | manage | 0.2 K | 23 Apr 2008 - 07:10 | MichaelOSullivan | |

mod | ice.mod | manage | 0.4 K | 23 Apr 2008 - 07:10 | MichaelOSullivan |

Topic revision: r5 - 11 May 2008 - 23:31:59 - MichaelOSullivan

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback