Mixed-Integer linear programming

Class date(s):	25 March 2015
Download video: Link [787 M]

Resources

Scroll down, if necessary, to see the resources.

Date	Class number	Topic	Slides/handouts for class	Video file	References and Notes
25 February	11B	Representation of integer variables Types of problems that can be solved with integer variables	Handout from class	Video

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;