Adding a binary decision variable in a linear optimization problem

Hi everybody!

I have the following optimization problem that is related to recycling of plastic waste:

1) There are three plastic waste collection points with different recycling demands per year:

P_CP = [1500,1000,200]; % [t/yr] Recycling Demand

2) There are two recycling stations with two different recycling capacities per year (1000 or 2000 t/yr):

C_RS = [1000,2000,1000,2000]; % [t/yr] Recycling Capacity

3) Due to the fact that the two recycling stations have two different capacity levels, but are at the same location, the column 1,2 and 3,4 in the transport cost matrix are the same:

k_TC = [1,1,2,2; % [$/yr] Transport Costs

2,2,4,4;

4,4,3,3];

The MATLAB code for the linear optimization problem is given below:

%% Cleanup
clear;close all;clc;

%% Define Problem
% Transport Costs
k_TC = [1,1,2,2;
        2,2,4,4;
        4,4,3,3];

% Collection Points
P_CP = [1500,1000,200]; % Recycling Demand

% Recycling Stations
C_RS = [1000,2000,1000,2000]; % Recycling Capacity

%% Form the LPP (Linear Programming Problem)
N_CP = size(k_TC,1); % Number of Collection Points
N_RS = size(k_TC,2); % Number of Recycling Stations
N_x = numel(k_TC); % Number of Decision Variables

% Index Converter
ind = @(i,j) sub2ind(size(k_TC),i,j);

% Objective Function
f = k_TC(:);

% Preallocate A, b
A = zeros(N_RS,N_x);
b = zeros(N_RS,1);

c = 0; % Initialize Counter
% Nonlinear Constraints for Recycling Capacities
for j = 1:N_RS
    c = c+1;
    for i = 1:N_CP
        A(c,ind(i,j)) = 1;
    end
    b(c,1) = C_RS(j);
end

% Preallocate Aeq, beq
Aeq = zeros(N_CP,N_x);
beq = zeros(N_CP,1);

c = 0; % Initialize Counter
% Linear Constraints for Recycling Demands
for i = 1:N_CP
    c = c+1;
    for j = 1:N_RS
        Aeq(c,ind(i,j)) = 1;
    end
    beq(c,1) = P_CP(i);
end

% Bounds
lb = zeros(N_x,1);
ub = [];

%% Sove the LPP
[x_opt,f_val] = linprog(f,A,b,Aeq,beq,lb,ub);

Optimal solution found.

x_opt = reshape(x_opt,size(k_TC))

x_opt = 3×4

500 1000 0 0 0 1000 0 0 0 0 0 200

As the result shows, for the first recycling station, both capacity levels are used.

One possibility would be to run the optimization problem 2^2 times for every combination of recycling capacities. However, if this problem is scaled up to 10 different capacity levels and 500 possible recycling stations, the number of combinations explodes.

Therefore, my question is how to include additional binary decision variables that allow just the use of one capacity level for each recycling station.

Thank you very much for your help!

Answer 1

[John D'Errico]

linprog CANNOT be used with integer (binary) variables.

However, there is intlinprog, which is explicitly designed to handle exactly that problem.

help intlinprog

 INTLINPROG Mixed integer linear programming.
 
    X = INTLINPROG(f,intcon,A,b) attempts to solve problems of the form
 
             min f'*x    subject to:  A*x  <= b
              x                       Aeq*x = beq
                                      lb <= x <= ub
                                      x(i) integer, where i is in the index
                                      vector intcon (integer constraints)
 
    X = INTLINPROG(f,intcon,A,b) solves the problem with integer variables
    in the intcon vector and linear inequality constraints A*x <= b. intcon
    is a vector of positive integers indicating components of the solution
    X that must be integers. For example, if you want to constrain X(2) and
    X(10) to be integers, set intcon to [2,10].
 
    X = INTLINPROG(f,intcon,A,b,Aeq,beq) solves the problem above while
    additionally satisfying the equality constraints Aeq*x = beq. (Set A=[]
    and b=[] if no inequalities exist.)
 
    X = INTLINPROG(f,intcon,A,b,Aeq,beq,LB,UB) defines a set of lower and
    upper bounds on the design variables, X, so that the solution is in the
    range LB <= X <= UB. Use empty matrices for LB and UB if no bounds
    exist. Set LB(i) = -Inf if X(i) is unbounded below; set UB(i) = Inf if
    X(i) is unbounded above.
 
    X = INTLINPROG(f,intcon,A,b,Aeq,beq,LB,UB,X0) sets the initial point
    to X0.
 
    X = INTLINPROG(f,intcon,A,b,Aeq,beq,LB,UB,X0,OPTIONS) minimizes with
    the default optimization parameters replaced by values in OPTIONS, an
    argument created with the OPTIMOPTIONS function. See OPTIMOPTIONS for
    details.
 
    X = INTLINPROG(PROBLEM) finds the minimum for PROBLEM. PROBLEM is a
    structure with the vector 'f' in PROBLEM.f, the integer constraints in
    PROBLEM.intcon, the linear inequality constraints in PROBLEM.Aineq and
    PROBLEM.bineq, the linear equality constraints in PROBLEM.Aeq and
    PROBLEM.beq, the lower bounds in PROBLEM.lb, the upper bounds in
    PROBLEM.ub, the initial point in PROBLEM.x0, the options structure in
    PROBLEM.options, and solver name 'intlinprog' in PROBLEM.solver.
 
    [X,FVAL] = INTLINPROG(f,intcon,A,b,...) returns the value of the
    objective function at X: FVAL = f'*X.
 
    [X,FVAL,EXITFLAG] = INTLINPROG(f,intcon,A,b,...) returns an EXITFLAG
    that describes the exit condition. Possible values of EXITFLAG and the
    corresponding exit conditions are
 
      3  Optimal solution found with poor constraint feasibility.
      2  Solver stopped prematurely. Integer feasible point found.
      1  Optimal solution found.
      0  Solver stopped prematurely. No integer feasible point found.
     -1  Solver stopped by an output function or plot function.
     -2  No feasible point found.
     -3  Root LP problem is unbounded.
     -9  Solver lost feasibility probably due to ill-conditioned matrix.
 
    [X,FVAL,EXITFLAG,OUTPUT] = INTLINPROG(f,A,b,...) returns a structure
    OUTPUT containing information about the optimization process. OUTPUT
    includes the number of integer feasible points found and the final gap
    between internally calculated bounds on the solution. See the
    documentation for a complete description.
 
    See also LINPROG.

    Documentation for intlinprog
       doc intlinprog

A binary variable is just an integer variable, where the lower and upper bounds are 0 and 1.

[Evenpolar]

Thank you for your hint!

I finally made it work.

[John D'Errico]

inlinprog cannot solve nonlinear problems. It is still LINEAR programming. For that matter, linprog CANNOT handle nonlinear constraints either.

However, if you have only 4 binary variables, then one simple optino is to just solve the problem 16 times, once for each possible set of the binary variables. Then choose the best result. Now you can use other tools, like fmincon, or GA to handle the nonlinear constrints.

[Evenpolar]

Thank you for your comment.

As mentioned in the question, I plan to extend the problem to 10 different capacity levels and 500 possible recycling stations. Therefore, it is no option for me to use the concept with solving 500^10 different initial settings.

But it works now, so everything is fine and I can continue my work :)