Mixed-Integer linear programming
Resources
Scroll down, if necessary, to see the resources.
| Date | Class number | Topic | Slides/handouts for class | Video file | References and Notes |
|---|---|---|---|---|---|
| 25 March | 11B |
|
Video |
See the GAMS codes below | |
| 30 March | 12A |
More problems that can be solved with integer variables
|
Video |
See the GAMS codes below | |
| 01 April | 12B |
The branch and bound procedure to solve integer problems |
See code below to solve the original problem, and then the relaxed problem | ||
| 06 April | 13A |
More problems that can be solved with integer variables
|
Solving a basic ILP
free variable income "total income";
positive variables x1, x2;
binary variable delta "use ingredient x3 or not at all";
EQUATIONS
obj "maximize income",
blend "blending constraint";
obj.. income =E= 18*x1 - 3*x2 - 9*(20*delta);
blend.. 2*x1 + x2 + 7*(20*delta) =L= 150;
x1.up = 25;
x2.up = 30;
model recipe /all/;
SOLVE recipe using MIP maximizing income;
Solving the knapsack problem
free variable value "total value";
sets j "item j" /1*5/;
binary variables x(j) "whether to include item in the knapsack";
parameter v(j) "value of object j"
/1 4,
2 2,
3 10,
4 1,
5 2/;
parameter w(j) "weight of object j"
/1 12,
2 1,
3 4,
4 1,
5 2/;
EQUATIONS
obj "maximize value",
weight "weight constraint";
obj.. value =e= sum(j, v(j)*x(j));
weight.. sum(j, w(j)*x(j)) =L= 15;
model knapsack /all/;
solve knapsack using mip maximizing value;
Solving the knapsack problem for selecting amount projects, with constraints
free variable value "total value";
sets j "item j" /1*5/;
binary variables x(j) "whether to include item in the project";
parameter v(j) "value of object j"
/1 50,
2 72,
3 25,
4 41,
5 17/;
parameter w(j) "cost of object j"
/1 8,
2 21,
3 15,
4 10,
5 7/;
EQUATIONS
obj "maximize value",
weight "weight constraint",
me1v2 "1 and 2 are mutually exclusive",
me1v3v5 "1, 3 and 5 are mutually exclusive",
d4v3 "4 depends on 3";
obj.. value =e= sum(j, v(j)*x(j));
weight.. sum(j, w(j)*x(j)) =L= 35;
me1v2.. x('1') + x('2') =L= 1;
me1v3v5.. x('1') + x('3') + x('5') =L= 1;
d4v3.. x('4') =L= x('3');
model projects /all/;
solve projects using mip maximizing value;
Binary problem relaxation
Here is an example of an unusual case, where the binary problem (original) has the same optimum as the relaxed problem (LP). In this case the LP solution happens to be at values of 0 and 1 for the search variables, so this relaxed problem has the same optimum as the binary problem that it relaxed.
| Original problem | Relaxed problem |
|---|---|
free variable cost "total cost";
sets j "item j" /1*4/;
binary variables x(j) "whether to include item in the purchase";
parameter c(j) "cost of object j"
/1 3,
2 4,
3 6,
4 14/;
EQUATIONS
obj "cost",
LP_constraint,
IP_constraint,
NLP_constraint;
obj.. cost =e= sum(j, c(j)*x(j));
LP_constraint.. sum(j, x(j)) =G= 1;
IP_constraint.. x('2') + x('4') =G= 1;
NLP_constraint.. x('3') + x('4') =G= 1;
MODEL purchase /all/;
SOLVE purchase using MIP minimizing cost;
|
free variable cost "total cost";
sets j "item j" /1*4/;
positive variables x(j) "whether to include item in the purchase";
parameter c(j) "cost of object j"
/1 3,
2 4,
3 6,
4 14/;
EQUATIONS
obj "cost",
LP_constraint,
IP_constraint,
NLP_constraint;
obj.. cost =e= sum(j, c(j)*x(j));
LP_constraint.. sum(j, x(j)) =G= 1;
IP_constraint.. x('2') + x('4') =G= 1;
NLP_constraint.. x('3') + x('4') =G= 1;
MODEL purchase /all/;
SOLVE purchase using LP minimizing cost;
|
Binary problem relaxation
This is the problem we looked at in class for the generators.
Notice that the only differences are:
- the binary variables become positive variables, thepr
- the problem is solved as an LP not an MIP
- the constraints for .LO and .UP are added, where required, depending on the partial solution solved
| Original problem solved in class | Relaxed problem solved in class |
|---|---|
free variable cost "total cost";
sets j "item j" /1*4/;
binary variables x(j) "whether to use generator";
parameter c(j) "cost of using generator j"
/1 7,
2 12,
3 5,
4 14/;
parameter p(j) "power of generator j"
/1 300,
2 600,
3 500,
4 1600/;
EQUATIONS
obj "cost",
power_constraint;
obj.. cost =e= sum(j, c(j)*x(j));
power_constraint.. sum(j, p(j)*x(j)) =G= 700;
MODEL purchase /all/;
SOLVE purchase using MIP minimizing cost;
|
free variable cost "total cost";
sets j "item j" /1*4/;
positive variables x(j) "whether to use generator";
parameter c(j) "cost of using generator j"
/1 7,
2 12,
3 5,
4 14/;
parameter p(j) "power of generator j"
/1 300,
2 600,
3 500,
4 1600/;
EQUATIONS
obj "cost",
power_constraint;
obj.. cost =e= sum(j, c(j)*x(j));
power_constraint.. sum(j, p(j)*x(j)) =G= 700;
* Solve the problem for the partial solution: (#, 0, #, 1)
x.LO('1')=0;
x.UP('1')=1;
x.LO('2')=0;
x.UP('2')=0;
x.LO('3')=0;
x.UP('3')=1;
x.LO('4')=1;
x.UP('4')=1;
MODEL purchase /all/;
SOLVE purchase using LP minimizing cost;
|