TOMLAB Solving Linear Quadratic and Integer Programming Problems

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

${\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 &Ax&\leq &b_{U}\\\end{array}}\end{array}}$

where $c,x,x_{L},x_{U}\in \mathbb {R} ^{n}$, $A\in \mathbb {R} ^{m_{1}\times n}$, and $b_{L},b_{U}\in \mathbb {R} ^{m_{1}}$. Equality constraints are defined by setting the lower bound equal to the upper bound, i.e. for constraint $i:b_{L}(i)=b_{U}(i)$.

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

${\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}}$

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

${\begin{array}{ll}\min \limits _{x}&f(x)={\frac {1}{2}}x^{T}Fx+c^{T}x\\&\\s/t&{\begin{array}{lcccl}x_{L}&\leq &x&\leq &x_{U},\\b_{L}&\leq &Ax&\leq &b_{U}\\\end{array}}\end{array}}$

where $c,x,x_{L},x_{U}\in \mathbb {R} ^{n}$, $F\in \mathbb {R} ^{n\times n}$, $A\in \mathbb {R} ^{m_{1}\times n}$, and $b_{L},b_{U}\in \mathbb {R} ^{m_{1}}$. Equality constraints are defined by setting the lower bound equal to the upper bound, i.e. for constraint $i$: $b_{L}(i)=b_{U}(i)$. $b_{L}(i)=b_{U}(i),\forall i\in E,whereE$ 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

${\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}}$

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 x₀ = (0, -1)^T was rejected because it was infeasible, and instead a Phase I solution lead to the initial point x₀ = (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

${\begin{array}{ccccl}\min \limits _{x}&c^{T}x\\&\\s/t&{\begin{array}{lcccl}0&\leq &x&\leq &1,\\&&Ax&=&b,\\\end{array}}\end{array}}$

where $b=(600,600)^{T}$,

${\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}}$

and the A matrix is

$\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)$

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.