Home | | **Resource Management Techniques** | Cutting Plane Algorithm - Traveling Salesperson Problem (TSP)

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.

**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 *u _{j}* (≥

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 *x _{ij}* = (0, 1)
and all

This
corresponds to the tour solution 1-2-3-4-1. The solution satisfies all the
additional constraints in *u _{j}* (verify!).

To
demonstrate that subtour solutions do not satisfy the additional constraints,
consider (1-2-1,3-4-3), which corresponds to *x _{12}* = x

Substituting
*x _{43}* = 1,

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.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Operations Research: An Introduction : Integer Linear Programming : Cutting Plane Algorithm - Traveling Salesperson Problem (TSP) |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.