Quickguide Binary Selection Problems
From TomWiki
Jump to navigationJump to search
This page is part of the Quickguide Manual. See Quickguide. |
The general formulation in TOMLAB for a binary selection problem (i.e. a problem that has binary variable products with other binary/interger/continuous variables) is:
The following files define two test cases in TOMLAB. The first case is a binary programming problem with binary combinations only. The second case has continuous variables (possible to replace by integers if needed) of which a subset are to be selected by enforcing a constraint on the binary variables.
File: tomlab/quickguide/binbinQG.m
Open the file for viewing, and execute binbinQG in Matlab.
% binbinQG is a small example problem for defining and solving
% combinatorial binary programming problems using the TOMLAB format.
Name = 'binbinQG';
% The first 4 are for binary variables:
% b1 b2 b3 b4
% The rest are the combinations:
% b1*b2, b1*b3, b1*b4, b2*b3, b2*b4, b3*b4
% Coefficients in linear objective function
c = [zeros(1,4) 1 2 3 2 4 3]';
% At least 3 binary variables are active
A = [1 1 1 1 0 0 0 0 0 0];
b_U = inf;
b_L = 3;
x_L = zeros(10,1);
x_U = ones(10,1);
IntVars = ones(10,1);
Prob = mipAssign(c, A, b_L, b_U, x_L, x_U, [], Name, [], [], IntVars);
% Give the indices for the combinations and variables combined
Prob = binbin2lin(Prob, (5:10)', [1;1;1;2;2;3], [2;3;4;3;4;4]);
Result = tomRun('cplex', Prob, 1);
File: tomlab/quickguide/bincontQG.m
Open the file for viewing, and execute bincontQG in Matlab.
% bincontQG is a small example problem for defining and solving
% where a subset of the continuous variables are active.
Name = 'bincontQG';
% The first n are for binary variables:
% b1 ... bn
%
% Variables n+1 to 2*n are continuous:
% c1 ... cn
%
% Variables 2*n+1 to 3*n are combinations:
% b1*c1 ... bn*cn
% Coefficients in linear objective function
n = 20;
cov1 = magic(20)/100;
cov1 = cov1(:,1);
F = [zeros(2*n,3*n); zeros(n,2*n), diag(cov1)];
c = zeros(3*n,1);
% 10 variables to be selected
% Combined combinations greater than 1000
A = [ones(1,n), zeros(1,2*n);
zeros(1,2*n), ones(1,n)];
b_U = [10;inf];
b_L = [10;1000];
x_L = zeros(3*n,1);
x_U = [ones(n,1); 1e4*ones(2*n,1)];
IntVars = [ones(n,1); zeros(2*n,1)];
Prob = miqpAssign(F, c, A, b_L, b_U, x_L, x_U, [], IntVars);
% Give the indices for the combinations and variables combined
Prob = bincont2lin(Prob, (2*n+1:3*n)', (1:n)', (n+1:2*n)');
Result = tomRun('cplex', Prob, 1);