We solve the QSTSP using a branch-and-cut algorithm. A branch-and-cut al-gorithm is a branch-and-bound alal-gorithm where the bounds are obtained by solving the LP-relaxation of the problem, possibly including some additional cuts. We have implemented the branch-and-cut algorithm using the Branch-Cut-and-Price framework (BCP) which is part of COIN [1]. BCP is, as its name indicates, a framework for developing branch-cut-and-price algorithms.
The choice of using BCP instead of implementing from scratch was made to speed up development. We have used BCP standard setups and classes when-ever possible. The branch-and-cut algorithm is shown in Figure B.1.
An initial feasible solution is generated by selecting the best solution from the two heuristics described in Section B.4. The algorithm maintains a set of subproblems, initially containing the root node problem only. The root node problem consists of (1), (2), bounds on variables and one of the budget con-straints (10) or (11). If constraint (11) is used, we also include (15).
A subproblem is selected and the LP-relaxation of the subproblem including additional cuts are solved. If any violated cuts can be determined, the cuts are added to the subproblem and the subproblem is resolved. This is done until no more violated cuts can be determined. We generate (3), (13), and the GSECs (5). Generation of constraints (3) and (13) is done by checking whether any of the constraints are violated. Since there are (n2−n)/2 of each of those, the computation time isO(n2). Generation of GSECs is described in the following section.
B.3 Branch-and-Cut Algorithm 67
Incumbent = A feasible solution obtained heuristically.
Set of subproblems ={Root node problem}
whileSet of subproblems6=∅
Select subproblem and remove it fromSet of subproblems do
Solve LP-relaxation of subproblem including generated cuts Generate and add violated cuts
whileNew cuts added
LetObj val= objective value of LP-relaxation
if LPsolution is feasible, hence integerandObj val>Incumbent: Update incumbent: Incumbent=Obj val
else if Obj val≤Incumbentorsubproblem is infeasible:
Continue else Branch:
Add two subproblems toSet of subproblems end while
Figure B.1: The branch-and-cut algorithm
Given a bound on the subproblem, three possibilities exists. 1) The subproblem is feasible, hence a candidate solution has been identified. If the candidate is better than the incumbent, the candidate takes the place of the incumbent. 2) The bound is worse than the incumbent. The subproblem is not considered any further, since it will not lead to any better solutions. 3) Nothing can be determined, so we have to branch. Create two new subproblems and continue.
Subproblems are considered depth first. This allows for reuse of the obtained LP-tableau in the following iteration. Variable branching is applied. Note that the z variables are integer if the y variables are integer, thus the z variables are not considered for branching. The variable to branch on is determined as follows. First the y variables are considered. If any fractionaly variable exists, they variable with a value closest to 1/2 is chosen. If no fractionaly variable exists, the x variables are considered. Similarly the x variable with a value closest to 1/2 is chosen. Two new subproblems are created. In one subproblem we set the chosen variable equal to one and in the other subproblem we set the chosen variable equal to zero. The subproblem with the chosen variable equal to one is considered first.
68 Appendix B
B.3.1 Separation of GSECs
Separation of GSECs is due to [7] which presents an optimal and a heuristic separation routine. Optimal separation can be achieved in O(n4) time, but proves to be ineffective for GTSP. For completeness the optimal separation routine is, however, described.
Assume (x∗e, yi∗, z∗e) is the value of an optimal solution to the LP-relaxation of the problem. Set up an undirected graph with nnodes and edge capacities equal tox∗e.
Optimal separation of GSECs is best described based on constraints (9). Recall the interpretation of the constraints: If a node is selected on both sides of a cut, then at least two edges crossing the cut must be selected. Thus separation can be done by for all pairs of nodesk, lcomputing a minimum cut separating k andl. Given the minimum cut, i.e. a set of nodesS, evaluate (9) and check whether it is violated. This can be achieved in O(n5) time, since a minimum cut can be computed inO(n3) time andO(n2) pairs of nodes exists.
By using the following observation, the computation time can be reduced to O(n4). For a given S0 ⊂V, the most violated cut is obtained fork0 ∈S0 and l0 6∈ S0 such that k0 = arg maxi∈S0{yi∗} and l0 = arg maxi6∈S0{yi∗}. Assume without loss of generality thaty∗k0 ≥y∗l0. For any GSEC defined by S,k, andl, either k0 ∈S or k0 6∈S. But in that case one of the most violated GSECs will havek =k0 if k0 ∈ S or l =k0 if k0 6∈ S. Thus it suffices to pick any such k0 and consider pairs for this k0 and all other nodesl. Thus onlyO(n) pairs need to be considered and thus the complexity is onlyO(n4) in total.
In summary the separation algorithm is defined as follows. Pick a nodeksuch thatk= arg maxi∈V{yi∗}. For all nodesl6=kcompute a minimum cut between k and l. Evaluate (9) to check whether the cut is violated and if so add it in the form of (5). Thus up ton−1 cuts may be added.
Computational experiments show that substantial time is spent on optimal sep-aration, however, the most important problem is that the generated cuts do not span the graph [7]. This is explained in the following. Suppose that three disjoint setsSa ⊂V, a= 1,2,3, exist for whichδ(Sa) = 0. Assume the nodek, chosen during optimal separation, is in S1. Then at least two GSECs will be generated withS=S1 andl∈S2or l∈S3. The cut withS=S2,k∈S2, and l∈S3willnotbe generated. This last cut may be needed to get the best bound, and thus may have to be generated in later iterations. Thus additional iterations may be needed, thereby increasing the computation time. An alternative is to use heuristic separation as described in [7] and in the following.