ABSTRACT We introduce the nested ‐center problem, a multi‐period variant of the well‐known ‐center problem. Using the nesting concept allows us to obtain solutions consistent over the considered time horizon, that is, facilities that are opened in a given time period stay open for subsequent periods. This consistency is important in real‐life applications, as closing (and potentially later re‐opening) of facilities between time periods can be undesirable. We consider two versions of our problem, with the difference being the objective function. The first version considers the sum of the absolute regrets (of nesting) over all time periods, and the second version considers minimizing the maximum relative regret over the time periods. We present three mixed‐integer programming formulations for the version with an absolute regret objective and two formulations for the version with a relative regret objective. For all the formulations, we present valid inequalities. Based on the formulations and the valid inequalities, we develop branch‐and‐bound/branch‐and‐cut solution algorithms. These algorithms include a preprocessing procedure that exploits the nesting property and starting heuristics and primal heuristics. We conducted a computational study on instances from the literature for the ‐center problem, which we adapted to our problems. We also analyze the effect of nesting on the solution cost and the number of open facilities.

The discrete ‐neighbor ‐center problem (d‐‐CP) is an emerging variant of the classical ‐center problem which recently got attention in literature. In this problem, we are given a discrete set of points and we need to locate facilities on these points in such a way that the maximum distance between each point where no facility is located and its ‐closest facility is minimized. The only existing algorithms in literature for solving the d‐‐CP are approximation algorithms and two recently proposed heuristics. In this work, we present two integer programming formulations for the d‐‐CP, together with lifting of inequalities, valid inequalities, inequalities that do not change the optimal objective function value and variable fixing procedures. We provide theoretical results on the strength of the formulations and convergence results for the lower bounds obtained after applying the lifting procedures or the variable fixing procedures in an iterative fashion. Based on our formulations and theoretical results, we develop branch‐and‐cut (B&C ) algorithms, which are further enhanced with a starting heuristic and a primal heuristic. We evaluate the effectiveness of our B&C algorithms using instances from literature. Our algorithms are able to solve 116 out of 194 instances from literature to proven optimality, with a runtime of under a minute for most of them. By doing so, we also provide improved solution values for 116 instances.

In the Minimum Common String Partition Problem (MCSP), we are given two strings on input, and we want to partition both into the same collection of substrings, minimizing the number of the substrings in the partition. This combinatorial optimization problem has applications in computational biology and is NP-hard. Many different heuristic and exact methods exist for this problem, such as a Greedy approach, Ant Colony Optimization, or Integer Linear Programming. In this paper, we formulate the MCSP as a Dynamic Program and develop an exact solution algorithm based on Decision Diagrams for it. We also introduce a restricted Decision Diagram that allows to compute heuristic solutions to the MCSP and compare the quality of solution and runtime on instances from literature with existing approaches. Our approach scales well and is suitable for heuristic solution of large-scale instances.

We study a class of bilevel integer programs with second-order cone constraints at the upper level and a convex quadratic objective and linear constraints at the lower level. We develop disjunctive cuts to separate bilevel infeasible points using a second-order-cone-based cut-generating procedure. To the best of our knowledge, this is the first time disjunctive cuts are studied in the context of discrete bilevel optimization. Using these disjunctive cuts, we establish a branch-and-cut algorithm for the problem class we study, and a cutting plane method for the problem variant with only binary variables. We present a preliminary computational study on instances with no second-order cone constraints at the upper level and a single linear constraint at the lower level. Our study demonstrates that both our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our test instances, where the non-linearities are linearized in a McCormick fashion.

Many relevant applications from diverse areas such as marketing, wildlife conservation, and defending critical infrastructure can be modeled as interdiction games. In this work, we introduce interdiction games whose objective is a monotone and submodular set function. Given a ground set of items, the leader interdicts the usage of some of the items of the follower in order to minimize the objective value achievable by the follower, who seeks to maximize a submodular set function over the uninterdicted items subject to knapsack constraints. We propose an exact branch-and-cut algorithm for this kind of interdiction game. The algorithm is based on interdiction cuts, which allow the leader to capture the follower’s objective function value for a given interdiction decision of the leader and exploit the submodularity of the objective function. We also present extensions and liftings of these cuts and discuss additional preprocessing procedures. We test our solution framework on the weighted maximal covering interdiction game and the bipartite inference interdiction game. For both applications, the improved variants of our interdiction cut perform significantly better than the basic version. For the weighted maximal covering interdiction game for which a mixed-integer bilevel linear programming (MIBLP) formulation is available, we compare the results with those of a state-of-the-art MIBLP solver. Whereas the MIBLP solver yields a minimum of 54% optimality gap within one hour, our best branch-and-cut setting solves all but four of 108 instances to optimality with a maximum of 3% gap among unsolved ones.

Motivated by their success in the single-objective domain, we propose a very simple linear programming-based matheuristic for tri-objective binary integer programming. To tackle the problem, we obtain lower bound sets by means of the vector linear programming solver Bensolve. Then, simple heuristic approaches, such as rounding and path relinking, are applied to this lower bound set to obtain high-quality approximations of the optimal set of trade-off solutions. The proposed algorithm is compared to a recently suggested algorithm which is, to the best of our knowledge, the only existing matheuristic method for tri-objective integer programming. Computational experiments show that our method produces a better approximation of the true Pareto front using significantly less time than the benchmark method on standard benchmark instances for the three-objective knapsack problem.

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 a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS), and node-weighted Steiner tree problem (NWSTP). The main component of our framework is a new dual ascent algorithm for the rooted APCSTP, which generalizes Wong’s dual ascent algorithm for the Steiner arborescence problem. The lower bounds and dual information obtained from the algorithm are exploited within powerful bound-based reduction tests and for guiding primal heuristics. The framework is complemented by additional alternative-based reduction tests. Extensive computational results on benchmark instances for the PCSTP, MWCS, and NWSTP indicate the framework’s effectiveness, as most instances from literature are solved to optimality within seconds, including most of the (previously unsolved) largest instances from the recent DIMACS Challenge on Steiner trees. Moreover, results on new asymmetric instances for the APCSTP are reported. Since the addressed network design problems are frequently used for modeling various real-world applications (e.g., in bioinformatics), the implementation of the presented B&B framework has been made publicly available.

We introduce the bi-objective prize-collecting Steiner tree problem, whose goal is to find a subtree considering the conflicting objectives of minimizing the edge costs for building that tree, and maximizing the collected node revenues. We consider five iterative mixed-integer programming (MIP) frameworks that identify the complete Pareto front, i.e., one efficient solution for every point on the Pareto front. More precisely, the following methods are studied: an ε-constraint method, a two-phase method, a binary search in the objective space, a weighted Chebyshev norm method, and a method of Sylva and Crema. We also investigate how to exploit and recycle information gained during these iterative MIP procedures to accelerate the solution process. We consider (i) additional strengthening valid inequalities, (ii) procedures for initializing feasible solutions (using a solution pool), (iii) procedures for recycling violated cuts (using a cut pool), and (iv) guiding the branching process by previously detected Pareto optimal solutions. This work is a first study on exact approaches for solving the bi-objective prize-collecting Steiner tree problem. Standard benchmark instances from the literature are used to assess the efficacy of the proposed methods.