Cutting-Plane Algorithm
The idea
of the cutting plane algorithm is to add a set of constraints to the assignment
problem that prevent the formation of a subtour. The additional constraints are
defined as follows. In an n-city
situation, associate a continuous variable uj (≥ 0) with cities 2, 3, ... , and n.
Next, define the required set of additional constraints as
These
constraints, when added to the assignment model, will automatically remove all
subtour solutions.
Example
9.3-5
Consider
the following distance matrix of a 4-city TSP problem.
The
associated LP consists of the assignment model constraints plus the additional
constraints in the table below. All xij = (0, 1)
and all uj ≥ 0.
This
corresponds to the tour solution 1-2-3-4-1. The solution satisfies all the
additional constraints in uj (verify!).
To
demonstrate that subtour solutions do not satisfy the additional constraints,
consider (1-2-1,3-4-3), which corresponds to x12 = x21 = 1, x34 = x43 = 1. Now,
consider constraint 6 in the tableau above:
Substituting
x43 = 1, u3 = 2, u4 = 3 yields 5 ≤ 3, which
is impossible, thus disallowing x43
= 1 and subtour 3-4-3.
The
disadvantage of the cutting-plane model is that the number of variables grows
exponentially with the number of cities, making it difficult to obtain a
numeric solution for practical situations. For this reason, the B&B
algorithm (coupled with the heuristic) may be a more feasible alternative for
solving the problem.
AMPL
Moment
Figure
9.14 provides the AMPL model of the cutting-plane algorithm (file
amplEx9.3-5.txt). The data of the 4-cityTSP of Example 9.3-5 are used to drive
the model. The for-mulation is straightforward: The fIrst two sets of
constraints define the assignment model associated with the problem, and the
third set represents the cuts needed to re-move subtour solutions. Notice that
the assignment-model variables must be binary and that option solver cplex;
must precede solve; to ensure that the obtained so-lution is integer.
The for
and if - then statements at the bottom of the model are used to present the out-put
in the following readable format:
PROBLEM SET 9.3 D
1. An automatic guided vehicle (AGV) is used to deliver mail to 5
departments located on a factory floor. The trip starts at the mail sorting
room and makes the delivery round to the different departments before returning
to the mailroom. Using the mailroom as the origin (0,0), the (x, y) locations of the delivery spots are (10,30), (10, 50), (30, 10),
(40,40), and (50,60) for departments 1 through 5, respectively. All distances
are in meters. The AGV can move along horizontal and vertical aisles only. The
objective is to minimize the length of the round trip.
Formulate the problem as a TSP, including the cuts.
2. Write down the cuts associated with the following TSP:
3. AMPL experiment. Use AMPL to solve the following TSP problem by the cutting plane algorithm.
a) Problem 2, Set 9.3a.
b)
Problem 3, Set 9.3a.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.