MixedInteger linear programming
Class date(s):  25 March 2015  
 
 
 
 
 
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 
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

Video 
See code below for the simple scheduling problem (3 products on 1 unit).  
08 April  13B 
Scheduling problems Course wrapup 
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;
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 maximize 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 "relaxed" refers to the relaxed problem solution.
Use the depthfirst search method, and when branching, choose the branch with \(x_i = 0\) before the \(x_i=1\) branch.
If you do this, your nodes will have the following solution order:
Node 0 \((z=82.80)\)
Node 1 \((z=80.67)\)
Node 2 \((z=28.00)\) [incumbent]
Node 3 \((z=79.4)\)
Node 4 \((z=\text{Infeasible})\)
Node 5 \((z=77.00)\) [incumbent; turns out this is the eventual optimum]
Node 6 \((z=74.00)\)
[The end: can you prove why?]
Simple schedule: one unit, 3 products
This example was covered in class 13A:
set j "jobs" /1*3/; alias (j,jp); parameter p(j) "process time of j" / 1 15, 2 6, 3 9/; scalar M "bigM"; M = sum(j, p(j)); free variable MeanComp "Mean completion time"; positive variables x(j) "Start time of job j"; binary variables y(j,jp) "Disjunctive variable for j and jp"; EQUATIONS MeanCeqn "Mean completion time", Disj1(j,jp) "Disjunctive part 1", Disj2(j,jp) "Disjunctive part 2"; MeanCeqn.. MeanComp =E= sum(j, x(j)+p(j) ) / card(j); Disj1(j,jp)$(ord(j) lt ord(jp)).. x(j) + p(j) =L= x(jp) + M*(1y(j,jp)); Disj2(j,jp)$(ord(j) lt ord(jp)).. x(jp)+ p(jp) =L= x(j) + M*y(j,jp); MODEL simplesched /all/; SOLVE simplesched using MIP minimizing MeanComp;
Scheduling 3 products on 4 units
This example was covered in class 13B:
* Based on: https://comp.uark.edu/~rrardin/oorbook/software/gams/custommw.gms set j "Products" /A*C/, k "Units" /1*4/; alias (j,jp); alias (k,kp); set succ(j,k,kp) "Product j successor pairs" /A.1.2, A.2.3, A.3.4, B.3.4, C.3.2, C.2.4/; TABLE p(j,k) "Process time of product j on unit k" 1 2 3 4 A 1 5 4.0 1.5 B 0 0 4.5 1.0 C 0 3 5.0 1.5; scalar M "bigM"; M = sum((j,k), p(j,k)); FREE variable AverageC "Average completion time"; POSITIVE variables x(j,k) "Start time of job (product) j on unit k: j.k"; BINARY variables y(j,jp,k) "Disjunctive variable for j and jp on k"; EQUATIONS avgComplete "Average completeness", pred(j,k,kp) "Precedence within jobs", disj1(j,jp,k) "Disjunctive part 1 for j and jp on k", disj2(j,jp,k) "Disjunctive part 2 for j and jp on k"; avgComplete.. AverageC =E= sum((j,k), x(j,k)+p(j,k) ); * These are the precedence constraints pred(j,k,kp)$succ(j,k,kp).. x(j,k) + p(j,k) =L= x(j,kp); disj1(j,jp,k)$(ord(j) lt ord(jp) and p(j,k) gt 0 and p(jp,k) gt 0).. x(j,k) + p(j,k) =L= x(jp,k) + M*(1y(j,jp,k)); disj2(j,jp,k)$(ord(j) lt ord(jp) and p(j,k) gt 0 and p(jp,k) gt 0).. x(jp,k) + p(jp,k) =L= x(j,k) + M*y(j,jp,k); MODEL Jobshop /all/; option mip = mosek; SOLVE Jobshop USING MIP minimizing AverageC;