Quickguide Binary Selection Problems

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);