Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|

## Integer Programming with AMPL | ||||||||

Line: 8 to 8 | ||||||||

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

Changed: | ||||||||

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

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

Changed: | ||||||||

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

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

Changed: | ||||||||

< < | ||||||||

> > | ||||||||

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: | ||||||||

Changed: | ||||||||

< < | 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; | |||||||

> > | 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: | ||||||||

Changed: | ||||||||

< < | ||||||||

> > | ||||||||

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

Line: 33 to 51 | ||||||||

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

Changed: | ||||||||

< < | ||||||||

> > | ||||||||

Changed: | ||||||||

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

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

Changed: | ||||||||

< < | 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; | |||||||

> > | 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; | |||||||

Changed: | ||||||||

< < | ||||||||

> > | ||||||||

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

Changed: | ||||||||

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

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

Changed: | ||||||||

< < | ||||||||

> > | ||||||||

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

Changed: | ||||||||

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

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

We can force a down branch first on `Fridges` : | ||||||||

Changed: | ||||||||

< < | let Fridges.direction := -1; | |||||||

> > | let Fridges.direction := -1; | |||||||

Changed: | ||||||||

< < | ||||||||

> > | ||||||||

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: | ||||||||

Changed: | ||||||||

< < | 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; | |||||||

> > | 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; | |||||||

Changed: | ||||||||

< < | ||||||||

> > | ||||||||

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

View topic | History: r5 < r4 < r3 < r2 | More topic actions...

Copyright © 2008-2022 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