Quickguide MILP Problem: Difference between revisions
(Created page with "The general formulation in TOMLAB for a mixed-integer linear programming problem is: <math> \begin{array}{ll} \min\limits_{x} & f(x) = c^T x \\ & \\ s/t & \begin{array}{lcccl} ...") |
No edit summary |
||
Line 1: | Line 1: | ||
{{Part Of Manual|title=the Quickguide Manual|link=[[Quickguide|Quickguide]]}} | |||
The general formulation in TOMLAB for a mixed-integer linear programming problem is: | The general formulation in TOMLAB for a mixed-integer linear programming problem is: | ||
Revision as of 10:08, 9 August 2011
This page is part of the Quickguide Manual. See Quickguide. |
The general formulation in TOMLAB for a mixed-integer linear programming problem is:
Failed to parse (unknown function "\MATHSET"): {\displaystyle \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}, ~x_{j} \in \MATHSET{N}\ ~~\forall j \in $I$ \\ \end{array} \end{array} }
where Failed to parse (unknown function "\MATHSET"): {\displaystyle c, x, x_L, x_U \in \MATHSET{R}^n} , Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \in \MATHSET{R}^{m_1 \times n}} , and Failed to parse (unknown function "\MATHSET"): {\displaystyle b_L,b_U \in \MATHSET{R}^{m_1}} . The variables , the index subset of are restricted to be integers. Equality constraints are defined by setting the lower bound equal to the upper bound, i.e. for constraint : .
Mixed-integer linear problems are defined in the same manner as linear problems. However, the user can give a wider range of inputs to the assign routine and solvers. See 'help mipAssign' for more information. In TOMLAB integers can be identified by a 0-1 vector.
The following example illustrates how to solve a MILP problem using the TOMLAB format.
File: tomlab/quickguide/mipQG.m
Open the file for viewing, and execute mipQG in 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);
IntVars = [1:n]; % All original variables should be integer
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);