# 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

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