Given an undirected graph and two numbers q and b , the Capacitated Vertex Separation Problem (CVSP) looks for a vertex subset of minimum cardinality such that the connected components in the subgraph generated after the vertex removal can be packed into no more than q bins of cardinality at most b. This problem has been studied in graph theory, and most of the success in solving it is due to the hypothesis that the objective function minimizes the number of deleted vertices, that is, each node removal contributes identically to the objective function. In our work, this hypothesis is relaxed so each vertex has a cost and a weight, and the problem aims to minimize the total cost of the removed vertices while the total vertex weight in each bin is within the given capacity b , still limiting the number of bins to at most q. We introduce several mathematical formulations for the new problem, called the Generalized Capacitated Vertex Separator Problem (GCVSP), and analyze the performance of algorithms based on such formulations.

Transportation problems are essential in commercial logistics and have been widely studied in the literature during the last decades. Many of them consist in designing routes for vehicles to move commodities between locations. This article approaches a pickup-and-delivery single-vehicle routing problem where there is susceptibility to uncertainty in customer requests. The probability distributions of the requests are assumed to be known, and the objective is to design an a priori route with minimum expected length. The problem has already been approached in the literature, but through a heuristic method. This article proposes the first exact approach to the problem. Two mathematical formulations are proposed: one is a compact model (i.e. defined by a polynomial number of variables and constraints); the other one contains an exponential number of inequalities and is solved within a branch-and-cut framework. Computational results show the upsides as well as the breakdowns of both formulations.

This article considers the problem of designing a two‐level network where the upper level consists of a backbone ring network connecting the so‐called hub nodes, and the lower level is formed by access ring networks that connect the non‐hub nodes to the hub nodes. There is a fixed cost for each type of link, and a facility opening cost associated to each hub. The number of nodes in each access ring is bounded, and the number of access rings connected to a hub is limited to , thus resulting in a ring/ ‐rings topology. The aim is to decide the hubs to open and to design the backbone and access rings to minimize the installation cost. We propose a mathematical model, give valid inequalities, and describe a branch‐and‐cut algorithm to solve the problem. Computational results show the algorithm is able to find optimal solutions on instances involving up to 40 nodes within a reasonable time. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 130–140 2016

Abstract– The “multi‐commodity Pickup‐and‐Delivery Traveling Salesman Problem” (m‐PDTSP) is a generalization of the well‐known “Traveling Salesman Problem” in which cities correspond to customers providing or requiring known amounts of m different products, and the vehicle has a known capacity. Each customer must be visited exactly once by the vehicle serving the demands of the different products while minimizing the total travel distance. It is assumed that a unit of a product collected from a customer can be supplied to any other customer that requires this product. We introduce a mixed integer linear programming model for the m‐PDTSP, discuss a classical decomposition technique, describe valid inequalities to strengthen the linear programming relaxation of the model, and detail separation procedures to develop a branch‐and‐cut procedure. Computational experiments on randomly generated instances with up to 30 customers, three products, and small vehicle capacities are analyzed. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 46–59 2014

Abstract This article analyzes inequalities derived by projecting out the flow variables of a single‐commodity flow model for a vehicle routing problem. These inequalities are called reverse multistar (RMS) inequalities and are related to the MS inequalities analyzed and used in other articles. Although the MS RMS inequalities are irrelevant for some vehicle routing problems, in others they are fundamental. The article presents a vehicle routing problem in which the RMS are of interest. It is called the vehicle routing problem with lower and upper bound capacities (LU‐VRP). It concerns a vehicle routing problem with one depot and a homogeneous fleet of vehicles. All the customers have a unit demand, and there are upper and lower bounds on the demand covered by each vehicle. New families of inequalities are derived by strengthening the RMS inequalities. Computational experiments show that the new inequalities are useful when solving LU‐VRP instances. The experiments are based on variations of symmetric and asymmetric VRP library (VRPLIB) instances with up to 100 customers. The constraint on a minimum number of customers served in each route is implicit in the unit‐demand capacitated vehicle routing problem with a fixed number of vehicles. Therefore, the article also evaluates the impact of using the lower bound inequalities developed in the context of this variant. It is still unknown whether the new inequalities can help solve it or not. Our theoretical analysis suggests that one of the families of developed inequalities is not implied by other standard inequalities. This prompts us to pursue studies in the search for other families of lower bound based inequalities for this variant. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Aphylogeny is an unrooted binary tree that represents the evolutionary relationships of a set of n species. Phylogenies find applications in several scientific areas ranging from medical research, to drug discovery, to epidemiology, to systematics, and to population dynamics. In such applications, the available information is usually restricted to the leaves of a phylogeny and is represented by molecular data extracted from the analyzed species, such as DNA, RNA, amino acid, or codon fragments. On the contrary, the information about the phylogeny itself is generally missing and is determined by solving an optimization problem, called the phylogeny estimation problem (PEP), whose versions depend on the criterion used to select a phylogeny from among plausible alternatives. In this paper, we investigate a recent version of the PEP, called the balanced minimum evolution problem (BMEP). We present a mixed-integer linear programming model to exactly solve instances of the BMEP and develop branching rules and families of valid inequalities to further strengthen the model. Our results give perspective on the mathematics of the BMEP and suggest new directions on the development of future efficient exact approaches to solutions of the problem.

Abstract This article considers the network design problem that searches for a minimum‐cost way of installing capacities on the edges of a network to simultaneously route a flow from a given access point to a subset of nodes representing customers with positive demands. We first consider compact and exponential‐sized Mixed Integer Programming (MIP) formulations of the problem and provide their theoretical and computational comparison. We also consider a stronger disaggregated flow formulation. To solve the problem in practice, we project out the flow variables and generate Benders cuts within a branch‐and‐cut framework. To the best of our knowledge, the combination of Benders approach and this specific disaggregation has not been considered so far. In an extensive computational study, we compare the performance of compact MIP models against a textbook implementation and several normalization variants of Benders decomposition. We introduce a set of 32 real‐world instances and use these, together with 64 other instances from the literature, to test our approaches. The results show that our branch‐and‐cut approach outperforms the best performing compact formulation leading to the best exact algorithm today for solving the considered dataset. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Minimum linear arrangement is a classical basic combinatorial optimization problem from the 1960s that turns out to be extremely challenging in practice. In particular, for most of its benchmark instances, even the order of magnitude of the optimal solution value is unknown, as testified by the surveys on the problem that contain tables in which the best-known solution value often has one more digit than the best-known lower bound value. In this paper, we propose a linear programming-based approach to compute lower bounds on the optimum. This allows us, for the first time, to show that the best-known solutions are indeed not far from optimal for most of the benchmark instances.

Abstract In recent years, there has been an increased literature on so‐called generalized network design problems (GNDPs), such as the generalized minimum spanning tree problem and the generalized traveling salesman problem. In a GNDP, the node set of a graph is partitioned into “clusters,” and the feasible solutions must contain one node from each cluster. Up to now, the polyhedra associated with different GNDPs have been studied independently. The purpose of this article is to show that it is possible, to a certain extent, to derive polyhedral results for all GNDPs simultaneously. Along the way, we point out some interesting connections to other polyhedra, such as the quadratic semiassignment polytope and the boolean quadric polytope. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract In the Traveling Salesman Problem with Pickup and Delivery (TSPPD) a single vehicle must serve a set of customer requests, each defined by an origin location where a load must be picked up, and a destination location where the load must be delivered. The problem consists of determining a shortest Hamiltonian cycle through all locations while ensuring that the pickup of each request is performed before the corresponding delivery. This article addresses a variant of the TSPPD in which pickups and deliveries must be performed according to a Last‐In First‐Out (LIFO) policy. We propose three mathematical formulations for this problem and several families of valid inequalities which are used within a branch‐and‐cut algorithm. Computational results performed on test instances from the literature show that most instances with up to 17 requests can be solved in less than 10 min, whereas the largest instance solved contains 25 requests. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract A basic problem in molecular biology is to rebuild phylogenetic trees (PT) from a set of DNA or protein sequences. Among different criteria used for this purpose, the minimum evolution criterion is an optimality based criterion aiming to rebuild PT characterized by a minimal length. This problem is known to be 𝒩𝒫‐hard. We introduce in this article some mixed integer programming models, and we also study possible cuts and lower bounds for the optimal value. So far, the number of sequences that can be involved in optimal phylogenetic reconstruction is still limited to 10. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract This article concerns the “One‐commodity Pickup‐and‐Delivery Traveling Salesman Problem” (1‐PDTSP), in which a single vehicle of fixed capacity must either pick up or deliver known amounts of a single commodity to a given list of customers. It is assumed that the product collected from the pickup customers can be supplied to the delivery customers, and that the initial load of the vehicle leaving the depot can be any quantity. The problem is to find a minimum‐cost sequence of the customers in such a way that the vehicle's capacity is never exceeded. This article points out a close connection between the 1‐PDTSP and the classical “Capacitated Vehicle Routing Problem” (CVRP), and it presents new inequalities for the 1‐PDTSP adapted from recent inequalities for the CVRP. These inequalities have been implemented in a branch‐and‐cut framework to solve to optimality the 1‐PDTSP that outperforms a previous algorithm (Hernández‐Pérez and Salazar‐González, Discrete Appl Math 145 (2004), 126–139). Larger instances (with up to 100 customers) are now solved to optimality. The classical “Traveling Salesman Problem with Pickups and Deliveries” (TSPPD) is a particular case of the 1‐PDTSP, and this observation gives an additional motivation for this article. The here‐proposed algorithm for the 1‐PDTSP was able to solve to optimality TSPPD instances with up to 260 customers. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 258–272 2007

Finding a linear layout of a graph having minimum bandwidth is a combinatorial optimization problem that has been studied since the 1960s. Unlike other classical problems, the approach based on stating a suitable integer linear program and solving the associated linear-programming relaxation seems to be useless in this case. This makes it nontrivial to design algorithms capable of solving to optimality instances of reasonable size. In this paper, we illustrate a new simple lower bound on the optimal bandwidth and its extension within an enumerative algorithm, leading to integer linear-programming relaxations that can be solved efficiently and provide effective lower bounds if part of the layout is fixed. Keeping the integrality constraints in these relaxations is essential for this purpose. We show that the resulting method can solve to proven optimality 24 out of the 30 instances from the literature with less than 200 nodes, each in less than a minute on a personal computer. The new approach is also analyzed on randomly generated instances with up to 1,000 nodes. Moreover, we propose a method to compute the well-known density lower bound on the optimal bandwidth, which succeeds in finding this bound within minutes for most instances in the literature with up to 250 nodes.

Abstract In the Ring Star Problem, the aim is to locate a simple cycle through a subset of vertices of a graph with the objective of minimizing the sum of two costs: a ring cost proportional to the length of the cycle and an assignment cost from the vertices not in the cycle to their closest vertex on the cycle. The problem has several applications in telecommunications network design and in rapid transit systems planning. It is an extension of the classical location–allocation problem introduced in the early 1960s, and closely related versions have been recently studied by several authors. This article formulates the problem as a mixed‐integer linear program and strengthens it with the introduction of several families of valid inequalities. These inequalities are shown to be facet‐defining and are used to develop a branch‐and‐cut algorithm. Computational results show that instances involving up to 300 vertices can be solved optimally using the proposed methodology. © 2004 Wiley Periodicals, Inc.

In the Orienteering Problem (OP), we are given an undirected graph with edge weights and node prizes. The problem calls for a simple cycle whose total edge weight does not exceed a given threshold, while visiting a subset of nodes with maximum total prize. This NP-hard problem arises in routing and scheduling applications. We describe a branch-and-cut algorithm for finding an optimal OP solution. The algorithm is based on several families of valid inequalities. We also introduce a family of cuts, called conditional cuts, which can cut off the optimal OP solution, and propose an effective way to use them within the overall branch-and-cut framework. Exact and heuristic separation algorithms are described, as well as heuristic procedures to produce near-optimal OP solutions. An extensive computational analysis on several classes of both real-world and random instances is reported. The algorithm proved to be able to solve to optimality large-scale instances involving up to 500 nodes, within acceptable computing time. This compares favorably with previous published methods.

Abstract The symmetric Generalized Traveling Salesman Problem (GTSP) is a variant of the classical symmetric Traveling Salesman Problem, in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. A different version of the problem, called E‐GTSP, arises when exactly one node for each cluster has to be visited. Both GTSP and E‐GTSP are NP‐hard problems and find practical applications in routing, scheduling, and location‐routing. in this paper, we model GTSP and E‐GTSP as integer linear programs and study the facial structure of the corresponding polytopes. in a companion paper, Theresults described in this work have been used to design a branch‐and‐cut algorithm for the exact solution of instances up to 442 nodes.