DISCRETE OR - summary

Linearizing Non-Linear Constraints/Objectives

Either-Or constraints

Linearizing Non-Linear Constraints/Objectives

If-Then constraints

Linearizing Non-Linear Constraints/Objectives

Incorporating absolute values: in constraints |f(x)|

Linearizing Non-Linear Constraints/Objectives

Incorporating absolute values: in constraints |f(x)| + |g(x)|

SECs

Option 1 and Option 2

SECs

Option 3

MST lower & upper bound

1-Tree

Construction Heuristics

Route first, cluster second heuristics

Assume the number of vehicles can be anything.

Construct a giant TSP tour through all nodes and the depot.

Then partition the tour into feasible segments.

ITP, OP

Construction Heuristics

Cluster first, route second heuristics

Assume the number of vehicles (K) is fixed. Form K clusters.

Then find routes for each cluster.

Clarke - Wright Savings Heuristic

Algorithm

Starts with 0-i-0 for all i.

For asymmetric > only use max savings

Operators

Improvement Heuristics

VRP Local Search

Neighborhoods

Node-insertion neighborhood

4 Local Search Neighborhoods

Selection Schemes for Operators

Roughly categorizing, there are four selection schemes:

Meta-heuristics

Tabu Search

Algorithm

Tabu Search

Tabu List & Aspiration Criteria

Simulated Annealing

Algorithm

Simulated Annealing

Acceptance Criterion

Procedure Design

Simulated Annealing & Tabu Search

Provide code to replace lines 9 and 10 so that a random route r and swap position s are selected.

Python

%
len()
range()
list slicing
loops

Python

pop()
insert()
loc

What does it print?

CVRP

Problem Definition:

Transportation Problem

Model + Standard Form

Cost Matrix

Example

Maximal Flow Problem

Model

Minimal Cut Problem

The max-flow min-cut theorem states the maximum flow equals the minimum cut capacity.

Duality

+ weak duality

Primal -> Dual

Node-Arc Incidence Matrix

The Matrix

Max Flow Problem with Node-Arc Incidence Matrix

Model

Max Flow Problem with Node-Arc Incidence Matrix

Rewriting Model

Max Flow Problem with Node-Arc Incidence Matrix

The Dual

Minimum Cost Flow Problem

Minimum Cost Flow Problem with Node-Arc Incidence Matrix

Model

TU matrices

Dynamic Programming Theory

Typical Properties & It works when we can …

Bellman Equation

Bellman Equation

State Transition & Min Variant

Challenges in Dynamic Programming

Dynamic Programming

Shortest-route problem

Dynamic Programming

TSP + Curse of Dimensionality

Dynamic Programming

Workforce Planning

Dynamic Programming

Ordering Inventory

Dynamic Programming

Game of Dice

Dynamic Programming

Coin Change Problem