TNK104 Applied Optimization

Lecture 7

based on the slides provided by Nikolaos Pappas

Relaxation and Bounding, Part I

Tatiana Polishchuk,

Associate Professor,

Linköping University, KTS

https://www.itn.liu.se/~tatpo46/

​

Bounding

TNK104 Applied Optimization I

Minimization

• Many comb. opt problems are hard to solve

→ Optimum out of reach for large-scale scenarios

​

• We have discussed several heuristics aimed at finding good solutions But can we say something about the quality of the solutions?

​

Maximization

​

Heuristic solution

Heuristic solution

Optimum

Optimum

=UB

=LB

Bounding (cont’d)

TNK104 Applied Optimization I

• Primal bound: Feasible solutions (e.g., by heuristics)
• Dual bound: Tells how bad the primal bound can be in the worst case
• Computing dual bounds: relaxation and duality
• Getting good dual bounds can be tough!

​

An example showing a solution to a telecommunication network design problem:

Design solution: 27681734.21

Dual bound: 23707019.81

Optimum

Example taken from the SNDlib

Duality

TNK104 Applied Optimization I

• Generally speaking, duality means a pair of problems providing bounds to each other

Examples:

• LP and its dual, with strong duality if optimum is bounded
• An ILP and the dual of its LP relaxation

c(x)

w(u)

∞

—∞

5

TNK104 Applied Optimization I

Recap: LP Duality

Primal

Dual

An (Classical) Example of Duality in Graphs

TNK104 Applied Optimization I

Maximum cardinality matching

Minimum cardinality cover

Find a set of disjoint edges of maximum size

Instance: A graph G = (V, E)

Find a set of nodes of minimum size, such that every edge has at least one endpoint in the set

Matching

Cover

An (Classical) Example of Duality in Graphs (cont’d)

TNK104 Applied Optimization I

Another (Classical) Example of Duality in Graphs

TNK104 Applied Optimization I

Vertex coloring

Maximum clique

Instance: A graph G = (V, E)

Clique = A set of nodes forming a complete subgraph Find a clique of maximum size

The minimum number of colors is at least the size of any clique

Find a feasible color assignment for the vertices with minimum number of colors

Relaxation

TNK104 Applied Optimization I

Relaxation: problem simplification

• Ignore some constraint (and/or integrality requirement→ LP relaxation)
• Modify some constraint to make the problem easier
• Lagrangean relaxation (next lecture)
• Removal of constraints plus modification of the objective function
• Lagrangean dual
• Surrogate relaxation
• Aggregation of constraints of the same sense by (positive) weights
• Positive semi-definite program (PSD) relaxation
• Derive a PSD with a more optimistic optimum

​

​

A strong relaxation (good bounds) typically takes more time to solve than a weak relaxation

Relaxation Illustrated

TNK104 Applied Optimization I

Simple Relaxations for Binary Knapsack

TNK104 Applied Optimization I

​

​

We can find a heuristic solution by a greedy algorithm. But how good is the solution?

• Let’s increase the RHS to infinity!

→ Select all items, value = 45 (valid but poor upper bound)

• We can’t select more than 21/4 = 5 items, and no item has value greater than 9

→ 5 x 9 = 45 (same bound)

• Pick the 5 items with largest values

→ 9+8+7+6+6 = 36 (Better bound)

• Can we really pick 5 items? The coefficients are 4, 5, 5, 6, 6, 6, 8

→ 9+8+7+6 = 30 (Even better)

​

ILP and LP Dual

TNK104 Applied Optimization I

• LP relaxation gives a dual bound (optimistic estimation of the ILP)
• Any feasible solution to the LP dual is an optimistic estimation of the ILP

→ We can obtain an optimistic estimation to the ILP via a heuristic solution of the LP dual!

Playing around with Relaxations for Knapsack

TNK104 Applied Optimization I

Playing around with Relaxations for Knapsack (cont’d)

TNK104 Applied Optimization I

Playing around with Relaxations for Knapsack (cont’d)

TNK104 Applied Optimization I

One-Tree Relaxation for TSP

TNK104 Applied Optimization I

• A TSP tour is, in fact, a tree + one edge
• MST is a relaxation!
• One-tree relaxation: The minimum-cost subgraph that is a tree with an extra edge
• Choose a node
• Delete the node and its edges
• Find MST for the remaining graph
• Add the node and its two cheapest edges

Clearly, we have relaxed some of the TSP constraints Which constraint has been relaxed?

Formulation and more details in the Discrete Optimization lecture slides from the University of Twente

tour

1-tree

Vehicle Routing Problem (VRP)

TNK104 Applied Optimization I

Depot

Can you think of a simple relaxation of VRP?

• A graph having one depot node
• Customers/nodes, each having a demand to be delivered
• A fleet of vehicles, each having a capacity limit, supplies the customers
• Every vehicle starts at the depot
• Construct the routes, minimizing the total cost (e.g., distance)