优化组合：理论与方法

需积分: 25 171 浏览量更新于2024-07-18 收藏 616KB PDF 举报

《组合优化笔记》是一篇关于优化理论的重要参考资料，特别关注于组合优化（Combinatorial Optimization）及其与多面体组合学的关联。该文档分为四个主要章节，深入探讨了优化问题的各个方面。 **第一章：组合优化与多面体组合** 本章首先介绍了组合优化的基本概念和形式化表述，包括如何将实际问题转化为数学模型，以及如何通过构造松弛（relaxations）来寻找最优解。作者还讨论了分离算法（separation oracles），如在动态单纯形法（dynamics simplex method）中的应用，以帮助解决复杂的组合优化问题。以森林多面体为例，阐述了如何设计有效的分离算法来检验可行域。 **第二章：整数多面体、TDI系统与全单模矩阵** 在这一部分，作者探讨了整数多面体，这些是优化问题中关键的几何结构，它们的顶点只包含整数解。TDI系统（Totally Dual Integrality）与全单模矩阵紧密相关，前者保证了线性规划的最优解同时满足整数性和对偶问题的整数性。此外，这部分还涉及网络矩阵的应用和最小最大定理在组合优化中的体现。 **第三章：组合优化的启发式算法** 本章着重介绍两种常用的启发式算法：构造式算法，如初始解生成策略；以及改进式算法，如局部搜索策略，用于在求解复杂问题时寻找近似最优解。通过实例，读者可以了解这些算法在实际问题中的应用和效果。 **第四章：精确方法** 这部分深入解析精确求解组合优化的方法，包括： 1. 松弛与分支定界法：通过放松约束以扩大搜索空间，然后通过分支策略逐层细化问题，直到找到最优解或证明无解。 2. 寻找附加有效不等式：在已知条件的基础上，探索新的限制条件，以增强问题的描述精度。 3. 拉格朗日松弛：利用拉格朗日乘子技术，将原问题转化为更易处理的形式，以便于求解。 4. 旅行商问题（Traveling Salesman Problem, TSP）：经典的组合优化问题，这里详细探讨了其解法和相关策略。 5. 练习题：提供了一系列练习，帮助读者巩固所学知识并进行实践操作。《组合优化笔记》提供了丰富的理论知识和实用技巧，适用于学习和研究组合优化的学者和工程师，无论是在理论层面还是在解决实际问题时，都具有很高的参考价值。

(0,0) 1

u u

u e

(



Figure 1.4: A formulation for the set of feasible solutions of Example 1.1

1.1 Formulations and r elaxations for (CO)

We start with an important deﬁnition.

Deﬁnition 1.1. Let S ⊆ {0, 1}

. A formulation for S is a polyhedron P ⊆ IR

satisfying P ∩ {0, 1}

= S.

In other words, P is a formulation for S iﬀ the 0-1 points of P are precisely the

points of S. A possible formulation for the set of feasible solutions of Example

1.1 is given in Figure 1.1. Clearly, one can build an inﬁnite number of diﬀerent

formulations f or the same set S. Since conv(S) ∩ {0, 1}

= S, it follows that

conv(S) is one such formulation for S. A special role is played by t he so called

natural formulation, which is the one directly obtained from the constraints ofnatural

formulation the original problem when this is stated as a linear pogramming problem with

integrality constraints on the variables. In particular, S is sometimes directly de-

ﬁned as the set of binary solutions to a family of linear constraints. In other cases,

such a family of linear constraints may be derived directly from the description

of the problem, as in Example 1.1. Of course, a natural f ormulation may not be

available in general.

Example 1.1 (continued). Let S be the set of feasible solutions of Example 1.1,

and let x ∈ S. Since x is a binary vector, then it satisﬁes:

0 ≤ x

≤ 1 i = 1, 2 (1.7)

Also, x satisﬁes the budget constraint:

300000x

+ 400000x

≤ 600000 (1.8)

elimination constraints:

x(E[S]) ≤ |S| − 1 for all S ⊆ V , S 6= ∅, S 6= V .

These constraints were introduced in the 1954 paper by Dantzig, Fulkerson and

Johnson [5]. Note that the number of 2-connectivity inequalities, or subtour elim-

ination constraints, g rows exponentially as a function of the number of nodes.

Relaxations.

In what follows we will often deal with mathematical optimization problems of the

form max{f(x) : x ∈ S ⊆ IR

}, and with their optimal values. Conventionally,

we will denote such a problem by a capital roman letter b etween brackets, e.g.

(Q); also, we denote its value by v(Q) = max{f( x) : x ∈ S ⊆ IR

} where we

permit the values v(Q) = −∞ (when the problem is infeasible) and v(Q) = ∞

(when the problem is unbounded).

Now, suppose we want to solve the combinatorial optimization max{w

x : x ∈ S}

(where S ⊆ {0, 1}

}) denoted by (Q), and assume we have at hand a feasible

solution ¯x ∈ S to (Q). How good is ¯x? In ot her words, how does the value w

¯x of

¯x compare with the optimal value v(Q) to (Q)? We will see that formulations can

provide such an answer. First we need to introduce the concept of a relaxation of

an optimization problem.

Deﬁnition 1.2. Let S ⊆ IR

and let (Q) be max{w(x) : x ∈ S}. The problem

(R) max{g(x) : x ∈ T } is a relaxation of (Q) iﬀ T ⊇ S and g(x) ≥ w(x) for a ll

x ∈ S.

The following theorem is a straightforward consequence o f the above deﬁnition:

Theorem 1.3. Let (Q) be a maximization probl e m (as above) an d let (R) be a

relaxation of ( Q ). T hen v(R) ≥ v(Q).

relaxation

quality

In o ther words, the optimal value of (R) provides an upper bound (UB) on the

optimal value of (Q). Let’s go back to our original question. In many cases, it

may be very diﬃcult to ﬁnd an optimal solution x

∗

of an optimization problem

Q, whereas it can be easy to obtain a feasible solution ¯x ∈ S. This is often the

case when (Q ) is a combinatorial optimization. Clearly, w(¯x) ≤ w(x

∗

) = v(Q),

and w(¯x) is a lower bound (LB) on the optimal value to (Q). Suppose now that

we have at hand a relaxation (R) {max g(x) : x ∈ T } of (Q ) and assume that an

optimal solution y

∗

to R can be computed eﬃciently. We have

UB = v(R ) = g(y

∗

) ≥ w(x

∗

) ≥ w(¯x) = LB.

The optimal value of (Q) belongs to the interval between the lower and the

upper bound (we are assuming that both can be computed eﬃciently). Its size

UB −LB is called the gap. The smaller the gap is, the better it is. If gap = 0 then

UB = LB, which in turn implies UB = v(R) = g(y

∗

) = w(x

∗

) = w(¯x) = LB,

which proves that ¯x is an optimal solution to (Q). So, in general, we would like

the upper bound to be as small as possible; in contrast, the lower bound should

be as large as possible. In other words, we want to have at hand

• strong relaxations of (Q), providing small upper bounds on v(Q) and

• eﬀective heuristic methods, capable to ﬁnd g ood quality solutions to (Q),

hopefully optimal.

The rest o f this chapter is devoted to the ﬁrst goal, whereas heuristic methods

will be discussed in a subsequent chapter.

Now, let (Q) be max{w

x : x ∈ S} where S ⊆ {0, 1}

be a combinatorial

optimization problem, and let P ⊆ IR

be a for mulation for S. By deﬁnition,

S ⊆ P . It f ollows from the above discussion that the following problem

(R) max{w

x : x ∈ P }

is a relaxation of (Q). Since problem (R) amounts to maximizing a linear func-

tion over a polyhedron, (R ) is a linear program (LP), and we there are a number

of eﬃcient algor ithms to solve LPs. The simplex method is one of these, even

though its theoretical complexity is still unknown. This means that the simplex

method works very well in practice, but in principle there exist highly complicated

instances requiring a n enormous amount of time to be solved. Interestingly, the-

oretically more eﬃcient methods as the interior point a lgorithms do not perform

signiﬁcantly better in practice. So, problem (R) along with the simplex metho d

can be used to compute upper bounds on v(Q). comparing

formulations

As already mentioned, we may have diﬀerent formulations for the same set S.

How can we distinguish among them? We need some criteria to compare between

formulations and to measure their quality. So, let (Q) be max{w

x : x ∈ S ⊆

{0, 1}

} be a combinatorial optimization, and let P

and P

be two distinct for-

mulations for S. Since we want to use P

and P

to compute upper bounds on

v(Q), one candidate quality criterium is the following: P

is better than P

if and

only if max{w

x : x ∈ P

} ≤ max{w

x : x ∈ P

}. So, if we consider the two for-

mulations in Figure 1.1 for the problem of Example 1.1, the natural formulation

has to be preferred to the other when the objective function is the original

one, to maximize 4x

+ 5x

However, if the o bjective becomes max x

, then P

has to be preferred to P

So, this indicator is dependent on the objective and thus on the problem. It is

剩余79页未读，继续阅读

QAQ_L

粉丝: 0
资源: 1

优化组合：理论与方法

MATLAB智能算法30个案例分析：遗传算法、免疫算法、粒子群算法等

"测量装置制造中的标定点选择问题：基于遗传算法的优化方案研究

"智能算法在TSP问题的组合优化应用研究

PROBABILISTIC COMBINATORIAL OPTIMIZATION

Metaheuristics in Combinatorial Optimization

Handbook of Combinatorial Optimization

Iterative methods in combinatorial optimization

Combinatorial optimization polyhedra and efficiency

first course in combinatorial optimization

Papadimitriou Combinatorial Optimization.djvu

最新资源