Looking at the LP Relaxation

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.

Priorities, Searching and Directions

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;

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.