An Exact Approach for the Train Single-Routing Selection Problem
A.L. Croella, F. Furini , I. Ljubic, B. Pascariu, P. Pellegrini, P. San Segundo
European Journal of Operational Research , 2026 · accepted
Given a set of train routes with route costs and a set of compatible route pairs with pairing costs, the Train Single-Routing Selection Problem (TSRSP) seeks to assign one route to each train, minimizing the total cost while ensuring pairwise compatibility among the selected routes. This problem is of significant practical relevance in rail traffic management and it is a special case of the Train Routing Selection Problem. We introduce a Binary Quadratic Programming formulation for the TSRSP and apply a linearization technique from the literature that requires a linear number of additional variables and constraints. This yields a novel and effective Mixed Integer Linear Programming (MILP) formulation for the TSRSP. By exploiting the structure of the problem, we further propose a method to strengthen the Linear Programming (LP) relaxation of the MILP formulation, substantially improving its computational performance. The resulting formulation is the first to efficiently solve real-world TSRSP instances to optimality within short computational times—instances that, until now, have only been addressed using heuristic approaches in the literature. Extensive computational results show that our MILP model consistently outperforms existing formulations, both in terms of computational time and the number of instances solved to optimality, primarily due to the strength of its LP relaxation.
Exact Algorithms for Two-Dimensional Knapsack Problems: A Unified Framework with New Benchmark Results
S. Wang, R. Baldacci, F. Furini , L. Wei, Q. Liu
INFORMS Journal on Computing , 2026 · accepted
This paper investigates two-dimensional knapsack problems modeled as a Generalized Two-Dimensional Knapsack Problem, which has not been studied previously in the literature and whose importance arises in designing Branch-Price-and-Cut (BPC) algorithms for the classic Two-Dimensional Bin-Packing Problem. We propose a novel exact solution framework and design both non-numerically exact and numerically exact algorithms tailored to the, which effectively solve the generated problem instances. The proposed framework demonstrates state-of-the-art performance on the well-known Two-Dimensional Knapsack Problem with and without item conflicts and on the basic Two-Dimensional Orthogonal Packing Problem, solving several previously unsolved instances and providing new benchmark results. These findings demonstrate the framework's potential for inspiring algorithm development for higher-dimensional problems and pricing algorithms in other related BPC techniques. To facilitate these interesting future research directions, the algorithm code, instance data, and detailed results are made openly accessible.
Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem
F. Ciccarelli, V. Dose, F. Furini , M. Monaci
Discrete Applied Mathematics , 2026 · accepted
We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that none of them can give a performance guarantee. We further analyze the relative strength among the three upper bounds by determining, for every choice of a ratio between any two of them, the largest values it can attain and providing families of instances for which such values can be reached. Our results show that, for each pair of upper bounds, there exist appropriately chosen instances on which either bound is tighter than the other. Our theoretical analysis is complemented by extensive computational experiments on two benchmark datasets: the standard DIMACS instances and randomly generated instances, providing practical insights into the empirical strength of the upper bounds.
Integer linear programming formulations for the maximum flow blocker problem
I. Bentoumi, F. Furini , A.R. Mahjoub, S. Martin
European Journal of Operational Research , 2025
Given a network with capacities and blocker costs associated with its arcs, we study the maximum flow blocker problem (FB). This problem seeks to identify a minimum-cost subset of arcs to be removed from the network, ensuring that the maximum flow value from the source to the destination in the remaining network does not exceed a specified threshold. The FB finds applications in telecommunication networks and monitoring of civil infrastructures, among other domains. We undertake a comprehensive study of several new integer linear programming (ILP) formulations designed for the FB. The first type of model, featuring an exponential number of constraints, is solved through tailored Branch-and-Cut algorithms. In contrast, the second type of ILP model, with a polynomial number of variables and constraints, is solved using a state-of-the-art ILP solver. The latter formulation establishes a structural connection between the FB and the maximum flow interdiction problem (FI), introducing a novel approach to obtaining solutions for each problem from the other. blackThe ILP formulations proposed for solving the FB are evaluated thanks to a theoretical analysis assessing the strength of their LP relaxations. Additionally, the exact methods presented in this paper undergo a thorough comparison through an extensive computational campaign involving a set of real-world and synthetic instances. Our tests aim to evaluate the performance of the exact algorithms and identify the features of instances that can be solved with proven optimality.
A Numerically Exact Algorithm for the Bin-Packing Problem
R. Baldacci, S. Coniglio, F. Furini
INFORMS Journal on Computing , 2024
We propose a numerically exact algorithm for solving the Bin-Packing Problem (BPP) based on a branch-price-and-cut framework combined with a pattern-enumeration method. Key to the algorithm is a novel technique for the computation of numerically safe dual bounds for the widely adopted set covering reformulation of the BPP (tightened with additional valid inequalities) with a precision that is higher than the one of general-purpose floating-point solvers. Our branch-price-and-cut algorithm also relies on an exact integer (fixed-point) label setting algorithm for solving the pricing problem associated with the tightened set-covering formulation. To the best of our knowledge, ours is the first algorithm for the BPP that is numerically exact and practical for solving large-scale instances. Extensive computational results on instances affected by notorious numerical difficulties (those of the Augmented Non-IRUP class) show that our exact algorithm outperforms all of the not numerically exact state-of-the-art algorithms based on branch-and-cut-and-price techniques that rely on a set-covering formulation of the BPP.
A Branch-and-Benders-Cut Approach to Solve the Maximum Flow Blocker Problem
I. Bentoumi, F. Furini , A.R. Mahjoub, S. Martin
9th International Conference on Control, Decision and Information Technologies (CoDIT 2023), Rome, Italy, July 2023 (4 pages) , 2023
Given a directed graph with capacities and interdiction costs associated with its arcs, the maximum flow blocker problem (MFBP) asks to find a minimum-cost subset of arcs to be removed from the graph in such a way that the remaining maximum-flow value does not exceed a given threshold. The MFBP has applications in telecommunication networks and in the monitoring of civil infrastructures, among others. We propose an integer linear programming formulation (ILP) with an exponential number of constraints, called Benders cut, for the MFBP. Accordingly, we derive a branch-and-cut algorithm to optimally solve the problem. Preliminary experimental results are reported to assess performance of the formulation and more precisely to determine the dimension of the problem that could be solved to proven optimality.
A Combinatorial Flow-based Formulation for Temporal Bin Packing Problems
J. Martinovic, N. Strasdat, J. Valério de Carvalho, F. Furini
European Journal of Operational Research , 2023
In this article, we consider two neighboring generalizations of the classical bin packing problem: the temporal bin packing problem (TBPP) and the temporal bin packing problem with fire-ups (TBPP-FU). In both cases, the task is to arrange a set of given jobs, characterized by a resource consumption and an activity window, on homogeneous servers of limited capacity. To keep the operational costs but also the energy consumption of this allocation as low as possible, two main optimization goals were identified in the literature. While TBPP is exclusively concerned with minimizing the number of servers in use, TBPP-FU additionally takes into account the switch-on processes required for their operation. In both cases, challenging integer optimization problems are obtained, which can differ significantly from each other despite the seemingly only marginal variation of the problems. In the literature, a branch-and-price method enriched with many preprocessing steps (for the TBPP) and compact formulations (for the TBPP-FU), which have been steadily improved by numerous reduction methods, have emerged as, currently, the most promising solution methods. In this paper, we present, in a sense, a unified solution approach for both problems based on graph theory. Any scientific contributions in this direction failed so far because of the exponential number of the necessary states and transitions. The approach we present in this article cannot change the theoretical exponentiality itself, but it can make it controllable by clever construction of the resulting graphs. In particular, this leads to the fact that for the first time all classical benchmark instances (and even larger ones) for the two problems can be solved -- in times that significantly improve those of the previous approaches.
CliSAT: a new exact algorithm for hard maximum clique problems
P. San Segundo, F. Furini , D. Alvarez, P. Pardalos
European Journal of Operational Research , 2023
Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called, to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a wide range of applications. The newly developed exact approach is a combinatorial branch-and-bound algorithm that exploits the state-of-the-art branching scheme enhanced by two new bounding techniques with the goal of reducing the branching tree. The first one is based on graph colouring procedures and partial maximum satisfiability problems arising in the branching scheme. The second one is a filtering phase based on constraint programming and domain propagation techniques. is designed for structured MCP instances which are computationally difficult to solve since they are dense and contain many interconnected large cliques. Extensive experiments on hard benchmark instances, as well as new hard instances arising from different applications, show that outperforms the state-of-the-art MCP algorithms, in some cases by several orders of magnitude.
A new branch-and-filter exact algorithm for binary constraint satisfaction problems
P. San Segundo, F. Furini , R. León
European Journal of Operational Research , 2022
A binary constraint satisfaction problem (BCSP) consists in determining an assignment of values to variables that is compatible with a set of constraints. The problem is called binary because the constraints involve only pairs of variables. The BCSP is a cornerstone problem in Constraint Programming (CP), appearing in a very wide range of real-world applications. In this work, we develop a new exact algorithm which effectively solves the BCSP by reformulating it as a k-clique problem on the underlying microstructure graph representation. Our new algorithm exploits the cutting-edge branching scheme of the state-of-the-art maximum clique algorithms combined with two filtering phases in which the domains of the variables are reduced. Our filtering phases are based on coloring techniques and on heuristically solving an associated boolean satisfiability (SAT) problem. In addition, the algorithm initialization phase performs a reordering of the microstructure graph vertices that produces an often easier reformulation to solve. We carry out an extensive computational campaign on a benchmark of almost 2000 instances, encompassing numerous real and synthetic problems from the literature. The performance of the new algorithm is compared against four SAT-based solvers and three general purpose CP solvers. Our tests reveal that the new algorithm significantly outperforms all the others in several classes of BCSP instances.
Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
F. Furini , I. Ljubić, E. Malaguti, P. Paronuzzi
Operations Research , 2022
Given an undirected graph, we study the capacitated vertex separator problem which asks to find a subset of vertices of minimum cardinality, the removal of which induces a graph having a bounded number of pairwise disconnected shores (subsets of vertices) of limited cardinality. The problem is of great importance in the analysis and protection of communication or social networks against possible viral attacks, and for matrix decomposition algorithms. In this article we provide a new bilevel interpretation of the problem, and model it as a two-player Stackelberg game, in which the leader interdicts the vertices (i.e., decides on the subset of vertices to remove), and the follower solves a combinatorial optimization problem on the resulting graph. This approach allows us to develop a computational framework based on an integer programming formulation in the natural space of the variables. Thanks to this bilevel interpretation, we derive three different families of strengthening inequalities and show that they can be separated in polynomial time. We also show how to extend these results to a min-max version of the problem. Our extensive computational study conducted on available benchmark instances from the literature reveals that our new exact method is competitive against the state-of-the-art algorithms for the capacitated vertex separator problem, and is able to improve the best known results for several difficult classes of instances. The ideas exploited in our framework can also be extended to other vertex/edge deletion/insertion problems or graph partitioning problems by modeling them as two-player Stackelberg games and solving them through bilevel optimization.
On the exact separation of cover inequalities of maximum-depth
D. Catanzaro, S. Coniglio, F. Furini
Optimization Letters , 2022
We investigate the problem of separating cover inequalities of maximum-depth exactly. We propose a pseudopolynomial-time dynamic-programming algorithm for its solution, thanks to which we show that this problem is weakly NP-hard (similarly to the problem of separating cover inequalities of maximum violation). We carry out extensive computational experiments on instances of the knapsack and the multi-dimensional knapsack problems with and without conflict constraints. The results show that, with a cutting-plane generation method based on the maximum-depth criterion, we can optimize over the cover-inequality closure by generating a number of cuts smaller than when adopting the standard maximum-violation criterion. We also introduce the Point-to-Hyperplane Distance Knapsack Problem (PHD-KP), a problem closely related to the separation problem for maximum-depth cover inequalities, and show how the proposed dynamic programming algorithm can be adapted for effectively solving the PHD-KP as well.
Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
S. Coniglio, F. Furini , I. Ljubic
Mathematical Programming , 2022
We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This problem generalizes the problem introduced by, and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. It has applications to, among others, maximal covering location, and influence maximization problems. In the paper, we propose a double-hypograph decomposition which allows for projecting out the variables associated with the items by separately exploiting the structural properties of the utility function and of the set-union operator. Thanks to it, the utility function is linearized via an exact outer-approximation technique, whereas the set-union operator is linearized in two ways: either (i) via a reformulation based on submodular cuts, or (ii) via a Benders decomposition. We analyze from a theoretical perspective the strength of the inequalities of the resulting reformulations, and embed them into two branch-and-cut algorithms. We also show how to extend our reformulations to the case where the utility function is not necessarily increasing. We then experimentally compare our algorithms inter se, to a standard reformulation based on submodular cuts, to a state-of-the-art global-optimization solver, and to the greedy algorithm for the maximization of a submodular function. The results reveal that, on our testbed, the method based on combining an outer approximation with Benders cuts significantly outperforms the other ones.
Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups
J. Martinovic, N. Strasdat, J. Valerio de Carvalho, F. Furini
Optimization Letters , 2022
The aim of this letter is to design and computationally test several improvements for the compact integer linear programming (ILP) formulations of the temporal bin packing problem with fire-ups (TBPP-FU). This problem is a challenging generalization of the classical bin packing problem in which the items, interpreted as jobs of given weight, are active only during an associated time window. The TBPP-FU objective function asks for the minimization of the weighted sum of the number of bins, viewed as servers of given capacity, to execute all the jobs and the total number of fire-ups. The fire-ups count the number of times the servers are activated due to the presence of assigned active jobs. Our contributions are effective procedures to reduce the number of variables and constraints of the ILP formulations proposed in the literature as well as the introduction of new valid inequalities. By extensive computational tests we show that substantial improvements can be achieved and several instances from the literature can be solved to proven optimality for the first time.
A Branch-and-Price Algorithm for the Minimum Sum Coloring Problem
D. Delle Donne, F. Furini , E. Malaguti, R. Wolfler Calvo
Discrete Applied Mathematics , 2021
A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark DIMACS graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (ii) running times and (iii) exit gaps obtained when optimality is not achieved. For the DIMACS instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds.
A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques
T. Gschwind, S. Irnich, F. Furini , R. Wolfler Calvo
INFORMS Journal on Computing , 2021
We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property is relaxed, e.g., the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new effective pricing algorithms are developed and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, e.g., structure-preserving versus dichotomous branching and their interplay with different pricing algorithms. The finally chosen setup for the branch-and-price produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.
A branch-and-cut algorithm for the Edge Interdiction Clique Problem
F. Furini , I. Ljubic, P. San Segundo, Y. Zhao
European Journal of Operational Research , 2021
Given a graph G and an interdiction budget k N, the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim of reducing the clique number of the graph. The EICP optimal solutions, called optimal interdiction policies, determine the subset of most vital edges of a graph which are crucial for preserving its clique number. We propose a new set-covering-based Integer Linear Programming (ILP) formulation for the EICP with an exponential number of constraints, called the clique-covering inequalities. We design a new branch-and-cut algorithm which is enhanced by a tailored separation procedure and by an effective heuristic initialization phase. Thanks to the new exact algorithm, we manage to solve the EICP in several sets of instances from the literature. Extensive tests show that the new exact algorithm greatly outperforms the state-of-the-art approaches for the EICP.
A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts
S. Coniglio, F. Furini , P. San Segundo
European Journal of Operational Research , 2021
We study the Knapsack Problem with Conflicts, a generalization of the Knapsack Problem in which a set of conflicts specifies pairs of items which cannot be simultaneously selected. In this work, we propose a novel combinatorial branch-and-bound algorithm for this problem based on an n-ary branching scheme. Our algorithm effectively combines different procedures for pruning the branch-and-bound nodes based on different relaxations of the Knapsack Problem with Conflicts. Its main elements of novelty are: (i) the adoption of the branching-and-pruned set branching scheme which, while extensively used in the maximum-clique literature, was never successfully employed for solving the Knapsack Problem with Conflicts; (ii) the adoption of the Multiple-Choice Knapsack Problem for the derivation of upper bounds used for pruning the branch-and-bound tree nodes; and (iii) the design of a new upper bound for the latter problem which can be computed very efficiently. Key to our algorithm is its high pruning potential and the low computational effort that it requires to process each branch-and-bound node. An extensive set of experiments carried out on the benchmark instances typically used in the literature shows that, for edge densities ranging from 0.1 to 0.9, our algorithm is faster by up to two orders of magnitude than the state-of-the-art method and by up to several orders of magnitude than a state-of-the-art mixed-integer linear programming solver.
A branch-and-price algorithm for the temporal bin packing problem
M. Dell'Amico, F. Furini , M. Iori
Computer & Operations Research , 2020
We study an extension of the classical Bin Packing Problem, where each item consumes the bin capacity during a given time window that depends on the item itself. The problem asks for finding the minimum number of bins to pack all the items while respecting the bin capacity at any time instant. A polynomial-size formulation, an exponential-size formulation, and a number of lower and upper bounds are studied. A branch-and-price algorithm for solving the exponential-size formulation is introduced. An overall algorithm combining the different methods is then proposed and tested through extensive computational experiments.
On Integer and Bilevel Formulations for the k-Vertex Cut Problem
F. Furini , I. Ljubic, E. Malaguti, P. Paronuzzi
Mathematical Programming Computation , 2020
The family of Critical Node Detection Problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problems asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.
A lexicographic pricer for the fractional bin packing problem
S. Coniglio, F. D'Andreagiovanni, F. Furini
Operations Research Letters , 2019
We propose an exact lexicographic dynamic programming pricing algorithm for solving the Fractional Bin Packing Problem with column generation. The new algorithm is designed for generating maximal columns of minimum reduced cost which maximize, lexicographically, one of the measures of maximality we investigate. Extensive computational experiments reveal that a column generation algorithm based on this pricing technique can achieve a substantial reduction in number of columns and computing time, also when combined with a classical smoothing technique from the literature.
A new branch-and-bound algorithm for the Maximum Weighted Clique Problem
P. San Segundo, F. Furini , J. Artieda
Computer & Operations Research , 2019
We study the Maximum Weighted Clique Problem (MWCP), a generalization of the Maximum Clique Problem in which weights are associated with the vertices of a graph. The MWCP calls for determining a complete subgraph of maximum weight. We design a new combinatorial branch-and-bound algorithm for the MWCP, which relies on an effective bounding procedure. The size of the implicit enumeration tree is largely reduced via a tailored branching scheme, specifically conceived for the MWCP. The new bounding function extends the classical MWCP bounds from the literature to achieve a good compromise between pruning potential and computing effort. We perform extensive tests on random graphs, graphs from the literature and real-world graphs, and we computationally show that our new exact algorithm is competitive with the state-of-the-art algorithms for the MWCP in all these classes of instances.
A new branch-and-bound algorithm for the maximum edge-weighted clique problem
P. San Segundo, S. Coniglio, F. Furini , I. Ljubic
European Journal of Operational Research , 2019
We study the maximum edge-weighted clique problem, a problem related to the maximum (vertex-weighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics, material science, computer vision, robotics, and many more. In this work, we propose a new combinatorial branch-and-bound algorithm for the problem which relies on a novel bounding procedure capable of pruning a very large amount of nodes of the branch-and-bound tree. Extensive computational experiments on random and structured graphs, encompassing standard benchmarks used in the literature as well as recently introduced real-world large-scale graphs, show that our new algorithm outperforms the state-of-the-art by several orders of magnitude on many instances.
A note on selective line-graphs and partition colorings
D. Cornaz, F. Furini , E. Malaguti, A. Santini
Operations Research Letters , 2019
We extend a one-to-one correspondence between the set of all colorings of any graph and the set of all stable sets of an auxiliary graph, from graphs to partitioned graphs. This correspondence has an application to Selective Coloring and to Selective Max-Coloring.
Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Location Problems
J.F. Cordeau, F. Furini , I. Ljubic
European Journal of Operational Research , 2019
Covering problems constitute a fundamental family of facility location problems. This paper introduces a new exact algorithm for two important members of this family: i) the maximal covering location problem (MCLP), which requires finding a subset of facilities that maximizes the amount of customer demand covered while respecting a budget constraint on the cost of the facilities; and ii) the partial set covering location problem (PSCLP), which minimizes the cost of the open facilities while forcing a certain amount of customer demand to be covered. We study an effective decomposition approach to the two problems based on the branch-and-Benders-cut reformulation. Our new approach is designed for the realistic case in which the number of customers is much larger than the number of potential facility locations. We report the results of a series of computational experiments demonstrating that, thanks to this decomposition techniques, optimal solutions can be found very quickly for some benchmark instances with one hundred potential facility locations and involving up to 15 and 40 million customer demand points for the MCLP and the PSCLP, respectively.
QPLIB: A Library of Quadratic Programming Instances
F. Furini , E. Traversi, P. Belotti, A. Frangioni, A. Gleixner, N. Gould, L. Liberti, A. Lodi, R. Misener, H. Mittelmann, N. Sahinidis, S. Vigerske and A. Wiegele
Mathematical Programming Computation , 2019
This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very ``varied'' class of problems, comprising sub-classes of problems ranging from trivial to undecidable. Solution methods for QP are very diverse, ranging from entirely combinatorial ones to completely continuous ones, including many for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the many different interested communities is therefore important. We propose a simple taxonomy for QP instances that leads to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents.
The Maximum Clique Interdiction Problem
F. Furini , I. Ljubic, S. Martin, P. San Segundo
European Journal of Operational Research , 2019
Given a graph G and an interdiction budget k, the Maximum Clique Interdiction Problem asks to find a subset of at most k vertices to remove from G so that the size of the maximum clique in the remaining graph is minimized. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases and surveillance of communication networks. We propose an integer linear programming formulation of the problem based on an exponential family of Clique-Interdiction Cuts and we give necessary and sufficient conditions under which these cuts are facet-defining. Our new approach provides a useful tool for analyzing the resilience of (social) networks with respect to clique-interdiction attacks, i.e., the decrease of the size of the maximum clique as a function of an incremental interdiction budget level. On a benchmark set of publicly available instances, including large-scale social networks with up to one hundred thousand vertices and three million edges, we show that most of them can be analyzed and solved to proven optimality within short computing time.
The Vertex k-cut Problem
D. Cornaz, F. Furini , M. Lacroix, E. Malaguti, A. R. Mahjoub, S. Martin
Discrete Optimization , 2019
Given an undirected graph G=(V,E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k components. Given a graph G and an integer k2, the vertex k-cut problem consists in finding a vertex k-cut of G of minimum cardinality. We first prove that the problem is NP-hard for any fixed k 3. We then present a compact formulation, and an extended formulation from which we derive a column generation and a branching scheme. Extensive computational results prove the effectiveness of the proposed methods.
Theoretical and computational study of several linearisation techniques for Binary Quadratic Problems
F. Furini , E. Traversi
Annals of Operations Research , 2019
We perform a theoretical and computational study of the classical Linearisation Techniques (LT) and we propose a new LT for Binary Quadratic Problems (BQPs). We discuss the relations between the Linear Programming (LP) relaxations of the considered LT for generic BQPs. We prove that for a specific class of BQP all the LTs have the same LP relaxation value. We also compare the LT computational performance for four different BQPs from the literature. We consider the Unconstrained BQP and the Maximum Cut of edge-weighted graphs and, in order to measure the effects of constraints on the computational performance, we also consider the quadratic extension of two classical combinatorial optimization problems, i.e., the Knapsack and Stable Set problems.
Tighter MIP models for Barge Container Ship Routing
L. Alfandari, T. Davidovic, F. Furini , I. Ljubic, V. Maras and S. Martin
Omega , 2019
This paper addresses the problem of optimal planning of a liner service for a barge container shipping company. Given estimated weekly demands between pairs of ports, our goal is to determine the subset of ports to be called and the amount of containers to be shipped between each pair of ports, so as to maximize the profit of the shipping company. In order to save possible leasing or storage costs of empty containers at the respective ports, our approach takes into account the repositioning of empty containers. The line has to follow the outbound-inbound principle, starting from the port at the river mouth. We propose a novel integrated approach in which the shipping company can simultaneously optimize the route (along with repositioning of empty containers), the choice of the final port, length of the turnaround time and the size of its fleet. To solve this problem, a new mixed integer programming model is proposed. On the publicly available set of benchmark instances for barge container routing, we demonstrate that this model provides very tight dual bounds and significantly outperforms the existing approaches from the literature for splittable demands. We also show how to further improve this model by projecting out arc variables for modeling the shipping of empty containers. Our numerical study indicates that the latter model improves the computing times for the challenging case of unsplittable demands. We also study the impact of the turnaround time optimization on the total profit of the company.
An Exact Algorithm for the Partition Coloring Problem
F. Furini , E. Malaguti and A. Santini
Computer & Operations Research , 2018
We study the Partition Coloring Problem (PCP), a generalization of the Vertex Coloring Problem where the vertex set is partitioned. The PCP asks to select one vertex for each subset of the partition in such a way that the chromatic number of the induced graph is minimum. We propose a new Integer Linear Programming formulation with an exponential number of variables. To solve this formulation to optimality, we design an effective Branch-and-Price algorithm. Good quality initial solutions are computed via a new metaheuristic algorithm based on adaptive large neighbourhood search. Extensive computational experiments on a benchmark test of instances from the literature show that our Branch-and-Price algorithm, combined with the new metaheuristic algorithm, is able to solve for the first time to proven optimality several open instances, and compares favourably with the current state-of-the-art exact algorithm.
Exact Approaches for the Knapsack Problem with Setups
F. Furini , M. Monaci, E. Traversi
Computer & Operations Research , 2018
We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We theoretically compare the strength of the relaxations and derive specific results for a relevant case arising in benchmark instances from the literature. Finally, we embed the algorithms above into a unified implicit enumeration scheme which is run in parallel with an improved Dynamic Programming algorithm to effectively solve the problem to proven optimality. An extensive computational analysis shows that our new exact algorithm is capable of efficiently solving all the instances of the literature and turns out to be the best algorithm for instances with a low number of classes.
On the Product Knapsack Problem
C. D'Ambrosio, F. Furini , M. Monaci, E. Traversi
Optimization Letters , 2018
Given a set of items, each characterized by a profit and a weight, we study the problem of maximizing the product of the profits of the selected items, while respecting a given capacity. To the best of our knowledge this is the first manuscript that studies this variant of the knapsack problem which we call Product Knapsack Problem. We show that PKP is weakly NP-hard. We propose and implement a Dynamic Programming algorithm and different Mixed Integer Linear and Nonlinear Programming formulations for the. Finally, we present an extensive computational study on a large set of benchmark instances derived from the literature.
An Improved DSATUR-Based Branch-and-Bound Algorithm for the Vertex Coloring Problem
F. Furini , V. Gabrel, I. C. Ternier
Networks , 2017
Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph in such a way that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR-based Branch-and-Bound algorithm (DSATUR) is an effective exact algorithm for the VCP. One of its main drawback is that a lower bound is computed only once and it is never updated. We introduce a reduced graph which allows the computation of lower bounds at nodes of the branching tree. We compare the effectiveness of different classical VCP bounds, plus a new lower bound based on the 1-to-1 mapping between VCPs and Stable Set Problems. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of instances solved to proven optimality.
An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
F. Furini , I. Ljubić, M. Sinnl
European Journal of Operational Research , 2017
Given a set of items with profits and weights and a knapsack capacity, we study the problem of finding a maximal knapsack packing that minimizes the profit of selected items. We propose an effective dynamic programming (DP) algorithm which has pseudo-polynomial time complexity. We demonstrate the equivalence between this problem and the problem of finding a minimal knapsack cover that maximizes the profit of selected items. In an extensive computational study on a large and diverse set of benchmark instances, we demonstrate that the new DP algorithm outperforms a state-of-the-art commercial mixed-integer programming (MIP) solver applied to the two best performing MIP models from the literature.
ILP Models and Column Generation for the Minimum Sum Coloring Problem
F. Furini , E. Malaguti, S. Martin and I.-C. Ternier
8th International Network Optimization Conference (INOC 2017), Lisbon, Portugal, February 2017 (10 pages) , 2017
We study two Integer Linear Programming (ILP) formulations for the Minimum Sum Coloring Problem (MSCP). The problem is an extension of the classical Vertex Coloring Problem in which each color is represented by a positive natural number. The MSCP asks to minimize the sum of the cardinality of subsets of vertices receiving the same color, weighted by the index of the color, while ensuring that vertices linked by an edge receive different colors. The first ILP formulation has a polynomial number of variables while the second one has an exponential number of variables and is tackled via column generation. Computational tests show that the linear programming relaxation of the second formulation provides tight lower bounds which allow us to solve to proven optimality some hard instances of the literature.
Improving the Approximated Projected Perspective Reformulation by Dual Information
A. Frangioni, F. Furini , C. Gentile
Operations Research Letters , 2017
We propose an improvement of the Approximated Projected Perspective Reformulation (AP^2R) for dealing with constraints linking the binary variables. The new approach solves the Perspective Reformulation (PR) once, and then use the corresponding dual information to reformulate the problem prior to applying AP^2R, thereby combining the root bound quality of the PR with the reduced relaxation computing time of AP^2R. Computational results for the cardinality-constrained Mean-Variance portfolio optimization problem show that the new approach is competitive with state-of-the-art ones.
Solving Vertex Coloring Problems as Maximum Weight Stable Set Problems
D. Cornaz, F. Furini , E. Malaguti
Discrete Applied Mathematics , 2017
In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set Problems on an associated graph. We exploit the transformation proposed by Cornaz and Jost, where given a graph G, an auxiliary graph G is constructed, such that the family of all stable sets of G is in one-to-one correspondence with the family of all feasible colorings of G. The transformation in was originally proposed for the classical Vertex Coloring and the Max-Coloring problems; we extend it to the Equitable Coloring Problem and the Bin Packing Problem with Conflicts. We discuss the relation between the Maximum Weight Stable formulation and a polynomial-size formulation for the VCP, proposed by Campeˆlo, Correˆa and Campos [4] and called the Representative formulation. We report extensive computational experiments on benchmark instances of the four problems, and compare the solution method with the state-of-the-art algorithms. By exploiting the proposed method, we largely outperform the state-of-the-art algorithm for the Max-coloring Problem, and we are able to solve, for the first time to proven optimality, 14 Max-coloring and 2 Equitable Coloring instances.
Approaches to a real-world train timetabling problem in a railway node
V. Cacchiani, F. Furini and M. P. Kidd
Omega , 2016
We consider the Train Timetabling Problem (TTP) in a railway node (i.e. a set of stations in an urban area interconnected by tracks), which calls for determining the best schedule for a given set of trains during a given time horizon, while satisfying several track operational constraints. In particular, we consider the context of a highly congested railway node in which different Train Operators wish to run trains according to timetables that they propose, called ideal timetables. The ideal timetables altogether may be (and usually are) conflicting, i.e. they do not respect one or more of the track operational constraints. The goal is to determine conflict-free timetables that differ as little as possible from the ideal ones. The problem was studied for a research project funded by Rete Ferroviaria Italiana (RFI), the main Italian railway Infrastructure Manager, who also provided us with real-world instances. We present an Integer Linear Programming (ILP) model for the problem, which adapts previous ILP models from the literature to deal with the case of a railway node. The Linear Programming (LP) relaxation of the model is used to derive a dual bound. In addition, we propose an iterative heuristic algorithm that is able to obtain good solutions to real-world instances with up to 1500 trains in short computing times. The proposed algorithm is also used to evaluate the capacity saturation of the railway nodes.
Approximated perspective relaxations: a project and lift approach
A. Frangioni, F. Furini , C. Gentile
Computational Optimization and Applications , 2016
The Perspective Reformulation (PR) of a Mixed-Integer NonLinear Program with semi-continuous variables is obtained by replacing each term in the (separable) objective function with its convex envelope. Solving the corresponding continuous relaxation requires appropriate techniques. Under some rather restrictive assumptions, the Projected PR (P^2R) can be defined where the integer variables are eliminated by projecting the solution set onto the space of the continuous variables only. This approach produces a simple piecewise-convex problem with the same structure as the original one; however, this prevents the use of general-purpose solvers, in that some variables are then only implicitly represented in the formulation. We show how to construct an Approximated Projected PR (AP^2R) whereby the projected formulation is ``lifted'' back to the original variable space, with each integer variable expressing one piece of the obtained piecewise-convex function. In some cases, this produces a reformulation of the original problem with exactly the same size and structure as the standard continuous relaxation, but providing substantially improved bounds. In the process we also substantially extend the approach beyond the original P^2R development by relaxing the requirement that the objective function be quadratic and the left endpoint of the domain of the variables be non-negative. While the AP^2R bound can be weaker than that of the PR, this approach can be applied in many more cases and allows direct use of off-the-shelf MINLP software; this is shown to be competitive with previously proposed approaches in some applications.
MIP Formulations for a Rich Real-world Lot-sizing Problem with Setup Carryover
F. Focacci, F. Furini , V. Gabrel, D. Godard and X. Shen
5th International Symposium on Combinatorial Optimization (ISCO 2016), Vietri sul Mare, Italy, May 2016 (12 pages) , 2016
A rich lot-sizing problem is studied in this manuscript which comes from a real-world application. Our new lot-sizing problem combines several features, i.e., parallel machines, production time windows, backlogging, lost sale and setup carryover. Three mixed integer programming formulations are proposed. We theoretically and computationally compare these different formulations, testing them on real-world and randomly generated instances. Our study is the first step for efficiently tackling and solving this challenging real-world lot-sizing problem.
Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming
F. Furini , E. Malaguti, D. Thomopulos
INFORMS Journal on Computing , 2016
We propose a framework to model general guillotine restrictions in two-dimensional cutting problems formulated as Mixed-Integer Linear Programs (MIP). The modeling framework requires a pseudo-polynomial number of variables and constraints, which can be effectively enumerated for medium-size instances. Our modeling of general guillotine cuts is the first one that, once it is implemented within a state-of-the-art MIP solver, can tackle instances of challenging size. We mainly concentrate our analysis on the Guillotine Two Dimensional Knapsack Problem (G2KP), for which a model, and an exact procedure able to significantly improve the computational performance, are given. We also show how the modeling of general guillotine cuts can be extended to other relevant problems such as the Guillotine Two Dimensional Cutting Stock Problem (G2CSP) and the Guillotine Strip Packing Problem (GSPP). Finally, we conclude the paper discussing an extensive set of computational experiments on G2KP and GSPP benchmark instances from the literature.
Solving the Temporal Knapsack Problem via Recursive Dantzig–Wolfe Reformulation
A. Caprara, F. Furini , E. Malaguti, E. Traversi
Information Processing Letters , 2016
The Temporal Knapsack Problem (TKP) is a generalization of the standard Knapsack Problem where a time horizon is considered, and each item consumes the knapsack capacity during a limited time interval only. In this paper we solve the TKP using what we call a Recursive Dantzig-Wolfe Reformulation (DWR) method. The generic idea of Recursive DWR is to solve a Mixed Integer Program (MIP) by recursively applying DWR, i.e., by using DWR not only for solving the original MIP but also for recursively solving the pricing sub-problems. In a binary case (like the TKP), the Recursive DWR method can be performed in such a way that the only two components needed during the optimization are a Linear Programming solver and an algorithm for solving Knapsack Problems. The Recursive DWR allows us to solve Temporal Knapsack Problem instances through computation of strong dual bounds, which could not be obtained by exploiting the best-known previous approach based on DWR.
The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace
F. Furini , C.A. Persiani, P. Toth
Transportation Research Part B , 2016
The integration of drones into civil airspace is one of the most challenging problems for the automation of the controlled airspace, and the optimization of the drone route is a key step for this process. In this paper, we optimize the route planning of a drone mission that consists of departing from an airport, flying over a set of mission way points and coming back to the initial airport. We assume that during the mission a set of piloted aircraft flies in the same airspace and thus the cost of the drone route depends on the air traffic and on the avoidance maneuvers used to prevent possible conflicts. Two Air Traffic Management techniques, i.e., routing and holding, are modeled in order to maintain a minimum separation between the drone and the piloted aircraft. The considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA), relates to the drone route planning phase and aims to minimize the total operational cost. Two heuristic algorithms are proposed for the solution of the problem. A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem, which allows holdings at mission way points, and a Branch and Cut algorithm are proposed for solving the TDTSPPCA to optimality. An additional formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and a Cutting Plane algorithm is designed. Finally, computational experiments on real-world air traffic data from Milano Linate Terminal Maneuvering Area are reported to evaluate the performance of the proposed formulations and of the heuristic algorithms.
Automatic Dantzig-Wolfe Reformulation of Mixed Integer Programs
M. Bergner, A. Caprara, A. Ceselli, F. Furini , M. E. Lübbecke, E. Malaguti, E. Traversi
Mathematical Programming , 2015
Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That is, we perform a rigorous experimental study, which results in identifying a score to estimate the quality of a decomposition: after building a set of potentially good candidates, we exploit such a score to detect which decomposition might be useful for Dantzig-Wolfe reformulation of a MIP. We experiment with general instances from MIPLIB2003 and MIPLIB2010 for which a decomposition method would not be the first choice, and demonstrate that strong dual bounds can be obtained from the automatically reformulated model using column generation. Our findings support the idea that Dantzig-Wolfe reformulation may hold more promise as a ge-ne-ral-pur-pose tool than previously acknowledged by the research community.
Heuristic and exact algorithms for the interval min-max regret knapsack problem
F. Furini , M. Iori, S. Martello, M. Yagiura
INFORMS Journal on Computing , 2015
We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min-max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the complexity class ^p_2 hence it is most probably not in NP. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an NP-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm, and evaluate their performance through extensive computational experiments.
ILP and CP Formulations for the Lazy Bureaucrat Problem
I. Ljubic, F. Furini , M. Sinnl
12th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2015), Barcelona, Spain, May 2015 (15 pages) , 2015
Lazy reformulations of classical combinatorial optimization problems are new and challenging classes of problems. In this paper we focus on the Lazy Bureaucrat Problem (LBP) which is the lazy counterpart of the knapsack problem. Given a set of tasks with a common arrival time and deadline, the goal of a lazy bureaucrat is to schedule a least profitable subset of tasks, while having an excuse that no other tasks can be scheduled without exceeding the deadline. Three ILP formulations and their CP counterparts are studied and implemented. In addition, a dynamic programming algorithm that runs is pseudo-polynomial time and polynomial greedy heuristics are implemented and computationally compared with ILP/CP approaches. For the computational study, a large set of knapsack-type instances with various characteristics is used to examine the applicability and strength of the proposed approaches.
Improved rolling horizon approaches to the aircraft sequencing problem
F. Furini , M. P. Kidd, C. Persiani, P. Toth
Journal of Scheduling , 2015
In a scenario characterized by a continuous growth of air transportation demand, the runways of large airports serve hundreds of aircraft every day. Aircraft sequencing is a challenging problem that aims to increase runway capacity in order to reduce delays as well as the workload of air traffic controllers. In many cases, the air traffic controllers solve the problem by using the simple ``First-Come-First-Serve'' (FCFS) rule. In this paper we present a rolling horizon approach which partitions a sequence of aircraft into chunks and solves the Aircraft Sequencing Problem (ASP) individually for each of these chunks. Some rules for deciding how to partition a given aircraft sequence are proposed and their effects on solution quality investigated. Moreover, two Mixed Integer Linear Programming (MILP) models for the ASP are reviewed in order to formalize the problem, and a tabu search heuristic is proposed for finding solutions to the ASP in a short computation time. Finally, we develop an IRHA which, by using different chunking rules, is able to find solutions significantly improving on the FCFS rule for real world air traffic instances from Milano Linate Airport.
Lower Bounding Techniques for DSATUR-based Branch and Bound
F. Furini , V. Gabrel, I. C. Ternier
7th International Network Optimization Conference (INOC 2015), Warsaw, Poland, June 2015 (8 pages) , 2015
Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph such that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR-based Branchand-Bound is a well-known exact algorithm for the VCP. One of its main drawbacks is that a lower bound (equal to the size of a maximal clique) is computed once at the root of the branching scheme and it is never updated during the execution of the algorithm. In this article, we show how to update the lower bound and we compare the efficiency of several lower bounding techniques.
Matheuristics for the Temporal Bin Packing Problem
F. Furini and X. Shen
11th Metaheuristics International Conference (MIC 2015), Agadir, Morocco, June 2015 (13 pages) , 2015
We study an extension of the Bin Packing Problem, where items consume the bin capacity during a time window only. The problem asks for finding the minimum number of bins to pack all the items respecting the bin capacity at any instant of time. Both a polynomial-size formulation and an extensive formulation are studied. Moreover, various heuristic algorithms are developed and compared, including greedy heuristics and a column generation based heuristic. We perform extensive computational experiments on benchmark instances to evaluate the quality of the computed solutions with respect to strong bounds based on the linear programming relaxation of the proposed formulations.
Generation of antipodal random vectors with prescribed non-stationary second-order statistics
A. Caprara, F. Furini , A. Lodi, M. Mangia, R. Rovatti and G. Setti
IEEE Transactions on Signal Processing , 2014
A Look-Up-Table-based method is proposed to generate random instances of an antipodal n-dimensional vector so that its 2-nd order statistics are as close as possible to a given specification. The method is based on linear optimization and exploits column-generation techniques to cope with the exponential complexity of the task. It yields a LUT whose storage requirements are only O(n^3) and thus are compatible with hardware implementation for non-negligible n. Applications are shown in the fields of Compressive Sensing and of Ultra Wide Band systems based on Direct Sequence - Code Division Multiple Acces.
Mathematical Formulations for the Balanced Vertex k -Separator Problem
D. Cornaz, F. Furini , M. Lacroix, E. Malaguti, A. R. Mahjoub, S. Martin
International Conference on Control, Decision and Information Technologies (CoDIT 2014), Metz, France, November 2014 (8 pages) , 2014
Given an undirected graph G = (V, E), a Vertex k-Separator is a subset of the vertex set V such that, when the separator is removed from the graph, the remaining vertices can be partitioned into k subsets that are pairwise edge-disconnected. In this paper we focus on the Balanced Vertex k-Separator Problem, i.e., the problem of finding a minimum cardinality separator such that the sizes of the resulting disconnected subsets are balanced. We present a compact Integer Linear Programming formulation for the problem, and present a polyhedral study of the associated polytope. We also present an Exponential-Size formulation, for which we derive a column generation and a branching scheme. Preliminary computational results are reported comparing the performance of the two formulations on a set of benchmark instances.
State space reduced dynamic programming for the aircraft sequencing problem with constrained position shifting
F. Furini , M. P. Kidd, A. Persiani, P. Toth
4th International Symposium on Combinatorial Optimization (ISCO 2014), Lisbon, Portugal, March 2014 (12 pages) , 2014
In this paper we present state space reduction techniques for a dynamic programming algorithm applied to the Aircraft Sequencing Problem (ASP) with Constrained Position Shifting (CPS). We consider the classical version of the ASP, which calls for determining the order in which a given set of aircraft should be assigned to a runway at an airport, subject to minimum separations in time between consecutive aircraft, in order to minimize the sum of the weighted deviations from the scheduled arrival/departure times of the aircraft. The focus of the paper is on a number of ways of improving the computation times of the dynamic programming algorithm proposed. This is achieved by using heuristic upper bounds and a completion lower bound in order to reduce the state space in the dynamic programming algorithm. We compare our algorithm to an approach based on mixed integer linear programming, which was adapted from the literature for the case of CPS. We show using real-world air traffic instances from the Milan Linate Airport that the dynamic programming algorithm significantly outperforms the MILP. Furthermore, we show that the proposed algorithm is capable of solving very large instances in short computation times, and that it is suitable for use in a real-time setting.
A fast heuristic approach for train timetabling in a railway node
F. Furini , M. P. Kidd
6th International Network Optimization Conference (INOC 2013), Tenerife, Spain, May 2013 (8 pages) , 2013
We consider a conflict-free scheduling problem which arises in railway networks, where ideal timetables have been provided for a set of trains, but where these timetables may be conflicting. We use a space-time graph approach from the railway scheduling literature in order to develop a fast heuristic which resolves conflicts by adjusting the ideal timetables while attempting to minimize the deviation from the ideal timetable. Our approach is tested on realistic data obtained from the railway node of Milan.
Hybrid SDP Bounding Procedure
F. Furini , E. Traversi
12th International Symposium on Experimental Algorithms (SEA 2013), Rome, Italy, June 2013 (12 pages) , 2013
The principal idea of this paper is to exploit Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers when tackling Binary Quadratic Problems. We included the SDP relaxation in a state-of-the-art MINLP solver as an additional bounding technique and demonstrated that this idea could be computationally useful. The Quadratic Stable Set Problem is adopted as the case study. The tests indicate that the Hybrid SDP Bounding Procedure allows an average 50% cut of the overall computing time and a cut of more than one order of magnitude for the branching nodes.
Models for the Two-Dimensional Two-Stage Cutting Stock Problem with Multiple Stock Size
F. Furini , E. Malaguti
Computer & Operations Research , 2013
We consider a Two-Dimensional Cutting Stock Problem (2DCSP) where stock of different sizes is available, and a set of rectangular items has to be obtained through two-stage guillotine cuts. We propose and computationally compare three Mixed-Integer Programming models for the 2DCSP developing formulations from the literature. The first two models have a polynomial and pseudo-polynomial number of variables, respectively, and can be solved with a general-purpose MIP solver. The third model, having an exponential number of variables, is solved via branch-and-price techniques. We conclude the paper describing the results of extensive computational experiments on a set of benchmark instances from the literature.
Uncommon Dantzig-Wolfe Reformulation for the Temporal Knapsack Problem
A. Caprara, F. Furini , E. Malaguti
INFORMS Journal on Computing , 2013
We study a natural generalization of the knapsack problem, in which each item exists only for a given time interval. One has to select a subset of the items (as in the classical case), guaranteeing that for each time instant the set of existing selected items has total weight not larger than the knapsack capacity. We focus on the exact solution of the problem, noting that prior to our work the best method was the straightforward application of a general-purpose solver to the natural ILP formulation. Our results indicate that much better results can be obtained by using the same general-purpose solver to tackle a nonstandard Dantzig-Wolfe reformulation in which subproblems are associated with groups of constraints. This is also interesting since the more natural Dantzig-Wolfe reformulation of single constraints performs extremely poorly in practice.
A Column Generation Heuristic for the Two-Dimensional Two-Staged Guillotine Cutting Stock Problem with Multiple Stock Size
F. Furini , E. Malaguti, R. Medina Durán, A. Persiani, P. Toth
European Journal of Operational Research , 2012
We consider a Two-Dimensional Cutting Stock Problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as subproblem the solution of a Two-Dimensional Knapsack Problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a Mixed Integer Linear Programming Model for the solution of this Knapsack Problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al..
Aircraft Sequencing Problems via a Rolling Horizon Algorithm
F. Furini , C. Persiani, P. Toth
3rd International Symposium on Combinatorial Optimization (ISCO 2012), Athens, Greece, April 2012 (12 pages) , 2012
Aircraft sequencing on the runway is a challenging optimization problem that aims to reduce the delays and the air traffic controllers workload in a scenario characterized by a continuous growth of the air transportation demand. In this paper we consider the problem of sequencing both arrivals and departures on a single runway airport. We formalize the problem using a Mixed Integer Programming Model and we propose a rolling horizon solution approach. Computational results on real-world air traffic instances from the Milano Linate Airport are reported. The results show that the proposed approach is able to significantly improve on the First Come First Served (FCFS) sequence.
Exact Weighted Vertex Coloring via Branch-and-Price
F. Furini , E. Malaguti
Discrete Optimization , 2012
We consider the Weighted Vertex Coloring Problem (WVCP), in which a positive weight is associated to each vertex of a graph. In WVCP, one is required to assign a color to each vertex in such a way that colors on adjacent vertices are different, and the objective is to minimize the sum of the costs of the colors used, where the cost of each color is given by the maximum weight of the vertices assigned to that color. This NP-hard problem arises in practical scheduling applications, where it is also known as Scheduling on a Batch Machine with Job Compatibilities. We propose the first exact algorithm for the problem, which is based on column generation and branch-and-price. Computational results on a large set of instances from the literature are reported, showing excellent performance when compared with the best heuristic algorithms from the literature.
Partial convexification of general MIPs by Dantzig-Wolfe reformulation
M. Bergner, A. Caprara, F. Furini , M.E. Lübbecke, E. Malaguti, E. Traversi
15th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2011), New York, USA, June 2011 (12 pages) , 2011
Dantzig-Wolfe decomposition is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs) in practice. However, the method is not implemented in any state-of-the-art MIP solver: it needs tailoring to the particular problem; the decomposition must be determined from the typical bordered block-diagonal matrix structure; the resulting column generation subproblems must be solved efficiently; etc. We provide a computational proof-of-concept that the process can be automated in principle, and that strong dual bounds can be obtained on general MIPs for which a solution by a decomposition has not been the first choice. We perform an extensive computational study on the 0-1 dynamic knapsack problem (without block-diagonal structure) and on general MIPLIB2003 instances. Our results support that Dantzig-Wolfe reformulation may hold more promise as a ge-ne-ral-pur-pose tool than previously acknowledged by the research community.