# Teaching Integer Programming Formulations Using the Traveling Salesman Problem∗
## 1. Introduction.
### 1.1. Integer Programs and Their Formulations.
:::info
An integer program (IP) is an optimization problem of the form $\min c^Tx \text{ s.t. } x \in X$, where $X = \mathbb{Z}^n \cap \left\{ x \in \mathbb{R}^n \vert Ax \leq b \right\}$, with some matrix $A$, vector $b$, and the symbols $\mathbb{Z}^n$ and $\mathbb{R}^n$ denoting the set of integer and real $n$-vectors, respectively. The polyhedron $\left\{ x \in \mathbb{R}^n \vert Ax \leq b \right\}$ is a formulation of the set $X$. An IP has many formulations; for instance, in Figure 1 the solid and dashed lines enclose the same integer points; i.e., the corresponding polyhedra are both formulations of the same set.
:::

:::success
整數規劃(IP)是一個最佳化問題，其形式為$\min c^Tx \text{ s.t. } x \in X$，其中$X = \mathbb{Z}^n \cap \left\{ x \in \mathbb{R}^n \vert Ax \leq b \right\}$，以某一個矩陣$A$、向量$b$，且$\mathbb{Z}^n, \mathbb{R}^n$各自為整數的集合與實際為$n$為向量。[多面體](http://terms.naer.edu.tw/detail/714641/)$\left\{ x \in \mathbb{R}^n \vert Ax \leq b \right\}$是集合$X$的形式。一個整數規劃會有多個形式；舉例來說，在Figure 1中，實線與虛線圍起相同的整數點。也就是相對應的多面體是相同集合的兩個形式。
:::

:::info
Fig. 1 Two formulations of the same set.

:::

:::info
Given two such polyhedra, $P$ and $Q$ (i.e., $P \cap \mathbb{Z}^n = Q \cap \mathbb{Z}^n$), we say that $P$ is a better, or stronger, formulation, if $P \varsubsetneq Q$. (The definitions here are from [9].)
:::

:::success
給定兩個多面體，$P$與$Q$(即，$P \cap \mathbb{Z}^n = Q \cap \mathbb{Z}^n$)，如果$P \varsubsetneq Q$，那我們就說$P$比較好的、更強而有力的形式(定義來自[9])。
:::

:::info
One of the most important skills that a practitioner of integer programming must acquire is that of designing a strong formulation for a particular problem. The main component of all commercial IP solvers is a branch-and-bound algorithm that uses the linear programming (LP) relaxation of an IP (i.e., the problem obtained from an IP by discarding the integrality constraints). Hence, a stronger formulation usually can be solved with fewer branch-and-bound nodes; if the tighter LPs are not “much” more time-consuming, this translates into a smaller overall solution time. Even if the problem cannot be solved to optimality within the available time, a strong formulation provides a good bound on the optimal value of the problem. Hence it can also serve as a counterpoint to an effective heuristic, by proving that a solution provided by the latter is close enough to being optimal.
:::

:::success
整數規劃的從業人員最重要的技巧之一就是為特定問題設計出一個強形式。所有商用整數規劃解答器的主要組件是演算法branch-and-bound，該演算法使用整數規劃的線性規劃(LP)[鬆弛](http://terms.naer.edu.tw/detail/2123609/)(即利用放棄限制式的完整性從整數規劃得到問題)。因此，一個更強而有力的形式通常可以用少少的branch-and-bound節點來求解；如果更緊密(tighter)的線性規劃不會花費更多的時間，那就轉化為更小的整體求解時間。即使問題無法在可用時間內求到最佳解，強形式也會為問題提供一個好的界限(bound)。因此，透過證明後者的解決方案是夠接近最佳解，它也可以做為一個有效的啟發式對比。
:::

### 1.2. Exercises to Compare Formulations in Practice.
:::info
A classroom lecture on comparing weak and strong formulations is best accompanied by an assignment asking students to do a computational comparison. Such a comparison can simply consist of feeding a strong and a weak formulation of the same problem to an IP solver and comparing the number of branch-and-bound nodes and times required to solve them to optimality. A problem is well suited for the purpose of a comparison if
1. it is relevant in practice, interesting, and easy to understand;
2. the advantages of the strong formulation are not immediately apparent, for some of the following reasons:
* the strong formulation uses many more variables and/or constraints;
* the weak one can accommodate more versatile objective functions;
3. the weak and strong formulations are easy to generate.
:::

:::success
關於弱、強形式的課程最好是是跟要求學生做計算比較的作業同時進行。這樣的比較可以簡單的將相同問題的強、弱形式餵給整數規劃解決器，然後比較branch-and-bound節點數量與求到最佳解所需要的時間。一個問題很適合用於比較，只要滿足：
1. 實用性高、有趣、很容易理解
2. 基於下面理論，強形式的優勢無法立即的顯現：
* 強形式會使用更多的變數and/or約束式
* 弱形式可以容納更多的目標函數
3. 弱與強形式很容易生成
:::

:::info
Several such problems are (see, e.g., [9])
* facility location problems (with their weak, i.e., the aggregated, and the strong, i.e., the disaggregated formulation);
* knapsack problems (their usual formulation can easily be strengthened by cover inequalities);
* lot-sizing problems (their usual formulation can be strengthened by various inequalities).
:::

:::success
有幾個這樣的問題(見[9])
* 設備選址(設施定位)問題(FLP)
* 背包問題
* 批量問題
:::

:::info
For many problems, however, the advances in IP software disguise the advantage of providing a stronger formulation to solvers. Most IP solvers now incorporate automatic reformulation techniques that can substantially strengthen a weak formulation. Such techniques include disaggregation (i.e., replacing the constraint $\sum^m_{i=1}x_i\leq my$ on the 0–1 variables $x_i$ and $y$ with the inequalities $x_i \leq y(i=1,...,m)$), generating many of the inequalities that one would add to the knapsack, and lot-sizing problems (e.g., covers, and flow-covers). Hence, in the case of the models listed above,
* frequently there is no significant difference in the solution times, when feeding a weak or a strong formulation to the solver;
* sometimes the solution times are even better for the weaker formulation. The reason is that IP solvers strengthen the weak formulation quite intelligently. For instance, when disaggregating, they only add those xi ≤ y inequalities, which are violated by the current LP solution, thus not enlarging the LP relaxation unnecessarily;
* or, the strong one must be quite sophisticated and hence not too useful at the beginning of a course, when the importance of strong formulations should already “sink in.” Such an example is strengthening the lot-sizing problem with path-inequalities ([9, p. 223]).
:::

:::success
然而，對很多問題而言，整數規劃軟體的進步掩飾了為解決器(solver)提供更強而有力的公式的優勢。現在，多數的整數規劃解決器都納入自動重組技術，這技術可以大大的增強弱形式。這樣的技術包含分解(即，用不等式$x_i \leq y(i=1,...,m)$取代約束式$\sum^m_{i=1}x_i\leq my$的變數$x_i, y$)，生成許多加到背包、批量問題的不等式(e.g., covers, and flow-covers)。因此，在上述模型情況下，
* 當餵給解決器弱或強形式的時候，在求解時間通常沒有明顯的差異；
* 對於弱形式而言，有時候求解時間甚至更好。理由是，整數規劃解答器巧妙的加強了弱形式。舉例來說，當分解的時候，它們就是單純的增加那些當前線性規劃求解所違反的不等式，$x_i \leq y$，因此不會不必要的去擴大線性規劃的鬆弛；
* 或者，強形式必需相當複雜(精巧?)，因此在課程開始的時候就不是那麼有用，這時候強形式的重要性應該已經被充份理解。這樣的範例正加強具有path-inequalities的批量問題([9, p. 223])。
:::

:::info
Of course, one could always ask the students to turn off the preprocessor, or the cut-generator of the solver; this would hardly make a convincing exercise, though.
:::

:::success
當然啦，總是可以要求學生關掉前處理器或解答器的cut-generator；但是這就很難成為一個令人信服的練習了。
:::

:::info
A problem that well fits criteria (1) and (2) is the traveling salesman problem (TSP): given n cities, and pairwise travel costs between them, find the shortest tour, i.e., a directed cycle containing all cities. (In fact, students invariably find the TSP more fascinating than the somewhat mundane knapsack, location, or lotsizing problems.) The formulation that serves as a benchmark for all others is the subtour formulation; there are also many weaker ones. Three articles that survey and analytically compare some of them are [1], [5], and [8]. The weaker formulations all use extra variables; i.e., the set of tours $X$ is written as $X=\mathbb{Z}^n \cap P$, where $P=\left\{x\vert Bx + Du \leq f \text{ for some } u \in \mathbb{R}^m \right\}$. Now $P$ is the projection of the polyhedron $\left\{(x,u)\vert Bx + Du \leq f \right\}$, hence it is also a polyhedron. Thus we can write $P=\left\{x \vert Gx \leq h \right\}$ for some matrix $G$ and vector $h$. The latter representation, however, may contain many more and/or more complicated inequalities than the first.
:::

:::success
符合條件(1)、(2)的問題就是旅行推銷員問題(TSP)：給定$n$個城市，以及城市之間的旅行成本，從中找出最短的行程，也就是包含所有城市的有向循環。(事實上，學生總是發現TSP比起一些單調的背包、位置或批量問題來有的吸引力)。做為所有其它基準的公式為subtour formulation；還存在許多較弱的形式。有三篇做為調查分析比較的文章為[1],[5],[8]。較弱的形式都使用額外的變數；也就是行程的集合$X$寫為$X=\mathbb{Z}^n \cap P$，其中$P=\left\{x\vert Bx + Du \leq f \text{ for some } u \in \mathbb{R}^m \right\}$。現在$P$是一個多面體$\left\{(x,u)\vert Bx + Du \leq f \right\}$的投影，因此它也是多面體。因此，我們可以對某些矩陣$G$與向量$h$寫為$P=\left\{x \vert Gx \leq h \right\}$。不過，後面的那種表示可能比前一種表示包含更多and/or更複雜的不等式。
:::

:::info
Designing an experiment that allows students to do a computational comparison is not quite obvious though. This note gives a simple guide to comparing the subtour formulation to a weak one due to Miller, Tucker, and Zemlin [6] on relatively small, but far from trivial instances. It utilizes a primitive “cutting plane algorithm” of about 60 lines of MATLAB code that, used with a commercial IP solver, allows students to do the comparison and solve real world instances with up to 70 nodes to optimality.
:::

:::success
不過，設計一個讓學習去做計算比較的實驗並不是十分明顯。這個注意事項給出一個簡單的指南，主要是用於將subtour fourmulation與Miller, Tucker, and Zemlin [6]在相對小但不是鎖碎的實例上提出的弱形式做比較。它用了以MATLAB寫的“cutting plane algorithm”大約60行的程式碼，與商業整數規劃解答器一起用，可以讓學生做比較，然後可以解決最高70個節點的實際案例。
:::
## 2. The Formulations.
### 2.1. Problem Statement and the Node Constraints.
:::info
In the complete directed graph $D=(N, A)$, with arc-costs $c_{ij}$ , we seek the tour (a directed cycle that contains all n cities) of minimal length. Define the variables

$$
x_{ij}=
\begin{cases}
1, & \text{if arc ($i, j$ is in the tour)} \\
0, & \text{otherwise}
\end{cases}
$$
:::

:::success
在完全有向圖$D=(N, A)$中，有著arc-costs $c_{ij}$，我們尋找最短長度的行程(包含所有$n$個城市的有向循環)。定義變數如下：
$$
x_{ij}=
\begin{cases}
1, & \text{if arc ($i, j$ is in the tour)} \\
0, & \text{otherwise}
\end{cases}
$$
:::

:::info
The feasible solutions of the integer program (in fact, there is always an integer optimal solution to the LP relaxation)

$$
\begin{align}
\min \sum_{i,j}c_{ij}x_{ij}\\
\text{s.t. } \sum_ix_{ij}=1 \space \forall i,\\
\sum_jx_{ji}=1 \space \forall i, \\
0 \leq x_{ij} \leq 1, \space x_{ij} \text{ integer}
\end{align}\tag{2.1}
$$

may contain several directed cycles, called subtours. The constraints of (2.1) are called the assignment constraints.
:::

:::success
整數規劃的[可行解](http://terms.naer.edu.tw/detail/415950/)()
$$
\begin{align}
\min \sum_{i,j}c_{ij}x_{ij}\\
\text{s.t. } \sum_ix_{ij}=1 \space \forall i,\\
\sum_jx_{ji}=1 \space \forall i, \\
0 \leq x_{ij} \leq 1, \space x_{ij} \text{ integer}
\end{align} \tag{2.1}
$$

也許包含多個有向循環，稱為subtours。上面公式的約束式稱為assignment constraints。
:::
### 2.2. The MTZ Formulation.
:::info
To exclude subtours, one can use extra variables ui (i = 1,...,n), and the constraints

$$
\begin{align}
u_1 = 1, \\
2 \leq u_i \leq n \space \forall i \neq 1, \\
u_i - u_j + 1 \leq (n - 1)(1 - x_{ij}) \space \forall i \neq 1, \forall j \neq 1
\end{align} \tag{2.2}
$$
:::

:::success
為了能夠排除subtours，我們可以使用額外的變數$u_i(i=1,...,n)$與約束式
$$
\begin{align}
u_1 = 1, \\
2 \leq u_i \leq n \space \forall i \neq 1, \\
u_i - u_j + 1 \leq (n - 1)(1 - x_{ij}) \space \forall i \neq 1, \forall j \neq 1
\end{align} \tag{2.2}
$$
:::

:::info
We call the last inequality in (2.2) an arc-constraint. The formulation consisting of (2.1) and (2.2) is called the Miller–Tucker–Zemlin (MTZ) formulation of the TSP; see [6]. It indeed excludes subtours, as (1) the arc-constraint for $(i, j)$ forces $u_j \geq u_i + 1$, when $x_{ij}=1$; (2) if a feasible solution of (2.1)–(2.2) contained more than one subtour, then at least one of these would not contain node 1, and along this subtour the $u_i$ values would have to increase to infinity. This argument, with the bounds on the $u_i$ variables, also implies that the only feasible value of $u_i$ is the position of node $i$ in the tour. The advantages of the MTZ formulation are
* its small size (we need only $n$ extra variables and roughly $n^2/n$ extra constraints),
* if it is preferable to visit, say, city $i$ early in the tour, one can easily model this by adding a term − $\alpha u_i$ with some $\alpha > 0$ to the objective.
:::

:::success
我們稱上面公式(2.2)最後一個不等式為arc-constraint。然後，由(2.1)、(2.2)所組成的公式則稱為TSP的Miller–Tucker–Zemlin (MTZ)；見[6]。它確實排除subtours，因為(1)對$(i, j)$而言，當$x_{ij}=1$，arc-constraint限制了$u_j \geq u_i + 1$；(2)如果(2,1)-(2,2)的可行解包含超過一個subtour，那麼最少其中一個不會包含節點1，而且延著這個subtour，$u_i$的值必需增加到無限大。這個參數，加上$u_i$變數上的邊界(bound)，也意味著只有$u_i$的可行值是節點$i$在行程中的位置。MTZ公式的優點就是：
* 它很小(我們只需要$n$個額外的變數與大約$n^2/n$個額外的約束式)
* 如果說，去參訪是比較好的，那麼我們說，在行程中較早的城市$i$，只要透過增加一個項目，$\alpha u_i$(且$\alpha > 0$)在目標上，就可以很輕易的的對其建模。
:::
### 2.3. The Subtour Formulation.
:::info
The other way to exclude subtours is by adding to (2.1) the family of subtour (or subtour elimination) constraints

$$\sum_{i\in S, j\in S} x_{ij} \leq \vert S \vert - 1 (S \subsetneq V, \vert S \vert > 1) \tag{2.3}$$

to obtain the subtour formulation of the TSP consisting of (2.1) and (2.3). (As the subtour inequality for $N\S$ is a linear combination of the inequality for $S$ and of the assignment constraints, it is enough to use the subtour inequalities with $S$ having size at most $n/2$.) It does not have the advantages of the MTZ formulation. The disadvantage of its exponential size is mitigated by the fact that not all subtour inequalities must be put into the formulation from the start. They can be generated as needed by a separation algorithm: one can start with the formulation (2.1), then generate subtour inequalities that are violated by the current LP solution. The separation algorithm for subtour constraints is based on network flow techniques; for further details, see [4].
:::

:::success
排除subtours的另一種方法就是在(2.1)中加入subtour contraints的family(族?)(或是消除subtour)

$$\sum_{i\in S, j\in S} x_{ij} \leq \vert S \vert - 1 (S \subsetneq V, \vert S \vert > 1) \tag{2.3}$$

以獲得由(2.1)、(2.3)所組成的TSP的subtour formulation。(因為$N\S$的subtour不等式是$S$的不等式與分配約束式的線性組合，因此，subtour不等式最多只要$S=n/2$就夠了。)它並不具有MTZ形式的優點。利用一點，就是並非所有的subtour不等式都必需在開始的時候就通通放到公式裡面，這就可以減少其指數大小的缺點。它們可以利用分離演算法依需求生成：可以從公式(2.1)開始，然後生成當前線性規劃解決方案所違反的subtour不等式。subtour約束式的分離演算法是基於網路流技術(network flow techniques)，更多細節請見[4]。
:::
## 3. The Comparison.
### 3.1. The Strength of the Two Formulations.
:::info
Solving a reasonably large (with at least, say, 50 cities) problem to optimality is only possible using the subtour formulation; at least, we are not aware of any published computational studies that use the pure MTZ formulation. There is an analytical explanation of this fact: the LP relaxation of the MTZ formulation is much weaker. Since it contains the extra $u_i$ variables, for the comparison we need to eliminate them by taking appropriate linear combinations of the inequalities in (2.1)–(2.2). One way of doing this is by summing the arc-inequalities along a directed cycle. If the arc set of the cycle is denoted by $C$, then the result is
:::

:::success
只有使用subtour才能解決一個相當大的問題(最少50個城市)；最少，我們並不知道任何使用純MTZ形式發表的計算研究。這一個針對這個事實的分析解釋：MTZ形式的線性規格鬆弛是較弱的。由於它包含額外的$u_i$變數，為了比較，我們需要利用在(2.1)-(2.2)的不等式中做適當的線性組合來消除它。消除它的一種方法就是加總延著有向循環的arc-inequalities。如果這個循環的art set(弧集合)以$C$來表示，那結果就是

$$\sum_{(i,j) \in C} x_{ij} \leq \left(1 - \dfrac{1}{n-1} \right) \vert C \vert \tag{3.1}$$
:::

:::info
On the other hand, if we denote the node set of the cycle by N(C), then the subtour formulation contains the obviously stronger inequality
:::

:::success
另一方面，如果我們以$N(C)$來表示循環的節點集合，那麼subtour formulation包含明顯更強的不等式

$$\sum_{i,j \in N(C)} x_{ij} \leq \vert C \vert - 1 \tag{3.2}$$
:::

:::info
The intuitive fact that adding the arc-inequalities along a cycle is the only “essential” way to eliminate the ui variables can be made precise. Balas [1] and Padberg and Sung [8] showed that all nondominated inequalities in the projection of the MTZ formulation onto the space of the $x$ variables are of the form (3.1).
:::

:::success
直觀的事實是，延著一個循環增加arc-inequalities是消除$u_i$變數的唯一"必要"的方法。Balas [1] 與 Padberg 與 Sung [8] 說明了，所有MTZ形式在$x$變數空間上投影的非支配型不等式(nondominated inequalities)都是形式(3.1)
:::
### 3.2. How to Combine Them?
:::info
An efficient implementation of a separation routine for subtour inequalities is beyond the ability of most practitioners and undergraduate/MS students. A collection of excellent public-domain routines for the TSP, called Concorde, is available, with such routines among them; see [3]. However, most problems encountered in practice are not pure TSPs, only “TSP-like.” One example is the vehicle routing problem, in which there are k “salesmen” (i.e., trucks), and each of the cities must be visited by one to make a given amount of delivery, while obeying capacity restrictions. For TSP-like problems the TSP formulations are usually not hard to generalize, but the TSP separation routines cannot be used.

:::

:::success
一個對於subtour inequalities分離程序的有效實現是超過多數從業人員與大學生/碩士生的能力。一個用於TSP的優秀公共領域程序的集合，稱為Concorde，包含這類程序的Concorde可見[3]。然而，實務上多數遇到的問題都不是pure TSPs，而是"TSP-like"。一個車輛路徑問題的範例，有$k$個業務員(即卡車)，然後每個城市都必需要有人來拜訪過，才能達到給定的交貨量，同時要遵守容量的限制。對於TSP-like的問題，TSP公式通常不難泛化，但是就不能使用TSP分離程序
:::

:::info
One can combine the MTZ and subtour formulations to obtain the ease of use of the first and some of the strength of the second. Violated subtour inequalities are easy to identify if a solution satisfies the assignment constraints and is 0–1: one can take S to be the union of several subtours. Such an approach is likely to work for TSP-like problems as well. For small problems, one can identify such subtour inequalities even by inspection: see, for instance, the article [7] for such an approach to a variant of the TSP arising in aircraft mission planning. We used the following “cutting plane algorithm” to solve several TSP instances to optimality, with maxrounds an integer between 0 and 2, depending on how much we wanted to strengthen the MTZ formulation.
1. Let the IP formulation consist of the assignment constraints only, and $k = 1$.
2. $\text{while } k \leq \text{ maxrounds}$
* (2a)Solve the IP over the current formulation. Assume that the optimal solution consists of $r$ subtours $S_1,..S_r$.
* (2b)If $r = 1$, STOP; the solution is optimal to the TSP. Otherwise, add to the formulation at most 1000 subtour constraints, in which $S$ is the union of several $S_i$ sets and $\vert S \vert \leq \lfloor n/2 \rfloor$. Set $k=k+1$.
$\text{end while}$
3. Add the arc constraints to the formulation, and solve the IP to optimality
:::

:::success
我們可以將MTZ跟subtour公式結合起來得到MTZ的易用性與subtour的強度。如果一個解滿足約束式而且為0-1，那麼就很容易辨識出違反的subtor inequalities：可以將$S$視為多個subtours的聯集。這樣的方法可能也可以用在TSP-like問題上。針對小的問題，我們甚至可以利用檢查來辨識這樣的subtour inequalities：見參考[7]瞭解這樣的方法用在aircraft mission planning所產生的TSP變體。我們用“cutting plane algorithm”來解多個TSP實例以求最佳性，將數值maxrounds為一個介於0、2之間的整數，這取決於我們希望加強MTZ公式到什麼樣的程度。

1. 讓整數規劃公式僅包含分配約束式，而且$k=1$
2. $\text{while } k \leq \text{ maxrounds}$
* (2a)解當前公式上的整數規劃。假設最佳解包含$r$個subtours，$S_1,..S_r$
* (2b)如果$r=1$，停止；這對TSP而言是最佳解了。否則，增加最多1000個subtour約束式到公式中，其中$S$是多個$S_i$集合的聯集，且$\vert S \vert \leq \lfloor n/2 \rfloor$。設置$k=k+1$
$\text{end while}$
3. 增加arc constraints到公式中，將線性規劃解到最佳。

:::

:::info
We used a simple implementation of step 2b: we output the $(i,j)$pairs corresponding to the nonzero $x_{ij}$ values into a file, then ran a MATLAB routine to generate the required constraints. These were then pasted into the formulation. For example, suppose that the number of cities is 10, and the arcs corresponding to the variables at 1 are as shown in Figure 2. The nontrivial parts (i.e., excluding input, output, and obvious initializations) of the MATLAB code are given in Figure 3. The code works as follows:
* The first part constructs the list of subtours from the list of arcs. In the example, it will create the list $\left\{1,4,6\right\},\left\{2,3,8\right\},\left\{5,7\right\},\left\{9,10\right\}$.
* The second part constructs all appropriate subsets of nodes in the variable $S$, and the index-pairs corresponding to arcs within $S$, in the variable arcs in $S$
:::

:::success
我們使用上面(2b)的簡單實現：我們輸出關於非零(nonzero)$x_{ij}$的$(i,j)$ pairs的值到一個檔案，然後執行MATLAB程序來產生需求的約束式。然後把這些約束式貼到公式裡面。舉例來說，假設城市的數量是10，然後關於變數在1的時候的arcs(弧)如Figure 2所示。MATLAB程式碼非顯然的部份(即，排除輸入、輸出與初始化)給出在Figure 3。程式碼工作如下：
* 第一部份從弧的列表中構造subtours的列表。在範例中，它會建立$\left\{1,4,6\right\},\left\{2,3,8\right\},\left\{5,7\right\},\left\{9,10\right\}$
* 第二部份構造變數$S$中所有適合的節點的子集合以及關於$S$內的arcs的索引對(index-pairs)(在$S$裡面的變數arcs中)
:::

:::info
Fig. 2 A solution with four subtours.
:::

:::info
The code works with all IP solvers that have a “reasonable” user interface: all we need to do is output the index-pairs corresponding to the variables at 1 and paste the file containing the generated constraints into the solver’s input. After every paste operation the IP must be resolved from scratch. Most of the time is taken up by solving the final formulation, i.e., the IP with the subtour- and arc-constraints. The IPs encountered during the cutting phase solve very quickly, and the running time of the MATLAB program is negligible.
:::

:::success
這程式碼適用於有著"合理的"使用者界面的所有整數規劃解答器：我們要做的就是輸出變數在1的時候的索引對(index-pairs)，然後將包含產生的約束式文件貼到解答器的輸入。在每一次貼上操作之後，整數規劃會重新求解。多數的時間是花在解最後的公式，也就是具有subtour與arc-contraints的整數規劃。在切割階段遇到的整數規劃求解速度很快，而MATLAB程式的執行時間也可以忽略不計。
:::

:::info
We tested this method on six relatively small but nontrivial TSP instances from the TSPLIB library [10]. The problem parameters are given in Table 1. The last two are symmetric instances, in which cij = cji for all i, j pairs. (Symmetric TSPs are usually formulated on an undirected graph using edge-variables; however, with these variables the MTZ formulation has no compact size variant; see [8].)
:::

:::success
我們從TSPLIB libray[10](MATLAB的套件?)中找了六個相對較小但非顯然的TSP實例。Table 1給出了這個問題的參數。最後兩個對稱實例，其中對所有的$i, j$ pairs而言$c_{ij}=c_{ji}$。(對稱的TSPs通常在無向圖上以edge-variables來表示；但是，使用這些變數，在MTZ上就沒有緊緻的大小變化，見[8])
:::

:::info
In Table 2 we give the running times in seconds and the number of branch-andbound nodes needed to solve the MTZ formulation to optimality, depending on how much it was strengthened with subtour inequalities. (We do not report the IP solution times during the cutting phase, nor the time for the constraint generation.) We used the CPLEX 6.5 IP solver run from within the AMPL modeling language, with default branching strategy and a memory limit of 150 MB, on a 337 MHz machine running Sun Solaris. We note that CPLEX was not able to generate any cuts, and that none of the successful runs used more than 100 MBs of memory.
:::

:::success
在Table 2中，我們以秒為單位給出執行時間，以及解MTZ公式到最佳化所需要的branch-and-bound的節點數量，這取決於subtor inequalities對其加強的程度。(我們沒有報告切割階段在整數規劃求解的時間，也沒有約束式生成的時間)我們使用CPLEX 6.5整數規劃解答器，以AMPL modeling language，Sun Solaris，337MHz機器，限制記憶體150MB，預設branching strategy。我們注意到，CPLEX無法生成任何的切割，而且沒有成功的執行使用超過100MBs的記憶體。
:::

:::info
The symmetric instances tend to be harder to solve, as the IP solutions during the cutting phase contain many small (mostly size 2) subtours. Therefore, there are more violated subtour constraints, and due to memory restrictions we cannot add all of them to the formulation (we add at most 1000). For the symmetric instances, we can consider the assignment constraints with all the inequalities $x_{ij}+x_{ji} \leq 1$ as the formulation with 0 rounds (i.e., we can add all subtour constraints where $S$ is of size 2 at the beginning). This way they can be solved with one fewer round of cuts, but the solution times will usually be greater than for asymmetric instances of comparable size.
:::

:::success
對稱的實例通常更難解，因為在切割階段的整數規劃求解包含很多小的subtours(多數大小為2)。因此，存在更多違反subtor約束式，也由於記憶體限制，我們無法所有的subtour約束式加到公式中(我們最多加1000個)。對於對稱實例來說，我們可以考慮將所有不等式$x_{ij}+x_{ji} \leq 1$的分配約束式視為有著0 rounds的形式(我們可以所有的subtor約束式，其中$S$的起始大小為2)。這樣的方法可以少1 round的切割來解，但求解的時間通比同等大小的不等對稱實例還要來的久。
:::