Books in black and white
 Main menu Share a book About us Home
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

# Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): îombinatorialoptimi2012.pdf Previous << 1 .. 141 142 143 144 145 146 < 147 > 148 149 150 151 152 153 .. 156 >> Next we will obtain a way of treating side constraints and answering some of the questions which have been posed in Section 14.2.
14.4 Travelling Salesman Tours as Penalized Assignments
When a tsp is formulated as a linear assignment problem, it is well known that to an optimal solution of the latter does not necessarily correspond a
394 Franco Giannessi and Bernardo Nicoletti
Hamiltonian circuit of G. It can be shown that, either by suitably modifying the objective function, or by setting to zero some variables, a Hamiltonian circuit can be obtained as the optimal solution to the assignment problem.
Consider the real variables p.,, i = 1,..., n, associated with the vertices
Nu , Nn, and binary variables ai( e B = {0,1}, associated with
the arcs of G*; set
V- = Or,    , M-n) ¨ = (¨12,    , ¨In,    , ¨n.n-l)
and consider the set
 e j.R": - s=0, and
--------------*-3= l,if a = l[.
n I
Another n(n  l)-uple of binary values
0 =(012,    , Pin, ?   , Pn,n-l) P,j 6 5
will be considered. Let M be a large positive real, and consider the
penalized distances!
' C;y +(1 if
Cij(aiy)-? M if i =; = 0, 1,.. ., n
. ciy otherwise
Finally the binary vector
b = (b0= 1, bu ..., bn), k<=B
is introduced.
Now consider the problem
(14.1a)
(14.1b)
(14.1c) (14.Id) (14.le)
min ] z (x,a) ^ Cyy (oci(-) -V,, |
I i,j =0 -*
iU= K i = 0,1, . .., n
1=0
b j = 0,1,.. ., n
i=0
jc.^0 i, ]=0, 1,..., n
/A Jo 5
+ It is assumed that G has no loops, otherwise trivial variants are necessary.
The Crew Scheduling Problem: A Travelling Salesman Approach 395
and call it ^(a,/3, fa); call the corresponding minimum and an optimal solution Z(a, (3, b) and x(a, /3, b), respectively. Moreover, denote by R((3,b) the feasible region of (14.1), i.e. the polyhedron defined by (14.1b)-(14.1e).
We remark that a and /3 play the same role: a = 0 penalizes arc (i, j), so that one expects Xy = 0 in an optimal solution of (14.1); the same fact is obtained from /3y = 0. Thus, such two kinds of penalties will be used alternatively; their introduction is motivated by the need to obtain different results. Thus, if eh denotes a vector of h unit components, the general problem (14.1) will be considered alternatively in the particular cases as:
0>(a, en<n_1); b) and Pie^£, /3, b).
We also note that fa, = 0 implies x,, = x^ = 0, i = 0, 1,..., n, in a feasible solution of (14.1). This means that every path through Nt is considered infeasible, i.e. N, is cancelled, and the tsp is considered on the remaining graph. Thus
h=Ifa, (h 25 1)
J=1
is the number of vertices of G which it is legal to visit, so that a constraint of the form I"=1fa, & h imposes the need to visit at least h vertices in order to have a feasible circuit. When fa = n all the vertices of G must be visited, and the problem becomes the classical tsp.
First we will study problemt 3P(a, en(_lj, e) with the aim of characterizing a Hamiltonian circuit.
Remark that an optimal solution of 3P(a, 1, 1) has n +1 elements equal to 1, and n  1 of them are Xjj having I^jV/sSh. If aeB'1(n_1) has been chosen having more than (n -1)2 elements equal to zero, then for at least an arc (i,j), with l=si^/=?n, we have atl = 0 and in an optimal solution of (14.1a) is Xj, = 1, so that the minimum in ^(a, 1,1) is 5*M, and it does not correspond to a total distance of a path of G. For this reason we assume that a satisfies the constraint (assuming that n > 2)
Z <*;,- = n-1. (14-2)
1 5* j
Even if (14.2) is satisfied, there is not necessarily a feasible solution to problem i?(a, 1,1) with total distance less than M. In fact, if there are n - 1 of the a,, equal to 1, and if they have the same row index or the same column index, then there is no feasible solution of Sf(a, 1,1) with total distance <M. For this reason we are led to consider the set of all a e Bn("_1)
t For the sake of simplicity, and without fear of confusion, e,lfrl._ri and e will be replaced symbolically by 1, when considered as arguments of (*, *, *), R(*, *), Z(*. *, *), x(*, *, *).
396
Franco Giannessi and Bernardo Nicoletti
which satisfy (14.2) and which correspond to intersections of different rows and different columns. Let this set be Ht:
H1 = {aeBn(r,~1): ... =aj.1 = 1; I* il5..., is; h = k+1;
s = 1,..., n -1; al(, = 0, otherwise}.
It is easy to show that S'(a, 1,1) has feasible solutions with total distance less than M, iff a e Ht.
Unfortunately, the set Hl does not characterize the set of problems 9P(a, 1,1) which have optimal solutions corresponding to Hamiltonian circuits. To obtain this we consider the set of all a efl"1"-11 and such that
/*(¨)# 0; (14.3)
Theorem 14.1 Let a e Hl. Every Hamiltonian circuit of G corresponds to an optimal solution of 2P(ot, 1, 1), iff ae H2.
Proof. Sufficiency. Let x* be an optimal solution of SP(a, 1,1) which always exists. (14.1b)-(14.1d) ensure that, for every vertex, there is only one arriving arc; (14.1c)-(14.1d) that there is only one departing arc. If follows that the set of arcs corresponding to the nonzero elements of x* form a circuit, which is not necessarily Hamiltonian, i.e. it may be composed of subcircuits which do not contain N0. Assume that there are at least two such subcircuits, so that there exists a circuit defined by fc < n vertices different from N0. Call 3 the set of arcs (/, j) of indices of the k variables corresponding to such a circuit. We have Previous << 1 .. 141 142 143 144 145 146 < 147 > 148 149 150 151 152 153 .. 156 >> Next 