Compact formulations of the Steiner Traveling Salesman Problem and related problems

The Steiner Traveling Salesman Problem (STSP) is a variant of the TSP that is particularly suitable when routing on real-life road networks. The standard integer programming formulations of both the TSP and STSP have an exponential number of constraints. On the other hand, several compact formulations of the TSP, i.e., formulations of polynomial size, are known. In this paper, we adapt some of them to the STSP, and compare them both theoretically and computationally. It turns out that, just by putting the best of the formulations into the CPLEX branch-and-bound solver, one can solve instances with over 200 nodes. We also briefly discuss the adaptation of our formulations to some related problems.     

The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm

A ring star in a graph is a subgraph that can be decomposed into a cycle (or ring) and a set of edges with exactly one vertex in the cycle. In the minimum ring-star problem (mrsp) the cost of a ring star is given by the sum of the costs of its edges, which vary, depending on whether the edge is part of the ring or not. The goal is to find a ring-star spanning subgraph minimizing the sum of all ring and assignment costs. In this paper we show that the mrsp can be reduced to a minimum (constrained) Steiner arborescence problem on a layered graph. This reduction is used to introduce a new integer programming formulation for the mrsp. We prove that the dual bound generated by the linear relaxation of this formulation always dominates the one provided by an early model from the literature. Based on our new formulation, we developed a branch-and-cut algorithm for the mrsp. On the primal side, we devised a grasp heuristic to generate good upper bounds for the problem. Computational tests with these algorithms were conducted on a benchmark of public domain. In these experiments both our exact and heuristics algorithms had excellent performances, noticeably in dealing with instances whose optimal solution has few vertices in the ring. In addition, we also investigate the minimum spanning caterpillar problem (mscp) which has the same input as the mrsp and admits feasible solutions that can be viewed as ring stars with paths in the place of rings. We present an easy reduction of the mscp to the mrsp, which makes it possible to solve to optimality instances of the former problem too. Experiments carried out with the mscp revealed that our branch-and-cut algorithm is capable to solve to optimality instances with up to 200 vertices in reasonable time.     

Improved bounds for the traveling umpire problem: A stronger formulation and a relax-and-fix heuristic

Given a double round-robin tournament, the traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during the tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too often. We strengthen a known integer programming formulation for the TUP and use it to implement a relax-and-fix heuristic that improves the quality of 24 out of 25 best-known feasible solutions to instances in the TUP benchmark. We also improve all best-known lower bounds for those instances and, for the first time, provide lower bounds for instances with more than 16 teams.     

The Attractive Traveling Salesman Problem

In the Attractive Traveling Salesman Problem the vertex set is partitioned into facility vertices and customer vertices. A maximum profit tour must be constructed on a subset of the facility vertices. Profit is computed through an attraction function: every visited facility vertex attracts a portion of the profit from the customer vertices based on the distance between the facility and customer vertices, and the attractiveness of the facility vertex. A gravity model is used for computing the profit attraction. The problem is formulated as an integer non-linear program. A linearization is proposed and strengthened through the introduction of valid inequalities, and a branch-and-cut algorithm is developed. A tabu search algorithm is also implemented. Computational results are reported.     

Some formulations for the group steiner tree problem

The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V(G) and a cost c(e) for each edge of G, finding a minimum-cost subtree that connects at least one vertex from each R∈R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems.     

A mixed integer linear programming formulation of the maximum betweenness problem

This paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

Certification of an optimal TSP tour through 85,900 cities

We describe a computer code and data that together certify the optimality of a solution to the 85,900-city traveling salesman problem pla85900, the largest instance in the TSPLIB collection of challenge problems.     

Solving the asymmetric traveling purchaser problem

The Asymmetric Traveling Purchaser Problem (ATPP) is a generalization of the Asymmetric Traveling Salesman Problem with several applications in the routing and the scheduling contexts. This problem is defined as follows. Let us consider a set of products and a set of markets. Each market is provided with a limited amount of each product at a known price. The ATPP consists in selecting a subset of markets such that a given demand of each product can be purchased, minimizing the routing cost and the purchasing cost. The aim of this article is to evaluate the effectiveness of a branch-and-cut algorithm based on new valid inequalities. It also proposes a transformation of the ATPP into its symmetric version, so a second exact method is also presented. An extensive computational analysis on several classes of instances from literature evaluates the proposed approaches. A previous work () solves instances with up to 25 markets and 100 products, while the here-presented approaches prove optimality on instances with up to 200 markets and 200 products. Partially supported by “Ministerio de Ciencia y Tecnología” (TIC2003-05982-C05-02), and by Vicerrectorado de Investigación y Desarrollo Tecnológico de la Universidad de La Laguna.     

A computational evaluation of a general branch-and-price framework for capacitated network location problems

The purpose of this paper is to illustrate a general framework for network location problems, based on column generation and branch-and-price. In particular we consider capacitated network location problems with single-source constraints. We consider several different network location models, by combining cardinality constraints, fixed costs, concentrator restrictions and regional constraints. Our general branch-and-price-based approach can be seen as a natural counterpart of the branch-and-cut-based commercial ILP solvers, with the advantage of exploiting the tightness of the lower bound provided by the set partitioning reformulation of network location problems. Branch-and-price and branch-and-cut are compared through an extensive set of experimental tests.     

A branch-and-cut algorithm for solving the Non-Preemptive Capacitated Swapping Problem

This paper models and solves a capacitated version of the Non-Preemptive Swapping Problem. This problem is defined on a complete digraph G=(V,A), at every vertex of which there may be one unit of supply of an item, one unit of demand, or both. The objective is to determine a minimum cost capacitated vehicle route for transporting the items in such a way that all demands are satisfied. The vehicle can carry more than one item at a time. Three mathematical programming formulations of the problem are provided. Several classes of valid inequalities are derived and incorporated within a branch-and-cut algorithm, and extensive computational experiments are performed on instances adapted from TSPLIB.     

A New Memetic Algorithm for the Asymmetric Traveling Salesman Problem

This paper introduces a new memetic algorithm specialized for the asymmetric instances of the traveling salesman problem (ATSP). The method incorporates a new local search engine and many other features that contribute to its effectiveness, such as: (i) the topological organization of the population as a complete ternary tree with thirteen nodes; (ii) the hierarchical organization of the population in overlapping clusters leading to the special selection scheme; (iii) efficient data structures. Computational experiments are conducted on all ATSP instances available in the TSPLIB, and on a set of larger asymmetric instances with known optimal solutions. The comparisons show that the results obtained by our method compare favorably with those obtained by several other algorithms recently proposed for the ATSP.     

A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem

We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research was devoted to modeling and reformulation approaches. In this paper we carry out a polyhedral study for the cubic integer programming formulation by establishing the dimension of the integer hull as well as of faces induced by model inequalities. Moreover, we introduce a new class of inequalities and show that they are facet-defining. Finally, we evaluate the impact of these inequalities on the linear programming bounds.     

A new lower bound for the linear knapsack problem with general integer variables

It is well known that the linear knapsack problem with general integer variables (LKP) is NP-hard. In this paper we first introduce a special case of this problem and develop an O(n) algorithm to solve it. We then show how this algorithm can be used efficiently to obtain a lower bound for a general instance of LKP and prove that it is at least as good as the linear programming lower bound. We also present the results of a computational study that show that for certain classes of problems the proposed bound on average is tighter than other bounds proposed in the literature.     

A Tabu Search Approach for the Prize Collecting Traveling Salesman Problem

The Prize Collecting Traveling Salesman Problem is a generalization of the Traveling Salesman Problem. A salesman collects a prize for each visited city and pays a penalty for each non visited city. The objective is to minimize the sum of the travel costs and penalties, but collecting a minimum pre-established amount of prizes. This problem is here addressed by a simple, but efficient tabu search approach which had improved several upper bounds of the considered instances.     

Transgenetic algorithm for the Traveling Purchaser Problem

In this paper an evolutionary algorithm is presented for the Traveling Purchaser Problem, an important variation of the Traveling Salesman Problem. The evolutionary approach proposed in this paper is called transgenetic algorithm. It is inspired on two significant evolutionary driving forces: horizontal gene transfer and endosymbiosis. The performance of the algorithm proposed for the investigated problem is compared with other recent works presented in the literature. Computational experiments show that the proposed approach is very effective for the investigated problem with 17 and 9 new best solutions reported for capacitated and uncapacitated instances, respectively.     

A new variable reduction technique for convex integer quadratic programs

Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems.     

Optimal placement of stereo sensors

Autonomous wireless devices such as sensor nodes and stereo cameras, due to their low cost of operation coupled with the potential for remote deployment, have found a plethora of applications ranging from monitoring air, soil and water to seismic detection and military surveillance. Typically, such a network spans a region of interest with the individual nodes cooperating to detect events and disseminate information. Given a deployment of sensors and targets over a region, a sensor pairing is desired for each target that optimizes the coverage under certain constraints. This problem can be modeled as an integer programming problem and solved using branch-and-cut. For larger problems, it is necessary to limit the number of variables, and a GRASP routine was developed for this purpose. Valid cutting planes are developed and computational results presented. Research supported in part by NSF grant numbers DMS–0317323 and CMS–0301661.