Chapter 2 explains how it is possible to prove that feasible solutions are optimal or close to optimal.

目录

• 2 Optimality, Relaxation, and Bounds
• • 2.1 Optimality and Relaxation
  • 2.2 Linear Programming Relaxations
  • 2.3 Combinatorial Relaxations
  • 2.4 Lagrangian Relaxation
  • 2.5 Duality
  • 2.6 Linear Programming and Polyhedra
  • 2.7 Primal Bounds: Greedy and Local Search

2 Optimality, Relaxation, and Bounds

2.1 Optimality and Relaxation

我们想要寻找upper和lower bounds。

• Primal Bounds
  每个可行解都提供了一个lower bound。但有时寻找可行解本身就是一件不容易的事情。
• Dual Bounds
  松弛可以得到upper bound：扩大可行域或者替换目标函数为原目标函数的上界
  

2.2 Linear Programming Relaxations

• 更好的formulation会得到更紧的bound
  
• LP无解，IP无解；LP最优解是整数，它也是IP最优解

2.3 Combinatorial Relaxations

松弛得到的问题是组合优化问题。

• The Traveling Salesman Problem
  
• Symmetric Traveling Salesman Problem (STSP)
• The Quadratic 0–1 Problem
• The Integer Knapsack Problem

2.4 Lagrangian Relaxation

2.5 Duality

• 注意：对偶问题的任意可行解都提供了一个upper bound，而松弛问题的最优解才提供了一个upper bound。

• 线性松弛问题的对偶问题自然地和原问题形成了一个weak dual pair
  

• 对偶问题有时可以被用来证明最优性
  

• 一个例子：A Matching Dual
  
  从线性规划对偶角度来得到这个结果：
  
  
  

  强对偶不总是成立；当图是二分的的时候，强对偶成立。

• A Superadditive Dual
  
  

2.6 Linear Programming and Polyhedra

• 有可行解的充要条件
  
  
  
  

2.7 Primal Bounds: Greedy and Local Search

Now, we briefly consider some simple ways to obtain feasible solutions and primal bounds. This topic is treated in considerably more detail in Chapter 13.

• Heuristics from Restrictions
  
  
  • to fix the values of some variables
  • to replace inequalities by equalities
  • to add additional constraints
  • …
• Greedy and Local Search Heuristics
  • Greedy：两个例子
  • Local Search：两个例子