Difference between revisions of "Mixed-Integer linear programming"
Jump to navigation
Jump to search
Kevin Dunn (talk | contribs) |
Kevin Dunn (talk | contribs) |
||
| Line 273: | Line 273: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
|} | |} | ||
=== 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. | |||
[[Image:4G3-2015-MIP-Practice-problem.png|750px]] | |||
<!-- | |||
\begin{center}\begin{tabular}{ccc|ccc} | |||
Partial & ${\bf x}_{\rm rel}^{(k)}$ & $z_{\rm rel}^{(k)}$ & Partial & ${\bf x}_{\rm rel}^{(k)}$ & $z_{\rm rel}^{(k)}$ \\ \hline | |||
(\#,\#,\#) & (0.2,1,0) & 82.80 & (0,0,1) & \multicolumn{2}{c}{Infeasible} \\ | |||
(\#,\#,0) & (0.2,1,0) & 82.80 & (0,1,\#) & (0,1,0.67) & 80.67 \\ | |||
(\#,\#,1) & (0,0.8,1) & 79.40 & (0,1,0) & (0,1,0) & 28.00 \\ | |||
(\#,0,\#) & (0.7,0,0) & 81.80 & (0,1,1) & (0,1,1) & 77.00 \\ | |||
(\#,0,0) & (0.7,0,0) & 81.80 & (1,\#,\#) & (1,0,0) & 74.00 \\ | |||
(\#,0,1) & (0.4,0,1) & 78.60 & (1,\#,0) & (1,0,0) & 74.00 \\ | |||
(\#,1,\#) & (0.2,1,0) & 82.80 & (1,\#,1) & (1,0,1) & 63.00 \\ | |||
(\#,1,0) & (0.2,1,0) & 82.80 & (1,0,\#) & (1,0,0) & 74.00 \\ | |||
(\#,1,1) & (0,1,1) & 77.00 & (1,0,0) & (1,0,0) & 74.00 \\ | |||
(0,\#,\#) & (0,1,0.67) & 80.67 & (1,0,1) & (1,0,1) & 63.00 \\ | |||
(0,\#,0) & (0,1,0) & 28.00 & (1,1,\#) & (1,1,0) & 62.00 \\ | |||
(0,\#,1) & (0,0.8,1) & 79.40 & (1,1,0) & (1,1,0) & 62.00 \\ | |||
(0,0,\#) & \multicolumn{2}{c|}{Infeasible} & (1,1,1) & (1,1,1) & 51.00 \\ | |||
(0,0,0) & \multicolumn{2}{c|}{Infeasible} & \\ | |||
\end{tabular}\end{center} | |||
--> | |||
Revision as of 12:14, 6 April 2015
| 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 |
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
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.
