Integer programming in operations research

4 апреля 2019 г

Agenda

New meaning of the IP abbreviation
Prototype example
Some binary integer programming applications
Innovative uses of binary variables
Perspectives on solving IP problems
The branch-and-bound technique
Practical continue with the example
Continuous variables example

Integer programming definition

In many practical problems, the decision variables make sense only if they have integer values: people, machines, vehicles, yes/no questions.

If required integer values is the only way in which a problem deviates from a linear programming formulation, then it is a integer programming (IP) problem.

If only some of the variables are required to have integer values, this model is referred to as mixed integer programmming (MIP).

IP problems that contain only binary variables are called binary integer programming (BIP).

Prototype example: California Management Co.

Build a new factory in either LA or SF, or in both cities.
Build at most one new warehouse (in a city with a new factory).
Total capital available is $10 mln.
The objective is to maximize the total net present value.

Decision	Question	Variable	Net Present Value	Capital Required
1	Factory in LA?	x₁	$9 mln	$6 mln
2	Factory in SF?	x₂	$5 mln	$3 mln
3	Warehouse in LA?	x₃	$6 mln	$5 mln
4	Warehouse in SF?	x₄	$4 mln	$2 mln

Some BIP applications

Investment analysis

South African National Defense Force: to upgrade its capabilities with a smaller budget. A mixed BIP model to maximize the overall effectiveness. 16,000 variables (256 binary), 5,000 constraints. Savings of $1.1 bln per year.

Grantham, Mayo, Van Otterloo and Company: a mixed BIP model to construct many quantitatively managed portfolios (>$9 bln). Each portfolio to be close to target portfolio (sector and security exposure) but with a smaller number of distinct stocks (to reduce transaction costs). A binary - to include a stock or not. Then a separate continuous - the amount of the stock. Annual savings $4 mln.

Midwest Independent Transmission System Operator, Inc: 13 states, 40 mln customers, 60,000 miles of lines, 146,000 Mwatts. Mixed BIP to minimize the total cost. Each binary - a particular power plant should be on during specific period. Then a linear programming model: electricity output levels and prices. 3.3 mln continuous variables, 0.45 mln binaries, 3.9 mln constraints (+ Lagrangian relaxation). $2.5 bln savings over 4 years.

Site selection

AT&T: help their customers select the sites for telemarketing centers with minimizing labor, communications, real estate costs while providing the desired level of coverage.

Norske Skog: select sites to close facilities. A BIP model (312 binaries, 47,000 continuous variables, 2600 constraints). Two papers mills and a paper machine were closed, saving $100 mln annually.

Dispatching shipments

A certain route.
A certain size of truck.
A certain time period for the departure.

Petrobus transports 1,900 employees daily between 80 off-shore oil platforms and four mainland bases with 40 helicopters. A BIP model to generate helicopter routes and schedules. Annual savings >$20 mln.

Scheduling interrelated activities

Should a certain activity begin in a certain time period?

Swedish municipalities: plan stuff scheduling and routing 4,000 home care workers to attend to the needs of the elderly. BIP model saved $30 mln - $45 mln annually.

Airline applications

Fleet assignment problem: should a certain type of airplane be assigned to a certain flight leg?
Crew scheduling problem: should a certain sequence of flight legs be assigned to a crew.

Innovative uses of binary variables (!)

Auxiliary [UK - /ɔːkˈsɪli.əɹi/,US - /ɔɡˈzɪljəɹi/] binary variables.

Either-Or constraints (a very large positive)
K out of N constraints must hold
Functions with N possible values
The fixed-charge problem (the setup cost)
Binary representation of general integers

Some perspectives on solving IP problems

Is IP easier than linear programming?

far fewer solutions to be considered in IP;
finite number of feasible solutions.

But:

exponential growth of the difficulty (number of solutions).
Don’t be relaxed with linear programming relaxation!

Linear programming relaxation

The branch-and-bound technique

Branching.
Bounding.
Fathoming.

Our tree

Let’s solve the example

… with R!

library(ROI) # The R Optimization Infrastructure
library(ROI.plugin.glpk) # GNU linear programming kit
library(ompr) # MIP in algebraic way
library(ompr.roi)

# California Management Co.
net <- c(9, 5, 6, 4)
capital <- c(6, 3, 5, 2)

Define the model

caman_model <- MIPModel() %>% 
  # Define four decision variables
  add_variable(x[i], i = 1:4, type = "binary") %>% 
  # Define aim to maximize net profit
  set_objective(sum_expr(x[i] * net[i], i = 1:4), "max") %>%
  # Set constraint in maximal capital spent
  add_constraint(sum_expr(x[i] * capital[i], i = 1:4) <= 10) %>% 
  # Mutually exclusive alternatives: zero or one warehouse
  add_constraint(x[3] + x[4] <= 1) %>%
  # Contingent decisons: 
  #   1. Warehouse in LA if factory in LA
  add_constraint(x[3] - x[1] <= 0) %>% 
  #   2. Warehouse in SF if factory in SF
  add_constraint(x[4] - x[2] <= 0)

What is inside?

caman_model

## Mixed integer linear optimization problem
## Variables:
##   Continuous: 0 
##   Integer: 0 
##   Binary: 4 
## Model sense: maximize 
## Constraints: 4

Solving

solution <- solve_model(caman_model, 
                        with_ROI(solver = "glpk",
                                 verbose = TRUE))

## <SOLVER MSG>  ----
## GLPK Simplex Optimizer, v4.65
## 4 rows, 4 columns, 10 non-zeros
## *     0: obj =  -0.000000000e+00 inf =   0.000e+00 (4)
## *     5: obj =   1.650000000e+01 inf =   0.000e+00 (0)
## OPTIMAL LP SOLUTION FOUND
## GLPK Integer Optimizer, v4.65
## 4 rows, 4 columns, 10 non-zeros
## 4 integer variables, all of which are binary
## Integer optimization begins...
## Long-step dual simplex will be used
## +     5: mip =     not found yet <=              +inf        (1; 0)
## +     8: >>>>>   1.400000000e+01 <=   1.500000000e+01   7.1% (2; 0)
## +     8: mip =   1.400000000e+01 <=     tree is empty   0.0% (0; 3)
## INTEGER OPTIMAL SOLUTION FOUND
## <!SOLVER MSG> ----

Solution

get_solution(solution, x[i])

##   variable i value
## 1        x 1     1
## 2        x 2     1
## 3        x 3     0
## 4        x 4     0

It matches the book’s one! 8-0

Continuous variables example: Good Products Company

Three possible new products.
At most two should be chosen.
Just one of two plants should be chosen for all new products.
Maximize total profit.

Just cell!	Product 1	Product 2	Product 3	Production time available
Plant 1, hours	3	4	2	30
Plant 2, hours	4	6	2	40
Unit profit	5	7	3
Sales potential	7	5	9

Model

profit <- c(5, 7, 3)
M <- 10^5 # A very large positive
goodproducts <- MIPModel() %>% 
  add_variable(x[i], i = 1:3, type = "continuous", lb = 0) %>% 
  add_variable(y[j], j = 1:4, type = "binary") %>% 
  set_objective(sum_expr(x[i] * profit[i], i = 1:3), "max") %>% 
  add_constraint(x[1] <= 7) %>% 
  add_constraint(x[2] <= 5) %>% 
  add_constraint(x[3] <= 9) %>% 
  add_constraint(x[1] - M * y[1]  <= 0) %>% 
  add_constraint(x[2] - M * y[2] <= 0) %>% 
  add_constraint(x[3] - M * y[3] <= 0) %>% 
  add_constraint(y[1] + y[2] + y[3] <= 2) %>% 
  add_constraint(3 * x[1] + 4 * x[2] + 2 * x[3] - M * y[4] <= 30) %>% 
  add_constraint(4 * x[1] + 6 * x[2] + 2 * x[3] + M * y[4] <= 40 + M) %>% 
  solve_model(with_ROI(solver = "glpk"))

Solution

get_solution(goodproducts, x[i])

##   variable i value
## 1        x 1   5.5
## 2        x 2   0.0
## 3        x 3   9.0

Not covered

Other options with the branch-and-bound technique
A branch-and-bound algorithm for MIP
The branch-and-cut approach
The incorporation of constraint programming

Sources

F.Hillier, G.Lieberman. Introduction to Operations Research. Tenth Edition.
D.Schumacher. Optimization Modelling Package.