Mixed-Integer linear programming

Class date(s):	25 March 2015
Download video: Link [787 M]
Download video: Link [905 M]
Download video: Link [884 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
01 April	12B	The branch and bound procedure to solve integer problems	Handout from class Sequence of the branch and bound steps	Video	See code below to solve the original problem, and then the relaxed problem. See another example problem below (with solution).
06 April	13A	Working towards understanding schedule problems in engineering Gantt chart approach What the search variables mean What objective function choices exist Setting up the integer (disjunctive) variables constraints	Handout from class		See code below to simple scheduling problem.
08 April	13B	More problems that can be solved with integer variables: Scheduling problems Choice of locations Travelling salesmen problem

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

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;

Example problem to practice

The objective is to minimize the objective function value, \(z\). The table or partial solutions is provided below. The only constraints are that all the 3 search variables must be binary (0 or 1). The "rel" refers to the relaxed problem solution.