TOMLAB Solving Linear Quadratic and Integer Programming Problems: Difference between revisions
mNo edit summary |
|||
(29 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
{ | [[Category:Manuals]] | ||
{{Part Of Manual|title=the TOMLAB Manual|link=[[TOMLAB|TOMLAB Manual]]}} | |||
This section describes how to define and solve linear and quadratic programming problems, and mixed-integer linear programs using TOMLAB. Several examples are given on how to proceed, depending on if a quick solution is wanted, or more advanced tests are needed. TOMLAB is also compatible with MathWorks Optimization TB. See [[TOMLAB Appendix E]] for more information and test examples. | |||
The test examples and output files are part of the standard distribution of TOMLAB, available in directory ''usersguide'', and all tests can be run by the user. There is a file ''RunAllTests'' that goes through and runs all tests for this section. | |||
The test examples and output | |||
Also see the files ''lpDemo.m'', ''qpDemo.m'', and ''mipDemo.m'', in the directory ''examples'', where in each file a set of simple examples are defined. The examples may be ran by giving the corresponding file name, which displays a menu, or by running the general TOMLAB help routine ''tomHelp.m''. | Also see the files ''lpDemo.m'', ''qpDemo.m'', and ''mipDemo.m'', in the directory ''examples'', where in each file a set of simple examples are defined. The examples may be ran by giving the corresponding file name, which displays a menu, or by running the general TOMLAB help routine ''tomHelp.m''. | ||
==Linear Programming Problems== | |||
The general formulation in TOMLAB for a linear programming problem is | The general formulation in TOMLAB for a linear programming problem is | ||
Line 15: | Line 14: | ||
<math> | <math> | ||
\begin{array}{ll} | \begin{array}{ll} | ||
\min\limits_{x} & f(x) = c^T x \\ | \min\limits_{x} & f(x) = c^T x \\ | ||
Line 27: | Line 25: | ||
where <math> | where <math>c, x, x_L, x_U \in \mathbb{R}^n</math>, | ||
<math> | <math>A \in \mathbb{R}^{m_1 \times n}</math>, and <math>b_L,b_U \in \mathbb{R}^{m_1}</math>. | ||
Equality constraints are defined by setting | Equality constraints are defined by setting | ||
the lower bound equal to the upper bound, i.e. | the lower bound equal to the upper bound, i.e. | ||
for constraint <math> | for constraint <math>i: b_{L}(i) = b_{U}(i)</math>. | ||
To illustrate the solution of LPs consider the simple linear programming test problem | To illustrate the solution of LPs consider the simple linear programming test problem | ||
Line 37: | Line 35: | ||
<math> | <math> | ||
\begin{array}{ccccl} | \begin{array}{ccccl} | ||
\min\limits_{x_{1},x_{2}} & f(x_{1},x_{2}) & = & -7x_{1}-5x_{2} & | \min\limits_{x_{1},x_{2}} & f(x_{1},x_{2}) & = & -7x_{1}-5x_{2} & | ||
Line 43: | Line 40: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
named ''LP Example''. | named ''LP Example''. | ||
Line 50: | Line 48: | ||
'''File: '''tomlab/usersguide/lpExample.m | '''File: '''tomlab/usersguide/lpExample.m | ||
< | <source lang="matlab"> | ||
Name = 'lptest'; | Name = 'lptest'; | ||
c = [-7 -5]'; % Coefficients in linear objective function | c = [-7 -5]'; % Coefficients in linear objective function | ||
A = [ 1 2 | A = [ 1 2 | ||
4 1 ]; % Matrix defining linear constraints | 4 1 ]; % Matrix defining linear constraints | ||
b_U = [ 6 12 ]'; % Upper bounds on the linear inequalities | b_U = [ 6 12 ]'; % Upper bounds on the linear inequalities | ||
x_L = [ 0 0 ]'; % Lower bounds on x | x_L = [ 0 0 ]'; % Lower bounds on x | ||
% x_min and x_max are only needed if doing plots | % x_min and x_max are only needed if doing plots | ||
x_min = [ 0 | x_min = [ 0 0 ]'; | ||
x_max = [10 10 ]'; | x_max = [10 10 ]'; | ||
% b_L, x_U and x_0 have default values and need not be defined. | % b_L, x_U and x_0 have default values and need not be defined. | ||
% It is possible to call lpAssign with empty | % It is possible to call lpAssign with empty [] arguments instead | ||
b_L = [-inf -inf]'; | |||
x_U = []; | x_U = []; | ||
x_0 = []; | x_0 = []; | ||
</ | </source> | ||
===A Quick Linear Programming Solution=== | |||
The quickest way to solve this problem is to define the following Matlab statements using the TOMLAB format: | The quickest way to solve this problem is to define the following Matlab statements using the TOMLAB format: | ||
Line 74: | Line 73: | ||
'''File: '''tomlab/usersguide/lpTest1.m | '''File: '''tomlab/usersguide/lpTest1.m | ||
< | <source lang="matlab"> | ||
lpExample; | lpExample; | ||
Prob = lpAssign(c, A, b_L, b_U, x_L, x_U, x_0, 'lpExample'); | Prob = lpAssign(c, A, b_L, b_U, x_L, x_U, x_0, 'lpExample'); | ||
Result = tomRun('lpSimplex', Prob, 1); | Result = tomRun('lpSimplex', Prob, 1); | ||
</ | </source> | ||
lpAssign is used to define the standard Prob structure, which TOMLAB always uses to store all information about a problem. The three last parameters could be left out. The upper bounds will default be Inf, and the problem name is only used in the printout in ''PrintResult ''to make the output nicer to read. If x 0, the initial value, is left out, an initial point is found by ''lpSimplex ''solving a feasible point (Phase I) linear programming problem. In this test the given x 0 is empty, so a Phase I problem must be solved. The solution of this problem gives the following output to the screen | lpAssign is used to define the standard Prob structure, which TOMLAB always uses to store all information about a problem. The three last parameters could be left out. The upper bounds will default be Inf, and the problem name is only used in the printout in ''PrintResult ''to make the output nicer to read. If x 0, the initial value, is left out, an initial point is found by ''lpSimplex ''solving a feasible point (Phase I) linear programming problem. In this test the given x 0 is empty, so a Phase I problem must be solved. The solution of this problem gives the following output to the screen | ||
Line 86: | Line 84: | ||
<pre> | <pre> | ||
===== | ===== * * * =================================================================== * * * | ||
TOMLAB /SOL + /CGO + /Xpress MEX + /CPLEX Parallel 2-CPU + 21 more - Tomlab Optimizat | TOMLAB /SOL + /CGO + /Xpress MEX + /CPLEX Parallel 2-CPU + 21 more - Tomlab Optimizat | ||
===================================================================================== | ===================================================================================== | ||
Problem: --- 1: lpExample f_k -26.571428571428569000 | Problem: --- 1: lpExample f_k -26.571428571428569000 | ||
Solver: lpSimplex. EXIT=0. | Solver: lpSimplex. EXIT=0. | ||
Simplex method. Minimum reduced cost. | Simplex method. Minimum reduced cost. | ||
Optimal | Optimal solution found | ||
FuncEv 3 Iter 3 | FuncEv 3 Iter 3 | ||
CPU | CPU time: 0.046800 sec. Elapsed time: 0.019000 sec. | ||
</pre> | </pre> | ||
Having defined the ''Prob ''structure is it easy to call any solver that can handle linear programming problems, | Having defined the ''Prob ''structure is it easy to call any solver that can handle linear programming problems, | ||
< | <source lang="matlab"> | ||
Result | Result = tomRun('qpSolve', Prob, 1); | ||
</ | </source> | ||
Even a nonlinear solver may be used. | Even a nonlinear solver may be used. | ||
< | <source lang="matlab"> | ||
Result | Result = tomRun('nlpSolve',Prob, 3); | ||
</ | </source> | ||
All TOMLAB solvers may either be called directly, or by using the driver routine ''tomRun'', as in this case. | All TOMLAB solvers may either be called directly, or by using the driver routine ''tomRun'', as in this case. | ||
==Quadratic Programming Problems== | |||
The general formulation in TOMLAB for a quadratic programming problem is | The general formulation in TOMLAB for a quadratic programming problem is | ||
Line 119: | Line 117: | ||
<math> | <math> | ||
\begin{array}{ll} | \begin{array}{ll} | ||
\min\limits_{x} & f(x) = \frac{1}{2} x^T F x + c^T x \\ | \min\limits_{x} & f(x) = \frac{1}{2} x^T F x + c^T x \\ | ||
Line 129: | Line 126: | ||
where <math> | where <math>c, x, x_L, x_U \in \mathbb{R}^n</math>, <math>F \in \mathbb{R}^{n \times n}</math>, <math>A \in \mathbb{R}^{m_1 \times n}</math>, and <math>b_L,b_U \in \mathbb{R}^{m_1}</math>. Equality constraints are defined by setting | ||
the lower bound equal to the upper bound, i.e. | the lower bound equal to the upper bound, i.e. | ||
for constraint <math> | for constraint <math>i</math>: | ||
<math> | <math>b_{L}(i) = b_{U}(i)</math>. | ||
<math> | <math>b_{L}(i) = b_{U}(i), \forall i \in E, where E</math> is the set of equalities. | ||
Fixed variables are handled the same way. | Fixed variables are handled the same way. | ||
Line 140: | Line 137: | ||
<math> | <math> | ||
\begin{array}{ll} | \begin{array}{ll} | ||
\min\limits_{x} & f(x)=4x_{1}^2+1x_{1}x_{2}+4x_{2}^2+3x_{1}-4x_{2} \\ | \min\limits_{x} & f(x)=4x_{1}^2+1x_{1}x_{2}+4x_{2}^2+3x_{1}-4x_{2} \\ | ||
Line 146: | Line 142: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
named ''QP Example''. The following statements define this problem in Matlab. | named ''QP Example''. The following statements define this problem in Matlab. | ||
Line 151: | Line 148: | ||
'''File: '''tomlab/usersguide/qpExample.m | '''File: '''tomlab/usersguide/qpExample.m | ||
< | <source lang="matlab"> | ||
Name = 'QP Example'; % File qpExample.m | Name = 'QP Example'; % File qpExample.m | ||
F = [ 8 1 % Matrix F in 1/2 * x' * F * x + c' * x | F = [ 8 1 % Matrix F in 1/2 * x' * F * x + c' * x | ||
Line 165: | Line 162: | ||
x_min = [-1 -1 ]; % Plot region lower bound parameters | x_min = [-1 -1 ]; % Plot region lower bound parameters | ||
x_max = [ 6 6 ]; % Plot region upper bound parameters | x_max = [ 6 6 ]; % Plot region upper bound parameters | ||
</ | </source> | ||
===A Quick Quadratic Programming solution=== | |||
The quickest way to solve this problem is to define the following Matlab statements using the TOMLAB format: | The quickest way to solve this problem is to define the following Matlab statements using the TOMLAB format: | ||
Line 173: | Line 170: | ||
'''File: '''tomlab/usersguide/qpTest1.m | '''File: '''tomlab/usersguide/qpTest1.m | ||
< | <source lang="matlab"> | ||
qpExample; | qpExample; | ||
Prob = qpAssign(F, c, A, b_L, b_U, x_L, x_U, x_0, 'qpExample'); | Prob = qpAssign(F, c, A, b_L, b_U, x_L, x_U, x_0, 'qpExample'); | ||
Result = tomRun('qpSolve', Prob, 1); | Result = tomRun('qpSolve', Prob, 1); | ||
</ | </source> | ||
The solution of this problem gives the following output to the screen. | The solution of this problem gives the following output to the screen. | ||
Line 192: | Line 187: | ||
Solver: qpSolve. EXIT=0. INFORM=1. | Solver: qpSolve. EXIT=0. INFORM=1. | ||
Active set | Active set strategy | ||
Optimal | Optimal point found | ||
First order | First order multipliers >= 0 | ||
Iter 4 | Iter 4 | ||
CPU | CPU time: 0.046800 sec. Elapsed time: 0.037000 sec. | ||
</pre> | </pre> | ||
qpAssign is used to define the standard Prob structure, which TOMLAB always uses to store all information about a problem. The three last parameters could be left out. The upper bounds will default be Inf, and the problem name is only used in the printout in ''PrintResult ''to make the output nicer to read. If | qpAssign is used to define the standard Prob structure, which TOMLAB always uses to store all information about a problem. The three last parameters could be left out. The upper bounds will default be Inf, and the problem name is only used in the printout in ''PrintResult ''to make the output nicer to read. If x_0, the initial value, is left out, a initial point is found by ''qpSolve ''solving a feasible point (Phase I) linear programming problem calling the TOMLAB ''lpSimplex ''solver. In fact, the output shows that the given ''x''<sub>0</sub> = (0, -1)<sup>''T''</sup> was rejected because it was infeasible, and instead a Phase I solution lead to the initial point ''x''<sub>0</sub> = (0, 0)<sup>''T''</sup>. | ||
TOMLAB ''lpSimplex ''solver. In fact, the output shows that the given ''x''0 = (0 | |||
==Mixed-Integer Programming Problems== | |||
This section describes how to solve mixed-integer programming problems efficiently using TOMLAB. To illustrate the solution of MIPs consider the simple knapsack 0/1 test problem ''Weingartner 1'', which has 28 binary variables and two knapsacks. The problem is defined | This section describes how to solve mixed-integer programming problems efficiently using TOMLAB. To illustrate the solution of MIPs consider the simple knapsack 0/1 test problem ''Weingartner 1'', which has 28 binary variables and two knapsacks. The problem is defined | ||
Line 210: | Line 203: | ||
<math> | <math> | ||
\begin{array}{ccccl} | \begin{array}{ccccl} | ||
\min\limits_{x} & c^T x \\ | \min\limits_{x} & c^T x \\ | ||
Line 220: | Line 212: | ||
where <math> | where <math>b=(600, 600)^T</math>, | ||
<math> | <math> | ||
Line 250: | Line 242: | ||
'''File: '''tomlab/usersguide/mipExample.m | '''File: '''tomlab/usersguide/mipExample.m | ||
< | <source lang="matlab"> | ||
Name='Weingartner 1 - 2/28 0-1 knapsack'; | Name='Weingartner 1 - 2/28 0-1 knapsack'; | ||
Line 256: | Line 248: | ||
A = [ 45 0 85 150 65 95 30 0 170 0 ... | A = [ 45 0 85 150 65 95 30 0 170 0 ... | ||
40 25 20 0 0 25 0 0 25 0 ... | 40 25 20 0 0 25 0 0 25 0 ... | ||
165 0 85 0 0 0 0 100 ; ... | 165 0 85 0 0 0 0 100 ; ... | ||
30 20 125 5 80 25 35 73 12 15 ... | 30 20 125 5 80 25 35 73 12 15 ... | ||
15 40 5 10 10 12 10 9 0 20 ... | 15 40 5 10 10 12 10 9 0 20 ... | ||
60 40 50 36 49 40 19 150]; | 60 40 50 36 49 40 19 150]; | ||
Line 294: | Line 281: | ||
b_L = b_U; | b_L = b_U; | ||
f_opt = -141278; | f_opt = -141278; | ||
</source> | |||
The quickest way to solve this problem is to define the following Matlab statements: | The quickest way to solve this problem is to define the following Matlab statements: | ||
Line 299: | Line 287: | ||
'''File: '''tomlab/usersguide/mipTest1.m | '''File: '''tomlab/usersguide/mipTest1.m | ||
< | <source lang="matlab"> | ||
mipExample; | mipExample; | ||
Line 374: | Line 362: | ||
Result = tomRun('mipSolve', Prob, 0); | Result = tomRun('mipSolve', Prob, 0); | ||
</ | </source> | ||
To make it easier to see all variable settings, the first lines define the needed variables. Several of them are just empty arrays, and could be directly set as empty in the call to ''mipAssign''. ''mipAssign ''is used to define the standard ''Prob ''structure, which TOMLAB always uses to store all information about a problem. After mipAssign has defined the structure ''Prob ''it is then easy to set or change fields in the structure. The solver ''mipSolve ''is using three different strategies to search the branch-and-bound tree. The default is the ''Depth first ''strategy, which is also the result if setting the field ''Solver.Alg ''as zero. Setting the field as one gives the ''Breadth first ''strategy and setting it as two gives the ''Depth first, then breadth search ''strategy. In the example our choice is the last strategy. The number of iterations might be many, thus the maximal number of iterations must be increased, the field ''optParam.MaxIter''. | To make it easier to see all variable settings, the first lines define the needed variables. Several of them are just empty arrays, and could be directly set as empty in the call to ''mipAssign''. ''mipAssign ''is used to define the standard ''Prob ''structure, which TOMLAB always uses to store all information about a problem. After mipAssign has defined the structure ''Prob ''it is then easy to set or change fields in the structure. The solver ''mipSolve ''is using three different strategies to search the branch-and-bound tree. The default is the ''Depth first ''strategy, which is also the result if setting the field ''Solver.Alg ''as zero. Setting the field as one gives the ''Breadth first ''strategy and setting it as two gives the ''Depth first, then breadth search ''strategy. In the example our choice is the last strategy. The number of iterations might be many, thus the maximal number of iterations must be increased, the field ''optParam.MaxIter''. |
Latest revision as of 14:07, 14 January 2012
This page is part of the TOMLAB Manual. See TOMLAB Manual. |
This section describes how to define and solve linear and quadratic programming problems, and mixed-integer linear programs using TOMLAB. Several examples are given on how to proceed, depending on if a quick solution is wanted, or more advanced tests are needed. TOMLAB is also compatible with MathWorks Optimization TB. See TOMLAB Appendix E for more information and test examples.
The test examples and output files are part of the standard distribution of TOMLAB, available in directory usersguide, and all tests can be run by the user. There is a file RunAllTests that goes through and runs all tests for this section.
Also see the files lpDemo.m, qpDemo.m, and mipDemo.m, in the directory examples, where in each file a set of simple examples are defined. The examples may be ran by giving the corresponding file name, which displays a menu, or by running the general TOMLAB help routine tomHelp.m.
Linear Programming Problems
The general formulation in TOMLAB for a linear programming problem is
where ,
, and .
Equality constraints are defined by setting
the lower bound equal to the upper bound, i.e.
for constraint .
To illustrate the solution of LPs consider the simple linear programming test problem
named LP Example.
The following statements define this problem in Matlab
File: tomlab/usersguide/lpExample.m
Name = 'lptest';
c = [-7 -5]'; % Coefficients in linear objective function
A = [ 1 2
4 1 ]; % Matrix defining linear constraints
b_U = [ 6 12 ]'; % Upper bounds on the linear inequalities
x_L = [ 0 0 ]'; % Lower bounds on x
% x_min and x_max are only needed if doing plots
x_min = [ 0 0 ]';
x_max = [10 10 ]';
% b_L, x_U and x_0 have default values and need not be defined.
% It is possible to call lpAssign with empty [] arguments instead
b_L = [-inf -inf]';
x_U = [];
x_0 = [];
A Quick Linear Programming Solution
The quickest way to solve this problem is to define the following Matlab statements using the TOMLAB format:
File: tomlab/usersguide/lpTest1.m
lpExample;
Prob = lpAssign(c, A, b_L, b_U, x_L, x_U, x_0, 'lpExample');
Result = tomRun('lpSimplex', Prob, 1);
lpAssign is used to define the standard Prob structure, which TOMLAB always uses to store all information about a problem. The three last parameters could be left out. The upper bounds will default be Inf, and the problem name is only used in the printout in PrintResult to make the output nicer to read. If x 0, the initial value, is left out, an initial point is found by lpSimplex solving a feasible point (Phase I) linear programming problem. In this test the given x 0 is empty, so a Phase I problem must be solved. The solution of this problem gives the following output to the screen
File: tomlab/usersguide/lpTest1.out
===== * * * =================================================================== * * * TOMLAB /SOL + /CGO + /Xpress MEX + /CPLEX Parallel 2-CPU + 21 more - Tomlab Optimizat ===================================================================================== Problem: --- 1: lpExample f_k -26.571428571428569000 Solver: lpSimplex. EXIT=0. Simplex method. Minimum reduced cost. Optimal solution found FuncEv 3 Iter 3 CPU time: 0.046800 sec. Elapsed time: 0.019000 sec.
Having defined the Prob structure is it easy to call any solver that can handle linear programming problems,
Result = tomRun('qpSolve', Prob, 1);
Even a nonlinear solver may be used.
Result = tomRun('nlpSolve',Prob, 3);
All TOMLAB solvers may either be called directly, or by using the driver routine tomRun, as in this case.
Quadratic Programming Problems
The general formulation in TOMLAB for a quadratic programming problem is
where , , , and . Equality constraints are defined by setting
the lower bound equal to the upper bound, i.e.
for constraint :
.
is the set of equalities.
Fixed variables are handled the same way.
To illustrate the solution of QPs consider the simple quadratic programming test problem
named QP Example. The following statements define this problem in Matlab.
File: tomlab/usersguide/qpExample.m
Name = 'QP Example'; % File qpExample.m
F = [ 8 1 % Matrix F in 1/2 * x' * F * x + c' * x
1 8 ];
c = [ 3 -4 ]'; % Vector c in 1/2 * x' * F * x + c' * x
A = [ 1 1 % Constraint matrix
1 -1 ];
b_L = [-inf 0 ]'; % Lower bounds on the linear constraints
b_U = [ 5 0 ]'; % Upper bounds on the linear constraints
x_L = [ 0 0 ]'; % Lower bounds on the variables
x_U = [ inf inf ]'; % Upper bounds on the variables
x_0 = [ 0 1 ]'; % Starting point
x_min = [-1 -1 ]; % Plot region lower bound parameters
x_max = [ 6 6 ]; % Plot region upper bound parameters
A Quick Quadratic Programming solution
The quickest way to solve this problem is to define the following Matlab statements using the TOMLAB format:
File: tomlab/usersguide/qpTest1.m
qpExample;
Prob = qpAssign(F, c, A, b_L, b_U, x_L, x_U, x_0, 'qpExample');
Result = tomRun('qpSolve', Prob, 1);
The solution of this problem gives the following output to the screen.
File: tomlab/usersguide/qpTest1.out
===== * * * =================================================================== * * * TOMLAB /SOL + /CGO + /Xpress MEX + /CPLEX Parallel 2-CPU + 21 more - Tomlab Optimizat ===================================================================================== Problem: --- 1: qpExample f_k -0.027777777777777790 Solver: qpSolve. EXIT=0. INFORM=1. Active set strategy Optimal point found First order multipliers >= 0 Iter 4 CPU time: 0.046800 sec. Elapsed time: 0.037000 sec.
qpAssign is used to define the standard Prob structure, which TOMLAB always uses to store all information about a problem. The three last parameters could be left out. The upper bounds will default be Inf, and the problem name is only used in the printout in PrintResult to make the output nicer to read. If x_0, the initial value, is left out, a initial point is found by qpSolve solving a feasible point (Phase I) linear programming problem calling the TOMLAB lpSimplex solver. In fact, the output shows that the given x0 = (0, -1)T was rejected because it was infeasible, and instead a Phase I solution lead to the initial point x0 = (0, 0)T.
Mixed-Integer Programming Problems
This section describes how to solve mixed-integer programming problems efficiently using TOMLAB. To illustrate the solution of MIPs consider the simple knapsack 0/1 test problem Weingartner 1, which has 28 binary variables and two knapsacks. The problem is defined
where ,
and the A matrix is
The following statements define this problem in Matlab using the TOMLAB format:
File: tomlab/usersguide/mipExample.m
Name='Weingartner 1 - 2/28 0-1 knapsack';
% Problem formulated as a minimum problem
A = [ 45 0 85 150 65 95 30 0 170 0 ...
40 25 20 0 0 25 0 0 25 0 ...
165 0 85 0 0 0 0 100 ; ...
30 20 125 5 80 25 35 73 12 15 ...
15 40 5 10 10 12 10 9 0 20 ...
60 40 50 36 49 40 19 150];
b_U = [600;600]; % 2 knapsack capacities
c = [1898 440 22507 270 14148 3100 4650 30800 615 4975 ...
1160 4225 510 11880 479 440 490 330 110 560 ...
24355 2885 11748 4550 750 3720 1950 10500]'; % 28 weights
% Make problem on standard form for mipSolve
[m,n] = size(A);
A = [A eye(m,m)];
c = [-c;zeros(m,1)]; % Change sign to make a minimum problem
[mm nn] = size(A);
x_L = zeros(nn,1);
x_U = [ones(n,1);b_U];
x_0 = [zeros(n,1);b_U];
fprintf('Knapsack problem. Variables %d. Knapsacks %d\n',n,m);
fprintf('Making standard form with %d variables\n',nn);
% All original variables should be integer, but also slacks in this case
IntVars = nn; % Could also be set as: IntVars=1:nn; or IntVars=ones(nn,1);
x_min = x_L;
x_max = x_U;
f_Low = -1E7; % f_Low <= f_optimal must hold
n = length(c);
b_L = b_U;
f_opt = -141278;
The quickest way to solve this problem is to define the following Matlab statements:
File: tomlab/usersguide/mipTest1.m
mipExample;
nProblem = 7; % Use the same problem number as in mip_prob.m
fIP = []; % Do not use any prior knowledge
xIP = []; % Do not use any prior knowledge
setupFile = []; % Just define the Prob structure, not any permanent setup file
x_opt = []; % The optimal integer solution is not known
VarWeight = []; % No variable priorities, largest fractional part will be used
KNAPSACK = 0; % First run without the knapsack heuristic
Prob = mipAssign(c, A, b_L, b_U, x_L, x_U, x_0, Name, setupFile, nProblem,...
IntVars, VarWeight, KNAPSACK, fIP, xIP, ... f_Low, x_min, x_max, f_opt, x_opt);
Prob.Solver.Alg = 2; % Depth First, then Breadth (Default Depth First)
Prob.optParam.MaxIter = 5000; % Must increase iterations from default 500
Prob.optParam.IterPrint = 0;
Prob.PriLev = 1;
Result = tomRun('mipSolve', Prob, 0);
% ------------------------------------------------
% Add priorities on the variables
% ------------------------------------------------
VarWeight = c;
% NOTE. Prob is already defined, could skip mipAssign, directly set:
% Prob.MIP.VarWeight=c;
Prob = mipAssign(c, A, b_L, b_U, x_L, x_U, x_0, Name, setupFile, nProblem,...
IntVars, VarWeight, KNAPSACK, fIP, xIP, ...
f_Low, x_min, x_max, f_opt, x_opt);
Prob.Solver.Alg = 2; % Depth First, then Breadth search
Prob.optParam.MaxIter = 5000; % Must increase number of iterations
Prob.optParam.IterPrint = 0;
Prob.PriLev = 1;
Result = tomRun('mipSolve', Prob, 0);
% ----------------------------------------------
% Use the knapsack heuristic, but not priorities
% ----------------------------------------------
KNAPSACK = 1; VarWeight = [];
% NOTE. Prob is already defined, could skip mipAssign, directly set:
% Prob.MIP.KNAPSACK=1;
% Prob.MIP.VarWeight=[];
Prob = mipAssign(c, A, b_L, b_U, x_L, x_U, x_0, Name, setupFile, ...
nProblem, IntVars, VarWeight, KNAPSACK, fIP, xIP, ...
f_Low, x_min, x_max, f_opt, x_opt);
Prob.Solver.Alg = 2; % Depth First, then Breadth search
Prob.optParam.IterPrint = 0;
Prob.PriLev = 1;
Result = tomRun('mipSolve', Prob, 0);
% --------------------------------------------------
% Now use both the knapsack heuristic and priorities
% --------------------------------------------------
VarWeight = c; KNAPSACK = 1;
% NOTE. Prob is already defined, could skip mipAssign, directly set:
% Prob.MIP.KNAPSACK=1;
% Prob.MIP.VarWeight=c;
Prob = mipAssign(c, A, b_L, b_U, x_L, x_U, x_0, Name, setupFile, nProblem,...
IntVars, VarWeight, KNAPSACK, fIP, xIP, ...
f_Low, x_min, x_max, f_opt, x_opt);
Prob.Solver.Alg = 2; % Depth First, then Breadth search
Prob.optParam.IterPrint = 0;
Prob.PriLev = 1;
Result = tomRun('mipSolve', Prob, 0);
To make it easier to see all variable settings, the first lines define the needed variables. Several of them are just empty arrays, and could be directly set as empty in the call to mipAssign. mipAssign is used to define the standard Prob structure, which TOMLAB always uses to store all information about a problem. After mipAssign has defined the structure Prob it is then easy to set or change fields in the structure. The solver mipSolve is using three different strategies to search the branch-and-bound tree. The default is the Depth first strategy, which is also the result if setting the field Solver.Alg as zero. Setting the field as one gives the Breadth first strategy and setting it as two gives the Depth first, then breadth search strategy. In the example our choice is the last strategy. The number of iterations might be many, thus the maximal number of iterations must be increased, the field optParam.MaxIter.
Tests show two ways to improve the convergence of MIP problems. One is to define a priority order in which the different non-integer variables are selected as variables to branch on. The field MIP.VarWeight is used to set priority numbers for each variable. Note that the lower the number, the higher the priority. In our test case the coefficients of the objective function is used as priority weights. The other way to improve convergence is to use a heuristic. For binary variables a simple knapsack heuristic is implemented in mipSolve. Setting the field MIP.KNAPSACK as true instructs mipSolve to use the heuristic.
Running the four different tests on the knapsack problem gives the following output to the screen
File: tomlab/usersguide/mipTest1.out
mipTest1 Knapsack problem. Variables 28. Knapsacks 2 Branch and bound. Depth First, then Breadth. --- Branch & Bound converged! Iterations (nodes visited) = 714 Total LP Iterations = 713 Optimal Objective function = -141278.0000000000000000 x: 0 0 1 -0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 0 B: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Branch & bound. Depth First, then Breadth. Priority weights. --- Branch & Bound converged! Iterations (nodes visited) = 470 Total LP Iterations = 469 Optimal Objective function = -141278.0000000000000000 x: 0 0 1 -0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 0 B: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Branch and bound. Depth First, then Breadth. Knapsack Heuristic. Found new BEST Knapsack. Nodes left 0. Nodes deleted 0. Best IP function value -139508.0000000000000000 Found new BEST Knapsack. Nodes left 1. Nodes deleted 0. Best IP function value -140768.0000000000000000 Found new BEST Knapsack. Nodes left 4. Nodes deleted 0. Best IP function value -141278.0000000000000000 --- Branch & Bound converged! Iterations (nodes visited) = 96 Total LP Iterations = 95 Optimal Objective function = -141278.0000000000000000 x: 0 0 1 -0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 0 B: 1 1 -1 1 -1 -1 -1 -1 1 -1 0 -1 -1 -1 1 1 1 1 -1 1 -1 0 -1 -1 1 -1 -1 1 Branch & bound. Depth First, then Breadth. Knapsack heuristic. Priority weights. Found new BEST Knapsack. Nodes left 0. Nodes deleted 0. Best IP function value -139508.0000000000000000 Found new BEST Knapsack. Nodes left 1. Nodes deleted 0. Best IP function value -140768.0000000000000000 Found new BEST Knapsack. Nodes left 4. Nodes deleted 0. Best IP function value -141278.0000000000000000 --- Branch & Bound converged! Iterations (nodes visited) = 94 Total LP Iterations = 93 Optimal Objective function = -141278.0000000000000000 x: 0 0 1 -0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 0 B: 1 1 -1 1 -1 -1 -1 -1 1 -1 0 -1 -1 -1 1 1 1 1 -1 1 -1 0 -1 -1 1 -1 -1 1 diary off
Note that there is a large difference in the number of iterations if the additional heuristic and priorities are used. Similar results are obtained if running the other two tree search strategies.