Models Mixed-Integer Linear Programming Problems: mip prob

This page is part of TOMLAB Models. See TOMLAB Models.

In mip_prob there are 47 mixed-integer linear test problems with sizes to nearly 1100 variables and nearly 1200 constraints. In order to define the problem n and solve it execute the following in Matlab:

Prob	= probInit('mip_prob',n); 
Result  = tomRun('',Prob);

An example of a problem of this class, (that is also found in the TOMLAB quickguide) is mipQG:

${\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},~x_{j}\in \mathbb {N} \ ~~\forall j\in \$I\$\\\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}}$. The variables $x\in I$, the index subset of $1,...,n$ are restricted to be integers.

File: tomlab/quickguide/mipQG.m

<syntaxhighlight lang="matlab">% mipQG is a small example problem for defining and solving % mixed-integer linear programming problems using the TOMLAB format.

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); c = -c; % Change sign to make a minimum problem x_L = zeros(n,1); x_U = ones(n,1); x_0 = zeros(n,1);

fprintf('Knapsack problem. Variables %d. Knapsacks %d\n',n,m);

% All original variables should be integer IntVars = n; % Could also be set as: IntVars=1:n; or IntVars=ones(n,1); x_min = x_L; x_max = x_U; f_Low = -1E7;  % f_Low <= f_optimal must hold b_L = -inf*ones(2,1); f_opt = -141278;

nProblem = []; % Problem number not used 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 = 1;  % Run with the knapsack heuristic

% Assign routine for defining a MIP problem. 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.optParam.IterPrint = 0;  % Set to 1 to see iterations. Prob.Solver.Alg = 2; % Depth First, then Breadth search

% Calling driver routine tomRun to run the solver. % The 1 sets the print level after optimization.

Result = tomRun(’mipSolve’, Prob, 1); %Result = tomRun(’cplex’, Prob, 1); %Result = tomRun(’xpress-mp’, Prob, 1); %Result = tomRun(’miqpBB’, Prob, 1); %Result = tomRun(’minlpBB’, Prob, 1);