Solving Real-Life Problems with Integer Programming

[Pages:23]Motivation

Vehicle Routing

Scheduling

Production Planning

Solving Real-Life Problems with Integer Programming

Jesper Larsen1

1Department of Management Engineering Technical University of Denmark

42113 Network and Integer Programming

Motivation

Vehicle Routing

Linear Programming

Scheduling

Production Planning

Linear Programming is a strong tool for many real-life optimization problems.

We can solve large problems (thousands of constraints and millions of variables).

We can solve problems fast (even big problems with hundreds of constraints and thousands of variables solve in seconds or fractions hereof).

We can model a lot of problem type and using a modelling language (CPLEX, GAMS, OPL, MPL, etc.) it is easy to make the computer solve the problem.

Motivation

Vehicle Routing

Integer Programming

Scheduling

Production Planning

Integer variables extends the possibilities of problem solving. Basically all modeling languages incorporates integer variables.

Problem is that integer programs are (in general) much more difficult to solve than linear programs. It is therefore important to know:

How does an integer programming solver work. How can we exploit structure to implement efficient methods.

Motivation

Vehicle Routing

Vehicle Routing

Scheduling

Production Planning

Motivation

Vehicle Routing

Vehicle Routing

Scheduling

Production Planning

Given is a set of vehicles K and a set of nodes N. Each node i has to be supplied from a depot with some quantity qi . Each vehicle has a capacity of Q.

A Solution

q2

q4

q3

q1

q9

q5 q7 q8

q6

Integer Program

Objective: minimize number of vehicles or minimize to distance driven.

Constraints: Routes start and finish at depots, must respect capacity, and go from customer to customer.

Motivation

Vehicle Routing

A scheduling problem

Scheduling

Production Planning

We have 6 assignments A, B, C, D, E and F, that needs to be carried out. For every assignment we have a start time and a duration (in hours).

Assignment A B C D E F Start 0.0 1.0 2.0 2.5 3.5 5.0

Duration 1.5 2.0 2.0 2.0 2.0 1.5

Motivation

Objective

Vehicle Routing

Scheduling

Production Planning

A Workplan A workplan is a set of assignments. Now we want to formulate a mathematical model that finds the cheapest set of workplans that fullfills all the assignments.

Workplan rules A workplan can not consist of assignments that overlap each other. The length L of a workplan is equal to the finish time of the last assignment minus start of the first assignments plus 30 minutes for checking in and checking out. the cost of a workplan is max(4.0, L).

Motivation

Vehicle Routing

A View of the Assignments

Start Duration

A 0.0

1.5

B 1.0

2.0

C 2.0

2.0

D 2.5

2.0

E 3.5

2.0

F 5.0

1.5

Scheduling

Production Planning

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download