Finding high-quality solutions to mixed-integer linear programming problems (MILPs) is of great importance for many practical applications. In this respect, the refinement heuristic local branching (LB) has been proposed to produce improving solutions and has been highly influential for the development of local search methods in MILP. The algorithm iteratively explores a sequence of solution neighborhoods defined by the so-called local branching constraint, namely, a linear inequality limiting the distance from a reference solution. For a LB algorithm, the choice of the neighborhood size is critical to performance. Although it was initialized by a conservative value in the original LB scheme, our new observation is that the "best" size is strongly dependent on the particular MILP instance. In this work, we investigate the relation between the size of the search neighborhood and the behavior of the underlying LB algorithm, and we devise a leaning-based framework for guiding the neighborhood search of the LB heuristic. The framework consists of a two-phase strategy. For the first phase, a scaled regression model is trained to predict the size of the LB neighborhood at the first iteration through a regression task. In the second phase, we leverage reinforcement learning and devise a reinforced neighborhood search strategy to dynamically adapt the size at the subsequent iterations. We computationally show that the neighborhood size can indeed be learned, leading to improved performances and that the overall algorithm generalizes well both with respect to the instance size and, remarkably, across instances.

Two-person interdiction games represent an important modeling concept for applications in marketing, defending critical infrastructure, stopping nuclear weapons projects, or preventing drug smuggling. We present an exact branch-and-cut algorithm for interdiction games under the assumption that feasible solutions of the follower problem satisfy a certain monotonicity property. Prominent examples from the literature that fall into this category are knapsack interdiction, matching interdiction, and packing interdiction problems. We also show how practically relevant interdiction variants of facility location and prize-collecting problems can be modeled in our setting. Our branch-and-cut algorithm uses a solution scheme akin to Benders decomposition based on a family of so-called interdiction cuts. We present modified and lifted versions of these cuts along with exact and heuristic procedures for the separation of interdiction cuts and heuristic separation procedures for the other versions. In addition, we derive further valid inequalities and present a new heuristic procedure. We computationally evaluate the proposed algorithm on a benchmark of 360 knapsack interdiction instances from literature, including 27 instances for which the optimal solution was not known. Our approach is able to solve each of them to optimality within about one minute of computing time on a standard PC (in most cases, within just seconds), and it is up to some orders of magnitude faster than any previous approach from the literature. To further assess the effectiveness of our branch-and-cut algorithm, an additional computational study is performed on 144 randomly generated instances based on 0/1 multidimensional knapsack problems.

We present an exact mixed-integer programming (MIP) solution scheme where a set-covering model is used to find a small set of first-choice branching variables. In a preliminary “sampling” phase, our method quickly collects a number of relevant low-cost fractional solutions that qualify as obstacles for the linear programming (LP) relaxation bound improvement. Then a set covering model is solved to detect a small subset of variables (a “backdoor,” in the artificial intelligence jargon) that “cover the fractionality” of the collected fractional solutions. These backdoor variables are put in a priority branching list, and a black-box MIP solver is eventually run—in its default mode—by taking this list into account, thus avoiding any other interference with its highly optimized internal mechanisms. Computational results on a large set of instances from the literature are presented, showing that some speedup can be achieved even with respect to a state-of-the-art solver such as IBM ILOG CPLEX 12.2.

The split closure has been proved in practice to be a very tight approximation of the integer hull formulation of a generic mixed-integer linear program. However, exact separation procedures for optimizing over the split closure have unacceptable computing times in practice; hence, many different heuristic strategies have been proposed in the last few years. In this paper we present a new overall framework for approximating the split closure that merges different ideas from the previous approaches. Computational results prove the effectiveness of the proposed procedure compared to the state of the art, showing that a good approximation of the split closure bound can be obtained with very reasonable computing times.

The concept of dominance among nodes of a branch-and-bound tree, although known for a long time, is typically not exploited by general-purpose mixed-integer linear programming (MILP) codes. The starting point of our work was the general-purpose dominance procedure proposed in the 1980s by Fischetti and Toth, where the dominance test at a given node of the branch-and-bound tree consists of the (possibly heuristic) solution of a restricted MILP only involving the fixed variables. Both theoretical and practical issues concerning this procedure are analyzed, and important improvements are proposed. In particular, we use the dominance test not only to fathom the current node of the tree, but also to derive variable configurations called “nogoods” and, more generally, “improving moves.” These latter configurations, which we rename “pruning moves” so as to stress their use in a node-fathoming context, are used during the enumeration to fathom large sets of dominated solutions in a computationally effective way. Computational results on a testbed of MILP instances whose structure is amenable to dominance are reported, showing that the proposed method can lead to a considerable speedup when embedded in a commercial MILP solver.

Embedding cuts into a branch-and-cut framework is a delicate task, especially when a large set of cuts is available. In this paper we describe a separation heuristic for {0, ½} cuts, a special case of Chvátal-Gomory cuts, that tends to produce many violated inequalities within relatively short time. We report computational results on a large testbed of integer linear programming (ILP) instances of combinatorial problems including satisfiability, max-satisfiability, and linear ordering problems, showing that a careful cut-selection strategy produces a considerable speedup with respect to the cases in which either the separation heuristic is not used at all, or all of the cuts it produces are added to the LP relaxation.

Abstract Effective heuristic solution methods for general Mixed‐Integer Programs (MIPs) are strongly required in many practical applications, and have been the subject of an intensive research effort in the recent years. Fischetti and Lodi recently proposed an exact solution technique based on the use of branching conditions expressed through (invalid) linear inequalities called local branching cuts. In the concluding remarks of their article, these authors anticipated the possibility their method be used to design a genuine MIP metaheuristic framework akin to Tabu Search (TS) or Variable Neighborhood Search (VNS), based on an external MIP solver. In the present article we introduce and analyze computationally a specific implementation of the above idea. In particular, we address MIPs with binary variables, and propose a variant of the classical VNS scheme that we call Diversification, Refining, and Tight‐refining (DRT). The new approach is intended to be of high generality, but exploits the specific structure of some MIPs where the set of binary variables partitions naturally into two levels, with the property that fixing the value of the first‐level variables produces an easier‐to‐solve (but still hard) subproblem. This is often the case, for example, in hard facility location problems arising in telecommunication network design. Our method detects automatically the presence in the MIP model of the first‐level binary variables, if any, according to simple heuristic criteria. This information is then exploited during the intensification phase of the local search, so as to explore nested solution neighborhoods defined by local branching cuts affecting the first‐ and second‐level variables in a different way. Computational results for a hard facility location problem arising in telecommunication UMTS network design are presented, with a comparison among different heuristic methods: the general‐purpose commercial ILOG‐Cplex 7.0 MIP code, the original Fischetti‐Lodi local branching heuristic scheme, the new DRT method, and (for some instances) ad hoc TS and VNS heuristics. The results show that the DRT method, though very simple to implement, provides better heuristic solutions than the alternative methods on all the instances of our test bed. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 61–72 2004

Abstract Given a set of points and distances between them, a basic problem in network design calls for selecting a graph connecting them at a minimum total routing cost, that is, the sum over all pairs of points of the length of their shortest path in the graph. In this paper, we describe some branch‐and‐bound algorithms for the exact solution of a relevant special case arising when the graph has to be a tree. One of the enhancements to our algorithms is the use of “LP shortcutting,” which we introduce as a general‐purpose technique for speeding up the search. Besides network design, we show how trees of small routing cost find useful application in computational biology, where they can be used to determine good alignments of genomic sequences. This leads to a novel alignment heuristic that we analyze in our computational section. © 2002 Wiley Periodicals, Inc.

The asymmetric traveling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper, we present a formulation of the problem involving only 0/1 variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time-window restrictions are modeled using “infeasible path elimination” constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric traveling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, PTW, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of PTW is a strongly 𝒩𝒫-complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for PTW. Computational experiments on the new formulation are reported in a companion paper, where we show that it outperforms alternative formulations on some classes of problem instances. © 2000 John Wiley & Sons, 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.

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.g., in the design of distribution networks in which finite resources are available at each node. Some main classes of cuts are described, and the corresponding separation algorithms are presented. Also, we outline a procedure to extend to RMWA some known classes of valid inequalities for the asymmetric traveling salesman problem. New heuristic procedures to compute near-optimal feasible solutions are proposed, which proved to be very effective to reduce the overall computing time spent by the branch-and-cut algorithm. Computational experience on three classes of test problems involving up to 500 vertices is reported, showing that the proposed approach outperforms other published methods. © 1997 John Wiley & Sons, Inc.

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.

The index selection problem (ISP) is an important optimization problem in the physical design of databases. The aim of this paper is to show that ISP, although NP-hard, can in practice be solved effectively through well-designed algorithms. We formulate ISP as a 0-1 integer linear program and describe an exact branch-and-bound algorithm based on the linear programming relaxation of the model. The performance of the algorithm is enhanced by means of procedures to reduce the size of the candidate index set. We also describe heuristic algorithms based on the solution of a suitably defined knapsack subproblem and on Lagrangian decomposition. Finally, computational results on several classes of test problems are given. We report the exact solution of large-scale ISP instances involving several hundred indexes and queries. We also evaluate one of the heuristic algorithms we propose on very large-scale instances involving several thousand indexes and queries and show that it consistently produces very tight approximate (and sometimes provably optimal) solutions. Finally, we discuss possible extensions and future directions of research.

Abstract We consider the k‐CARD TREE problem, i.e., the problem of finding in a given undirected graph G a subtree with k edges, having minimum weight. Applications of this problem arise in oil‐field leasing and facility layout. Although the general problem is shown to be strongly NP hard, it can be solved in polynomial time if G is itself a tree. We give an integer programming formulation of k‐CARD TREE and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex hull of the integer solutions is studied. © 1994 by John Wiley & Sons, Inc.

An efficient algorithm for the solution of the Min-Sum Arborescence Problem with fixed root-vertex in complete digraphs is presented. The algorithm is based on the well-known Edmonds method. The new approach makes use of simple data structures leading to improvements affecting both computing times and memory requirements. Further improvements are obtained by using a new algorithm based on the solution of a sparse problem. The linear programming reduced costs associated with the arcs are also computed. A FORTRAN implementation is described; the corresponding code is available, on request, from the authors. Extensive computational results on both real-world and random instances are given, showing the effectiveness of the proposed algorithms. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract The Vehicle Scheduling Problem concerns the assigning of a set of time‐tabled trips to vehicles so as to minimize a given cost function. We consider the NP‐hard Multiple Depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assigment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria also described. A branch and bound algorithm is finally proposed. Computational results are given.