Welcome!

In this tutorial I’ll formulate linear integer programming models involving Binary or 0-1

variables.

Binary variables are employed when there is a yes or no situation.

That is, to indicate whether a selection is made or not.

For example, suppose we have 4 different projects to consider.

We can either select a project, or not select it.

So for the first project we can define the decision variable as follows:

X1 = 1 if project 1 is selected, and 0 if not selected.

We do the same for projects 2, 3, and 4 by defining X2, X3, and X4.

Or we can simply write Xi = 1 if project i is selected, and 0 if

not selected.

where i = 1, 2, 3, and 4.

Now, suppose each project has the same lifespan of 3 months (January to March), with corresponding

outlays or costs (in thousands of dollars) shown here.

Suppose these are the funds available for selected projects each month, and these are

the net returns (in thousand dollars) from each project.

In this case, our objective is to maximize return which is

217X1 + 125X2 + 88X3 + 109X4.

Since project outlays are constrained by available funds, we write (for January)

58X1+ 44X2+ 26X3+ 23X4 ≤ 120 We do the same for February, and for March.

And then complete the model by stating that the decision variables must be binary.

Upon solving this model using software like LINDO or Excel Solver, we find that the optimal

solution is X1 = 1, X2 = 0, X3 =1, and X4 = 1 with a corresponding

net return on 414.

That is, to maximize net return, undertake projects 1, 3 and 4 only.

Let’s now model a fixed cost problem.

Suppose a small company receives an order to supply 1000 units of a product.

The company has 3 machines that can be used to produce the product.

Here are the variable costs per unit produced from each machine, here are the fixed costs,

and here are the machines’ capacities.

Our objective is to minimize total costs.

We’re going to need 2 types of decision variables in this case.

One set for the number of units produced from each machine, and because of the fixed costs,

another to indicate whether a machine is being used or not.

So for units produced we write Xi = number of units produced on machine i

(i = 1, 2, 3) That is, X1 represents units produced on machine

1, X2 for machine 2 and X3 for machine 3.

Now because fixed costs indicate that the entire cost will be incurred if the corresponding

machine is used to produce at all, we define another set of variables.

For machine 1 we can write Y1 = 1 if machine 1 is used, 0 otherwise.

That is, if X1 > 0, Y1 = 1, otherwise Y1 = 0.

For all 3 machines we write Yi = 1 if machine i is used, 0 otherwise …

So for the objective function, which is to minimize total costs, we write

Minimize 2.39X1 + 1.99X2+ 2.99X3 + 300Y1+250Y2+ 400Y3

That is, we multiply variable costs by units produced

and multiply the fixed costs by the corresponding 0-1 variables.

When Y1 = 1 here, for example, it means that machine 1 is used and the fixed cost of 300

will be incurred.

And when Y1 = 0, machine 1 is not used, so the fixed cost of 300 will not be incurred.

For the constraints, we have an order here to supply 1000 units.

So we write X1+X2+X3 = 1000

Equality is used here because we have to meet the order or demand placed by the customer.

Now, for the capacities.

Normally we just write X1 ≤ 400, X2 ≤ 550, and X3 ≤ 600

Note that this X1 ≤ 400 constraint simply states that we can produce up to 400 units

on machine 1.

But if the machine is not used at all, this won’t be possible.

So whenever we have fixed costs associated with minimum requirements or maximum capacities,

we usually multiply the capacity by the corresponding binary variable.

So the correct format is X1 ≤ 400Y1.

That is, when Y1 = 1, we can produce up to 400 on machine 1, and when Y1 = 0, 0 units

should be produced.

We do the same for machine 2, and for machine 3.

We can then move the variables to the left side of the constraints.

And state that Xis should be non-negative, and the Yis binary.

On solving this model, we obtain X1 = 0, X2 = 550, X3 = 450

and for the binary variables Y1 = 0, Y2 = 1, and Y3 = 1.

Showing that only machines 2 and 3 should be used.

And that completes the fixed cost problem.

In the next video, I’ll be showing how to formulate some relational constraints using

binary variables, including multiple choice, mutually exclusive, co-requisite, and conditional

constraints.

Thanks for watching.