View source for TOMLAB Solving Linear Quadratic and Integer Programming Problems

[[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.

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


<math>
\begin{array}{ll}
\min\limits_{x} & f(x) = c^T x \\
&  \\
s/t & \begin{array}{lcccl}
x_{L} & \leq  & x    & \leq & x_{U}, \\
b_{L} & \leq  & A x  & \leq & b_{U} \\
\end{array}
\end{array}
</math>


where <math>c, x, x_L, x_U \in \mathbb{R}^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.
for constraint <math>i: b_{L}(i) =  b_{U}(i)</math>.

To illustrate the solution of LPs consider the simple linear programming test problem


<math>
\begin{array}{ccccl}
\min\limits_{x_{1},x_{2}} & f(x_{1},x_{2}) & = & -7x_{1}-5x_{2} &  
\\s/t &  x_{1}  + 2x_{2}  & \leq  &   6  &  \\    & 4x_{1} +   x_{2}  & \leq  &  12  &  \\    &  x_{1},x_{2}      & \geq  &   0  &
\end{array}
</math>


named ''LP Example''.

The following statements define this problem in Matlab

'''File: '''tomlab/usersguide/lpExample.m

<source lang="matlab">
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	= [];
</source>

===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

<source lang="matlab">
lpExample;
Prob	= lpAssign(c, A,  b_L,  b_U, x_L,  x_U, x_0,  'lpExample'); 
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

'''File: '''tomlab/usersguide/lpTest1.out

<pre>
===== * * * =================================================================== * * * 
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.
</pre>

Having defined the ''Prob ''structure is it easy to call any solver that can handle linear programming problems,

<source lang="matlab">
Result = tomRun('qpSolve', Prob, 1); 
</source>

Even a nonlinear solver may be used. 

<source lang="matlab">
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.

==Quadratic  Programming  Problems==

The general formulation in TOMLAB  for a quadratic programming problem is


<math>
\begin{array}{ll}
\min\limits_{x} & f(x) = \frac{1}{2} x^T F x + c^T x \\
&  \\
s/t & \begin{array}{lcccl} x_{L} & \leq  & x    & \leq & x_{U}, \\ b_{L} & \leq  & A x  & \leq & b_{U} \\
\end{array}
\end{array}
</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.
for constraint <math>i</math>:
<math>b_{L}(i) =  b_{U}(i)</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.

To illustrate the solution of QPs consider the simple quadratic programming test problem


<math>
\begin{array}{ll}
\min\limits_{x} & f(x)=4x_{1}^2+1x_{1}x_{2}+4x_{2}^2+3x_{1}-4x_{2} \\
s/t             & x_{1}+x_{2} \leq 5 \\& x_{1}-x_{2}   =  0 \\& x_{1} \geq 0 \\& x_{2} \geq 0, \\
\end{array}
</math>


named ''QP Example''. The following statements define this problem in Matlab.

'''File: '''tomlab/usersguide/qpExample.m

<source lang="matlab">
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
</source>

===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

<source lang="matlab">
qpExample;
Prob = qpAssign(F, c,  A,  b_L,  b_U, x_L,  x_U, x_0,  'qpExample');
Result  = tomRun('qpSolve', Prob,  1);
</source>

The solution of this problem gives the following output to the screen.

'''File: '''tomlab/usersguide/qpTest1.out

<pre>
===== * * * ===================================================================  * * * 
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.
</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 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>.

==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


<math>
\begin{array}{ccccl}
\min\limits_{x} & c^T x \\
&  \\
s/t & \begin{array}{lcccl} 0& \leq  & x    & \leq & 1, \\ &       & A x  & = & b, \\
\end{array}
\end{array}
</math>


where <math>b=(600, 600)^T</math>,

<math>
\begin{array}{rccccccccccccccl}
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&)^T
\end{array}
</math>

and the A matrix is

<math>
\left(
\begin{array}{cccccccccccccccccccc}
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\\
\end{array}
\right)
</math>


The following statements define this problem in Matlab using the TOMLAB  format:

'''File: '''tomlab/usersguide/mipExample.m

<source lang="matlab">
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;
</source>

The quickest way to solve this problem is to define the following Matlab statements:

'''File: '''tomlab/usersguide/mipTest1.m

<source lang="matlab">
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);
</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''.

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

<pre>
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
</pre>

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.