Quantitative

Chapter 11 Integer Linear Programming

Introduction

Everything remains the same as the linear programming problems that we have seen in the previous chapters, except that in the integer linear programming, all or part of the decision variables x1, x2, ... must be integers. (In the previous chapters x1, x2,... may be fractional numbers.)

Types of Integer Linear Programming Models

1. All-integer Linear Program

All decision variables x1, x2,... must be integer.

2. Mixed-integer Linear Program

Some, not all, of the variables are integers. Some may be fractional number.

3. 0-1 (binary) Integer Linear Program

Some variables must be either 0 or 1.

Examples

1. All-integer LP

Max 2x1 + 3x2

s.t.

3x1 + 3x2 ≤12

(2/3) x1 + 1x2 ≤ 4

1x1 + 2x2 ≤ 6

x1, x2 ≥ 0 and integer

2. All-integer LP

Eastborne Realty has $2 million to buy new rental property. They can buy townhouses. There are 5 townhouses on the market, each costs $282,000. Or they can buy apartments each at $400,000 for as many as they want.

Eastborne’s manager can work to 140 hours a month. Each townhouse needs 4 hours a month of his time and each apartment needs 40 hours of his time.

The cash flow is estimated to be $10 thousand per townhouse and $15 thousand per apartment.

Question: how many apartments and townhouses should Eastborne buy to maximize the profit?

Since no one can buy 0.3 apartment or 0.2 townhouse, this is an all-integer LP.

We set up the model as follows.

T = number of townhouse,

A = number of apartment buildings

Max: 10T + 15A

s.t. 282T + 400A ≤ 2000 (money available = $2M = $2000 thousands)

4T + 40A ≤ 140 (manager’s time available in hours)

T ≤ 5 (townhouses available)

The text book has a graphical solution on p.473.

Using Management Scientist we get the solution below.

3. 0-1 Integer LP

Ice-cold Refrigerator Company is thinking about...