Mixed-Integer linear programming

Class date(s):

25 March 2015



Download video: Link [787 M]



Download video: Link [905 M]

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	Representation of integer variables Types of problems that can be solved with integer variables	Handout from class	Video	See the GAMS codes below
30 March	12A	More problems that can be solved with integer variables Knapsack problem Mutual exclusivity constraints Dependence constraints Allocation problems	Handout from class	Video	See the GAMS codes below
30 March	12B	More problems that can be solved with integer variables Allocation problems Set covering problems Choice of locations Solutions methods of problems with integer variables Introducing the branch and bound procedure

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;