1.3　本书内容简介

对于组合优化问题中的NP困难问题，设计求解问题的有效算法至关重要，设计算法所涉及的技术与方法也是组合优化理论中的一个重要组成部分。组合优化问题一般都可表示成一个整数规划问题，特别是0-1整数规划，因此，数学规划松弛方法可应用于求解NP困难问题的算法设计中。能否得到好的算法，关键是决策变量的选取。数学规划松弛方法主要包括线性规划松弛、凸二次规划松弛、半定规划松弛和拉格朗日松弛等。

一个NP困难问题的数学规划松弛所得到的最优值是该问题最优值的一个下界（对于最小化问题），这个下界可用于求解该问题的分支定界算法中，如果能构造出更有效的不等式约束，将得到该问题更紧的松弛，即能得到一个更大的下界，这样所设计的分支定界算法在求解过程中更加有效。早期这方面的研究主要针对旅行售货员问题，得到超过100个城市的最优解（Crowder & Padberg，1980）。对于一个NP困难问题，也可以直接通过其数学规划松弛的最优解设计求解该问题的近似算法，而近似算法设计的关键是舍入方法（Raghavan & Thompson，1987）。对于图论中的最大割问题，可得到半定规划松弛（Goemans & Williamson，1995），再用随机舍入方法设计求解最大割问题的近似算法，这一近似算法的界达到0.651，改进了当时最好的界0.5，这也是第一次用半定规划松弛方法设计组合最优化问题的近似算法，并取得了好的成果。应用数学规划松弛设计求解排序问题的算法也有丰富的研究成果，最早是在研究单台机器总延误问题时，在设计分支定界算法中应用拉格朗日松弛（Fisher，1976），获得其所求问题的下界，算法成功求解的实例其工件数超过50个。

由于排序问题一般都可用0-1整数线性规划表示，因此，线性规划松弛尤为重要，得到的成果也非常丰富。在排序论中，线性规划松弛最早用于研究单台机器排序问题，对于具有就绪时间的排序问题1｜ r _j ｜ ∑w _j C _j ，通过引进工件开工时间变量、工件加工次序变量、时间指标变量等得到3种不同的线性规划松弛（Dyer & Wolsey，1990）。凸二次规划松弛和半定规划松弛分别用于研究平行机问题R｜ r _{i j} ｜ ∑w _j C _j 和 R 2｜ r _j ｜ ∑w _j C _j ，也得到了好的近似算法（Skutella，2001）。本书主要介绍排序问题的数学规划松弛方法，包括线性规划松弛和凸二次规划松弛两大部分，所讨论的排序问题包括经典排序问题、工件可拒绝排序问题和工件加工时间可控排序问题。

第2章 、第3章和第4章讨论了线性规划松弛方法。第2章所讨论的经典排序问题包括单机排序问题和平行机排序问题，表1.1给出了我们所讨论的经典排序问题的基本信息，包括决策变量选取以及近似算法的性能比。

第3章 讨论了工件可拒绝排序问题，应用线性规划松弛方法给出了3个工件可拒绝排序问题的近似算法，表1.2给出了我们所讨论的排序问题的基本信息，包括决策变量选取以及近似算法的性能比。

第4章 讨论了工件加工时间可控排序问题，应用线性规划松弛方法给出了2个工件加工时间可控排序问题的近似算法，表1.3给出了我们所讨论的排序问题的基本信息，包括决策变量选取以及近似算法的性能比。

第5章 、第6章和第7章讨论了凸二次规划松弛方法。第5章讨论了平行机排序问题，表1.4给出了我们所讨论的排序问题的基本信息，包括决策变量选取以及近似算法的性能比。

第6章 讨论了工件可拒绝排序问题，应用凸二次规划松弛方法给出了2个工件可拒绝排序问题的近似算法，表1.5给出了我们所讨论的排序问题的基本信息，包括决策变量选取以及近似算法的性能比。

第7章 讨论了工件加工时间可控排序问题，应用凸二次规划松弛方法给出了3个工件加工时间可控排序问题的近似算法，表1.6给出了我们所讨论的排序问题的基本信息，包括决策变量选取以及近似算法的性能比。