Domenico Salvagnin
Department of Information Engineering, Padova
Publications

1.Fast Approaches to Improve the Robustness of a Railway TimetableTransportation Science 43:321335, 2009
Abstract:
The Train Timetabling Problem (TTP) consists in finding a train schedule on a railway network that satisfies some operational constraints and maximizes some profit function which counts for the efficiency of the infrastructure usage. In practical cases, however, the maximization of the objective function is not enough and one calls for a robust solution that is capable of absorbing as much as possible delays/disturbances on the network. In this paper we propose and analyze computationally four different methods to improve the robustness of a given TTP solution for the aperiodic (non cyclic) case. The approaches combine Linear Programming (LP) and adhoc Stochastic Programming/Robust Optimization techniques. We compare computationally the effectiveness and practical applicability of the four techniques under investigation on realworld test cases from the Italian railway company (Trenitalia). The outcome is that two of the proposed techniques are very fast and provide robust solutions of comparable quality with respect to the standard (but very time consuming) Stochastic Programming approach.
Bibtex
@article{FSZ09, Author = {Matteo Fischetti and Domenico Salvagnin and Arrigo Zanette}, Journal = {Transportation Science}, Number = {3}, Pages = {321335}, Title = {Fast approaches to improve the robustness of a railway timetable}, Volume = {43}, Year = {2009} }

2.Just MIP it!V. Maniezzo, T. Stuetzle, S. Voss, Eds., MATHEURISTICS: Hybridizing metaheuristics and mathematical programming, Annals of Information Systems 10:3970, 2009
Abstract:
Modern MixedInteger Programming (MIP) solvers exploit a rich arsenal of tools to attack hard problems. It is widely accepted by the OR community that the solution of very hard MIPs can take advantage from the solution of a series of timeconsuming auxiliary Linear Programs (LPs) intended to enhance the performance of the overall MIP solver. E.g., auxiliary LPs may be solved to generate powerful disjunctive cuts, or to implement a strong branching policy. Also well established is the fact that finding goodquality heuristic MIP solutions often requires a computing time that is just comparable to that needed to solve the LP relaxations. So, it makes sense to think of a new generation of MIP solvers where auxiliary MIPs (as opposed to LPs) are heuristically solved on the fly, with the aim of bringing the MIP technology under the chest of the MIP solver itself. This leads to the idea of “translating into a MIP model” (MIPping) some crucial decisions to be taken within a MIP algorithm (How to cut? How to improve the incumbent solution? Is the current node dominated?). In this paper we survey a number of successful applications of the above approach.
Bibtex
@incollection{JMIPit, Author = {Matteo Fischetti and Andrea Lodi and Domenico Salvagnin}, Booktitle = {Matheuristics}, Editor = {V. Maniezzo and T. Stuetzle and S. Voss}, Pages = {3970}, Publisher = {Springer US}, Series = {Annals of Information Systems}, Title = {Just MIP it!}, Volume = {10}, Year = {2010} }

3.Feasibility Pump 2.0Mathematical Programming Computation 1:201222, 2009
Abstract:
Finding a feasible solution of a given MixedInteger Programming (MIP) model is a very important NPcomplete problem that can be extremely hard in practice. Feasibility Pump (FP) is a heuristic scheme for finding a feasible solution to general MIPs that can be viewed as a clever way to round a sequence of fractional solutions of the LP relaxation, until a feasible one is eventually found. In this paper we study the effect of replacing the original rounding function (which is fast and simple, but somehow blind) with more clever rounding heuristics. In particular, we investigate the use of a divinglike procedure based on rounding and constraint propagation — a basic tool in Constraint Programming. Extensive computational results on binary and general integer MIPs from the literature show that the new approach produces a substantial improvement of the FP success rate, without slowingdown the method and with a significantly better quality of the feasible solutions found.
Bibtex
@article{FP2, Author = {Matteo Fischetti and Domenico Salvagnin}, Journal = {Mathematical Programming Computation}, Number = {23}, Pages = {201222}, Title = {Feasibility Pump 2.0}, Volume = {1}, Year = {2009} }

4.Pruning MovesINFORMS Journal on Computing 22:108119, 2010
Abstract:
The concept of dominance among nodes of a branchandbound tree, although known for a long time, is typically not exploited by generalpurpose mixedinteger linear programming (MILP) codes. The starting point of our work was the generalpurpose dominance procedure proposed in the 1980s by Fischetti and Toth, where the dominance test at a given node of the branchandbound 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 nodefathoming 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.
Bibtex
@article{PMoves, Author = {Matteo Fischetti and Domenico Salvagnin}, Journal = {INFORMS Journal on Computing}, Number = {1}, Pages = {108119}, Title = {Pruning Moves}, Volume = {22}, Year = {2010} }

5.A note on the selection of Benders’ cutsMathematical Programming B 124:175182, 2010
Abstract:
A new cut selection criterion for Benders’ cuts is proposed and computationally analyzed. The results show that the new criterion is more robust—and often considerably faster—than the standard ones.
Bibtex
@article{Benders, Author = {Matteo Fischetti and Domenico Salvagnin and Arrigo Zanette}, Journal = {Mathematical Programming B}, Pages = {175182}, Title = {A note on the selection of {B}enders' cuts}, Volume = {124}, Year = {2010} }

6.Finding the Next Solution in Constraint and Preferencebased Knowledge Representation FormalismsKR 2010 Proceedings, 425433
Abstract:
In constraint or preference reasoning, a typical task is to compute a solution, or an optimal solution. However, when one has already a solution, it may be important to produce the next solution following the given one in a linearization of the solution ordering where more preferred solutions are ordered first. In this paper, we study the computational complexity of finding the next solution in some common preferencebased representation formalisms. We show that this problem is hard in general CSPs, but it can be easy in treeshaped CSPs and treeshaped fuzzy CSPs. However, it is difficult in weighted CSPs, even if we restrict the shape of the constraint graph. We also consider CPnets, showing that the problem is easy in acyclic CPnets, as well as in constrained acyclic CPnets where the (soft) constraints are treeshaped and topologically compatible with the CPnet.
Bibtex
@inproceedings{Next, Author = {Ronen Brafman and Francesca Rossi and Domenico Salvagnin and Kristen Brent Venable and Toby Walsh}, Booktitle = {Principles of Knowledge Representation and Reasoning}, Pages = {425433}, Title = {Finding the Next Solution in Constraint and Preferencebased Knowledge Representation Formalisms}, Year = {2010} }

7.An InOut Approach to Disjunctive OptimizationCPAIOR 2010 Proceedings, 136140
Abstract:
Cutting plane methods are widely used for solving convex optimization problems and are of fundamental importance, e.g., to provide tight bounds for MixedInteger Programs (MIPs). This is obtained by embedding a cutseparation module within a search scheme. The importance of a sound search scheme is well known in the Constraint Programming (CP) community. Unfortunately, the "standard" search scheme typically used for MIP problems, known as the Kelley method, is often quite unsatisfactory because of saturation issues. In this paper we address the socalled LiftandProject closure for 01 MIPs associated with all disjunctive cuts generated from a given set of elementary disjunction. We focus on the search scheme embedding the generated cuts. In particular, we analyze a general metascheme for cutting plane algorithms, called inout search, that was recently proposed by BenAmeur and Neto. Computational results on test instances from the literature are presented, showing that using a more clever meta scheme on top of a blackbox cut generator may lead to a significant improvement.
Bibtex
@inproceedings{Yoyo, Author = {Matteo Fischetti and Domenico Salvagnin}, Booktitle = {CPAIOR}, Pages = {136140}, Title = {An InOut Approach to Disjunctive Optimization}, Year = {2010} }

8.A RelaxandCut Framework for Gomory’s MixedInteger CutsMathematical Programming Computation 3:79102, 2011
Abstract:
Gomory MixedInteger Cuts (GMICs) are widely used in modern branchandcut codes for the solution of MixedInteger Programs. Typically, GMICs are iteratively generated from the optimal basis of the current Linear Programming (LP) relaxation, and immediately added to the LP before the next round of cuts is generated. Unfortunately, this approach is prone to instability. In this paper we analyze a different scheme for the generation of rank1 GMICs read from a basis of the original LP—the one before the addition of any cut. We adopt a relaxandcut approach where the generated GMICs are not added to the current LP, but immediately relaxed in a Lagrangian fashion. Various elaborations of the basic idea are presented, that lead to very fast—yet accurate—variants of the basic scheme. Very encouraging computational results are presented, with a comparison with alternative techniques from the literature also aimed at improving the GMIC quality. We also show how our method can be integrated with other cut generators, and successfully used in a cutandbranch enumerative framework.
Bibtex
@article{RelaxCut, Author = {Matteo Fischetti and Domenico Salvagnin}, Journal = {Mathematical Programming Computation}, Pages = {79102}, Title = {A RelaxandCut Framework for Gomory's MixedInteger Cuts}, Volume = {3}, Year = {2011} }

9.MIPLIB 2010  Mixed Integer Programming Library version 5Mathematical Programming Computation 3:103163, 2011
Abstract:
This paper reports on the fifth version of the Mixed Integer Programming Library. The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today’s codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.
Bibtex
@article{MIPLIB2010, Author = {Thorsten Koch and Tobias Achterberg and Erling Andersen and Oliver Bastert and Timo Berthold and Robert E. Bixby and Emilie Danna and Gerald Gamrath and Ambros M. Gleixner and Stefan Heinz and Andrea Lodi and Hans Mittelmann and Ted Ralphs and Domenico Salvagnin and Daniel E. Steffy and Kati Wolter}, Journal = {Mathematical Programming Computation}, Pages = {103163}, Title = {{MIPLIB} 2010  {M}ixed {I}nteger {P}rogramming {L}ibrary version 5}, Volume = {3}, Year = {2011} }

10.Three ideas for the Quadratic Assignment ProblemOperations Research 60:954964, 2012
Abstract:
We address the exact solution of the famous esc instances of the quadratic assignment problem. These are extremely hard instances that remained unsolved—even allowing for a tremendous computing power—by using all previous techniques from the literature. During this challenging task we found that three ideas were particularly useful, and qualified as a breakthrough for our approach. The present paper is about describing these ideas and their impact in solving esc instances. Our method was able to solve, in a matter of seconds or minutes on a single PC, all easy cases (all esc16* plus esc32e and esc32g). The three previouslyunsolved esc32c, esc32d and esc64a were solved in less than half an hour, in total, on a single PC. We also report the solution in about 5 hours of the previouslyunsolved tai64c. By using a facilityflow splitting procedure, we were finally able to solve to proven optimality, for the first time, both esc32h (in about 2 hours) as well as "the big fish" esc128 (to our great surprise, the solution of the latter required just a few seconds on a single PC).
Bibtex
@article{QAP, Author = {Matteo Fischetti and Michele Monaci and Domenico Salvagnin}, Journal = {Operations Research}, Number = {4}, Pages = {954964}, Title = {Three ideas for the Quadratic Assignment Problem}, Volume = {60}, Year = {2012} }

11.Winner determination in voting trees with incomplete preferences and weighted votesAutonomous Agents and MultiAgent Systems 25:130157, 2012
Abstract:
In multiagent settings where agents have different preferences, preference aggregation can be an important issue. Voting is a general method to aggregate preferences. We consider the use of voting tree rules to aggregate agents’ preferences. In a voting tree, decisions are taken by performing a sequence of pairwise comparisons in a binary tree where each comparison is a majority vote among the agents. Incompleteness in the agents’ preferences is common in many reallife settings due to privacy issues or an ongoing elicitation process. We study how to determine the winners when preferences may be incomplete, not only for voting tree rules (where the tree is assumed to be fixed), but also for the Schwartz rule (in which the winners are the candidates winning for at least one voting tree). In addition, we study how to determine the winners when only balanced trees are allowed. In each setting, we address the complexity of computing necessary (respectively, possible) winners, which are those candidates winning for all completions (respectively, at least one completion) of the incomplete profile. We show that many such winner determination problems are computationally intractable when the votes are weighted. However, in some cases, the exact complexity remains unknown. Since it is generally computationally difficult to find the exact set of winners for voting trees and the Schwartz rule, we propose several heuristics that find in polynomial time a superset of the possible winners and a subset of the necessary winners which are based on the completions of the (incomplete) majority graph built from the incomplete profiles.
Bibtex
@article{Winner, Author = {Jerome Lang and Maria Silvia Pini and Francesca Rossi and Domenico Salvagnin and Kristen Brent Venable and Toby Walsh}, DateAdded = {20111117 12:25:26 +0100}, DateModified = {20120218 08:49:33 +0000}, Journal = {Autonomous Agents and MultiAgent Systems}, Pages = {130157}, Title = {Winner determination in voting trees with incomplete preferences and weighted votes}, Volume = {25}, Year = {2012} }

12.A hybrid MIP/CP approach for multiactivity shift schedulingCP Proceedings 633646, 2012
Abstract:
We propose a hybrid MIP/CP approach for solving multiactivity shift scheduling problems, based on regular languages that partially describe the set of feasible shifts. We use an aggregated MIP relaxation to capture the optimization part of the problem and to get rid of symmetry. Whenever the MIP solver generates a integer solution, we use a CP solver to check whether it can be turned into a feasible solution of the original problem. A MIPbased heuristic is also developed. Computational results are reported, showing that the proposed method is a promising alternative compared to the stateoftheart.
Bibtex
@inproceedings{Regular, Author = {Domenico Salvagnin and Toby Walsh}, Booktitle = {CP}, Pages = {633646}, Title = {A hybrid MIP/CP approach for multiactivity shift scheduling}, Year = {2012} }

13.Approximating the split closureINFORMS Journal on Computing 25:808819, 2013
Abstract:
The split closure has been proved in practice to be a very tight approximation of the integer hull formulation of a generic mixedinteger 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 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.
Bibtex
@article{SplitApprox, Author = {Matteo Fischetti and Domenico Salvagnin}, Journal = {INFORMS Journal on Computing}, Number = {4}, Pages = {808819}, Title = {Approximating the split closure}, Volume = {25}, Year = {2013} }

14.Cloud BranchingCPAIOR 2013 Proceedings, 2843
Abstract:
Branchandbound methods for mixedinteger programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper we study branching strategies for mixedinteger programs that exploit the knowledge of multiple alternative optimal solutions (a cloud) of the current LP relaxation. These strategies naturally extend stateoftheart methods like strong branching, pseudocost branching, and their hybrids. We show that by exploiting dual degeneracy, and thus multiple alternative optimal solutions, it is possible to enhance traditional methods. We present preliminary computational results, applying the newly proposed strategy to full strong branching, which is known to be the MIP branching rule leading to the fewest number of search nodes. It turns out that cloud branching can reduce the mean running time by up to 30% on standard test sets.
Bibtex
@inproceedings{Cloud, Author = {Timo Berthold and Domenico Salvagnin}, Booktitle = {CPAIOR}, Pages = {2843}, Title = {Cloud Branching}, Year = {2013} }

15.Orbital Shrinking: a new tool for hybrid MIP/CP methodsCPAIOR 2013 Proceedings, 204215
Abstract:
Orbital shrinking is a newly developed technique in the MIP community to deal with symmetry issues, which is based on aggregation rather than on symmetry breaking. In a recent work, a hybrid MIP/CP scheme based on orbital shrinking was developed for the multiactivity shift scheduling problem, showing significant improvements over previous pure MIP approaches. In the present paper we show that the scheme above can be extended to a general framework for solving arbitrary symmetric MIP instances. This framework naturally provides a new way for devising hybrid MIP/CP decompositions. Finally, we specialize the above framework to the multiple knapsack problem. Computational results show that the resulting method can be orders of magnitude faster than pure MIP approaches on hard symmetric instances.
Bibtex
@inproceedings{Mkp, Author = {Domenico Salvagnin}, Booktitle = {CPAIOR}, Pages = {204215}, Title = {Orbital Shrinking: a new tool for hybrid MIP/CP methods}, Year = {2013} }

16.The strength of multirow modelsMathematical Programming Computation (to appear)
Abstract:
We develop a computational method for computing valid inequalities for any mixedinteger set PJ. Our implementation takes the form of a separator and is capable of returning only facetdefining inequalities for conv(PJ). The separator is not comparable in speed with the specific cuttingplane generators used in branchandcut solvers, but it is generalpurpose. We can thus use it to compute cuts derived from any reasonably small relaxation PJ of a general mixedinteger problem, even when there exists no specific implementation for computing cuts with PJ. Exploiting this, we evaluate, from a computational perspective, the usefulness of cuts derived from several types of multirow relaxations. In particular, we present results with four different strengthenings of the tworow intersection cut model, and multirow models with up to fifteen rows. We conclude that only fullystrengthened tworow cuts seem to offer a significant advantage over tworow intersection cuts. Our results also indicate that the improvement obtained by going from models with very few rows to models with up to fifteen rows may not be worth the increased computing cost.
Bibtex


17.Tree Search Stabilization by Random Sampling(submitted)
Abstract:
We discuss the variability in the performance of multiple runs of Mixed Integer Linear solvers, and we concentrate on the one deriving from the use of different optimal bases of the Linear Programming relaxations. We propose a new algorithm exploiting more than one of those bases and we show that different versions of the algorithm can be used to stabilize and improve the performance of the solver.
Bibtex


18.Exact and Heuristic Approaches for Directional Sensor Control(submitted)
Abstract:
Directional sensors are gaining importance due to applications, including surveillance, detection, and tracking. Such sensors have a limited fieldofview and a discrete set of directions they can be pointed to. The Directional Sensor Control problem (DSCP) consists in assigning a direction of view to each sensor. The location of the targets is known with uncertainty given by a joint apriori Gaussian distribution, while sensor locations are known exactly. In this paper we study exact and heuristic approaches for the DSCP with the goal of maximizing information gain on the location of a given set of immobile target objects. In particular, we propose an exact mixed integer convex programming (MICP) formulation to be solved by a blackbox MICP solver and several metaheuristic approaches based on local search. A computational evaluation shows the very good performance of both methods.
Bibtex


19.On Solving a Hard Quadratic 3Dimensional Assignment Problem(submitted)
Abstract:
We address the solution of a very challenging (and previously unsolved) instance of the quadratic 3dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to optimality, from the choice of an appropriate mixedinteger programming formulation, to cutting planes and symmetry handling. Using these techniques we were able to solve the target instance with moderate computational effort (2.5 million nodes and one week of computations on a standard PC).
Bibtex


20.Detecting and exploiting permutation structures in MIPsCPAIOR 2014 Proceedings, 2944
Abstract:
Many combinatorial optimization problems can be formulated as the search for the best possible permutation of a given set of objects, according to a given objective function. The corresponding MIP formulation is thus typically made of an assignment substructure, plus additional constraints and variables (as needed) to express the objective function. Unfortunately, the permutation structure is generally lost when the model is flattened out as a mixed integer program, and stateoftheart MIP solvers do not take full advantage of it. In the present paper we propose a heuristic procedure to detect permutation problems from their MIP formulation, and show how we can take advantage of this knowledge to speedup the solution process. Computational results on quadratic assignment and single machine scheduling problems show that the technique, when embedded in a stateoftheart MIP solver, can indeed improve performance.
Bibtex


21.Selfsplitting of workload in parallel computationCPAIOR 2014 Proceedings, 394404
Abstract:
Parallel computation requires splitting a job among a set of processing units called workers. The computation is generally performed by a set of one or more master workers that split the workload into chunks and distribute them to a set of slave workers. To guarantee correctness and achieve a desirable balancing of the split (needed for scalability), many schemes introduce a (possibly large) overhead due to communication/synchronization among the involved workers. We propose a simple mechanism to avoid the communication issues of the approach above. In the new paradigm, called SelfSplit, each worker is able to autonomously determine, without any communication with the other workers, the job parts it has to process. The above feature makes the scheme very suited for those applications where communication among workers is time consuming or unreliable. In particular, it allows for a simple yet effective parallelization of divideandconquer algorithms with a short input that produce a very large number of timeconsuming job parts, as it happens, e.g., when an NPhard problem is solved by an enumerative method. Computational results are reported, showing that SelfSplit can achieve an almost linear speedup for hard Constraint Programming applications, even when 64 workers are considered.
Bibtex


22.Orbital Shrinking: Theory and Applications(submitted)
Abstract:
Symmetry plays an important role in optimization. The usual approach to cope with symmetry in discrete optimization is to try to eliminate it by introducing artificial symmetrybreaking conditions into the problem, and/or by using an adhoc search strategy. This is the common approach in both the mixedinteger programming (MIP) and constraint programming (CP) communities. In this paper we argue that symmetry is instead a beneficial feature that we should preserve and exploit as much as possible, breaking it only as a last resort. To this end, we outline a new approach, that we call orbital shrinking, where additional integer variables expressing variable sums within each symmetry orbit are introduced and used to ``encapsulate'' model symmetry. This leads to a discrete relaxation of the original problem, whose solution yields a bound on its optimal value. Then, we show that orbital shrinking can be turned into an exact method for solving arbitrary symmetric MIP instances. The proposed method naturally provides a new way for devising hybrid MIP/CP decompositions. Finally, we report computational results on two specific applications of the method, namely the multiactivity shift scheduling and the multiple knapsack problem, showing that the resulting method can be orders of magnitude faster than pure MIP or CP approaches.
Bibtex


23.Selfsplit parallelization for Mixed Integer Linear Programming(submitted)
Abstract:
SelfSplit is a simple mechanism to convert a sequential treesearch code into a parallel one. In this paradigm, treesearch is distributed among a set of workers, each of which is able to autonomously determinewithout any communication with the other workersthe job parts it has to process. SelfSplit already proved quite effective in parallelizing Constraint Programming solvers. In the present paper we investigate the performance of SelfSplit when applied to a MixedInteger Linear Programming (MILP) solver. Both adhoc and general purpose MILP codes have been considered. Computational results show that SelfSplit, in spite of its simplicity, can achieve good speedups even in the MILP context. The role of performance variability in limiting scalability is also discussed.
Bibtex


24.MixedInteger Linear Programming Heuristics for the PrePack Optimization Problem(submitted)
Abstract:
In this paper we consider a packing problem arising in inventory allocation applications, where the operational cost for packing the bins is comparable, or even higher, than the cost of the bins (and of the items) themselves. This is the case, for example, of warehouses that have to manage a large number of different customers (e.g., stores), each requiring a given set of items. For this problem, we present MixedInteger Linear Programming heuristics based on problem substructures that lead to easytosolve and meaningful subproblems, and exploit them within an overall metaheuristic framework. The new heuristics are evaluated on a standard set of instances, and benchmarked against known heuristics from the literature. Computational experiments show that very good (often proven optimal) solutions can consistently be computed in short computing times.
Bibtex
