Mathematical Programming manuscript No. (will be inserted by the editor) (2008)
Matteo Fischetti, Andrea Lodi, Andrea Tramontani
the date of receipt and acceptance should be inserted later Abstract. Disjunctive cuts for Mixed-Integer Linear Programs have been introduced by Egon Balas in the late 70’s, and successfully...
Mathematical Programming manuscript No. (will be inserted by the editor) (2008)
Optimizing over the first Chvátal closure
Combinatorial Benders’ Cuts for Mixed-Integer Linear Programming (2008)
Gianni Codato, Matteo Fischetti
Mixed-Integer Programs (MIP’s) involving logical implications modelled through big-M coefficients, are notoriously among the hardest to solve. In this paper we propose and analyze computationally...
Kumar Abhishek, Ashutosh Mahajan, Matteo Fischetti, Fred Glover, Andrea Lodi, The Feasibility
Finding a feasible solution for MIP is NP-Hard and is difficult in practice for some important models and
Solving the Prize-Collecting Steiner Tree Problem to Optimality ⋆ (2008)
Ivana Ljubi, René Weiskircher, Ulrich Pferschy, Gunnar Klau, Petra Mutzel, Ivana Ljubić, ...
www.cg.tuwien.ac.at
Minimal Infeasible Subsystems and Benders cuts (2008)
Matteo Fischetti, Domenico Salvagnin, Arrigo Zanette
There are many situations in mathematical programming where cutting planes can be generated by solving a certain “cut generation linear program ” whose feasible solutions define a family of valid...
Fischetti, Matteo, Widmayer, Peter
The 8th ATMOS workshop was held in Karlsruhe, September 18, 2008, within ALGO, a set of meetings related to algorithms. The series of ATMOS workshops, starting in Heraklion in 2001, continuing in...
Fischetti, Matteo, Widmayer, Peter
Proceedings of the 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, held on Septmeber 18 in Karlsruhe, Germany.
A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem (2007)
Matteo Fischetti, Andrea Lodi, Paolo Toth
The Vehicle Scheduling Problem is an important combinatorial optimization problem arising in the management of transportation companies. It consists in assigning a set of time-tabled trips to a set...
The symmetric Generalized Travelling Salesman Problem (GTSP) is a variant of the classical symmetric Travelling Salesman Problem, in which the nodes are partitioned into clusters and the salesman has...
Alberto Caprara, Matteo Fischetti, Ax B
Given the integer polyhedron P I: = convfx 2 Z n: Ax bg, where A 2 Z m\Thetan and b 2 Z m
Modeling and Solving the (2007)
Train Timetabling Problem, Alberto Caprara, Matteo Fischetti, Paolo Toth
The Train Timetabling Problem aims at determining a periodic timetable for a set of trains which does not violate track capacities and satises some operational constraints. In particular, we...
We consider a variant of the classical symmetric Travelling Salesman Problem in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. This...
Matteo Fischetti, Juan Jose Salazar
In this paper we provide new theoretical models and practical solution techniques for protecting condentiality in statistical tables containing sensitive information that cannot be disseminated. This...
Alberto Caprara, Matteo Fischetti, Paolo Toth, Daniele Vigo, Pier Luigi Guida
Crew management is concerned with building the work schedules of crews needed to cover a planned timetable. This is a well-known problem in Operations Research and has been historically associated...
Internet: www.erim.eur.nl Bibliographic data and classifications of all the ERIM reports are also available on the ERIM website: www.erim.eur.nl
Konrad-Zuse-Zentrum fur Informationstechnik Berlin (2007)
Norbert Ascheuer, Norbert Ascheuer, Matteo Fischetti, Matteo Fischetti, Martin Grotschel, Martin Grotschel
A polyhedral study of the asymmetric travelling salesman problem with time windows Preprint SC 97--11 (February 1997) A polyhedral study of the asymmetric travelling salesman problem with time windows
A Feasibility Pump Heuristic for General Mixed-Integer Problems,’’ Discrete Optimization 4 (2007)
Livio Bertacco, Matteo Fischetti, Andrea Lodi
Finding a feasible solution of a given Mixed-Integer Programming (MIP) model is a very important (NP-complete) problem that can be extremely hard in practice. Very recently, Fischetti, Glover and...
A Local Dominance Procedure for Mixed-Integer Linear Programming (2007)
Matteo Fischetti, Domenico Salvagnin
Among the hardest Mixed-Integer Linear Programming (MILP) problems, the ones that exhibit a symmetric nature are particularly important in practice, as they arise in both theoretical and practical...
10. Fast Approaches to Robust Railway Timetabling (2007)
Fischetti, Matteo, Zanette, Arrigo, Salvagnin, Domenico
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...
Projected Chvátal-Gomory cuts for Mixed Integer Linear Programs (2006)
Pierre Bonami, Gérard Cornuéjols, Sanjeeb Dash, Matteo Fischetti, Andrea Lodi
Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure Integer Linear Program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize...
Mixed-integer cuts from cyclic groups (2005)
Matteo Fischetti, Cristiano Saturni
We analyze a separation procedure for Mixed-Integer Programs related to the work of Gomory and Johnson on interpolated subadditive functions. This approach has its roots in the Gomory-Johnson...
A.: Repairing mip infeasibility through local branching (2005)
Finding a feasible solution to a generic Mixed-Integer Program (MIP) is often a very difficult task. Recently, two heuristic approaches called Feasibility Pump and Local Branching have been proposed...
How tight is the corner relaxation? (2005)
Matteo Fischetti, Michele Monaci
Given a mixed-integer linear programming (MILP) model and an optimal basis of the associated linear programming relaxation, the Gomory’s corner relaxation is obtained by dropping nonnegativity...
Local Branching: Basics and Extensions (2005)
The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate...
Matteo Fischetti, Fred Glover, Andrea Lodi
In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min{cT x: Ax ≥ b, xj integer ∀j ∈ I}. Trivially, a feasible...
Solving the Prize-Collecting Steiner Tree Problem (2004)
Ivana Lubic, Ivana Ljubić, René Weiskircher, René Weiskircher, Ulrich Pferschy, Ulrich Pferschy, ...
The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total...
Matteo Fischetti, Carlo Polo, Massimo Scantamburlo
Effective heuristic solution methods for general Mixed-Integer Programs (MIPs) are strongly required in many practical applications, and have been the subject of an intensive research effort in the...
Solution of real-world train timetabling problems (2001)
Alberto Caprara, Michele Monaci, Paolo Toth, Matteo Fischetti, Pier Luigi Guida
The Train Timetabling Problem (TTP) aims at determining a timetable for a set of trains which does not violate track capacities and satises some operational constraints. We concentrate on the problem...
On the separation of maximally violated mod-k cuts (2000)
Alberto Caprara, Matteo Fischetti, Adam N. Letchford
Abstract. Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the...
On the separation of maximally violated mod-k cuts (2000)
Alberto Caprara, Matteo Fischetti, Adam N. Letchford, Ax B
Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research eort has been devoted to the denition of...
Models and Algorithms for Optimizing Cell Suppression in Tabular Data with Linear Constraints (2000)
Cell suppression is a widely-used technique for protecting sensitive information in statistical data presented in tabular form. Previous works on the subject mainly concentrate on 2- and...
Models and Algorithms for Optimizing Cell Suppression in Tabular Data with Linear Constraints (2000)
Cell suppression is a widely-used technique for protecting sensitive information in statistical data presented in tabular form. Previous works on the subject mainly concentrate on 2- and...
Models and Algorithms for Optimizing Cell Suppression in Tabular Data with Linear Constraints (2000)
Cell suppression is a widely-used technique for protecting sensitive information in statistical data presented in tabular form. Previous works on the subject mainly concentrate on 2- and...
A polyhedral study of the asymmetric travelling salesman problem with time Windows (2000)
Norbert Ascheuer, Matteo Fischetti, Martin Grötschel
The asymmetric traveling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper, we present a formulation of the problem involving only...
Matteo Fischetti, Juan Jose Salazar
We study the problem of protecting sensitive data in a statistical two-dimensional table, when the non-sensitive table entries are made public along with the row and column totals. In particular, we...
Solution of large-scale railway crew planning problems: the italian experience (1999)
Alberto Caprara, Matteo Fischetti, Pier Luigi Guida, Paolo Toth, Daniele Vigo
Crew scheduling is a very well known problem which has been historically associated with airlines and mass transit companies; recently also railway applications have come on the scene. This now...
Matteo Fischetti, Juan Jose Salazar
We study the problem of protecting sensitive data in a statistical two-dimensional table, when the non-sensitive table entries are made public along with the row and column totals. In particular, we...
A heuristic method for the set covering problem (1999)
Alberto Caprara, Matteo Fischetti, Paolo Toth
We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows and...
The Fixed-Outdegree 1-Arborescence Polytope. (1998)
Balas, Egon, Fischetti, Matteo
A 1-arborescence is an arborescence rooted at node 1, plus one arc incident into node 1. The 1-arborescences polytope, the convex hull of incidence vectors of 1-arborescence, is a well known...
Lifted Cycle Inequalities for the Asymmetric Traveling Salesman Problem (1998)
Balas, Egon, Fischetti, Matteo
We investigate the family of facet defining inequalities for the asymmetric traveling salesman (ATS) polytope obtainable by lifting the cycle inequalities. We establish several properties of this...
Modeling and Solving the Cell Suppression Problem for Linearly-Constrained Tabular Data (1998)
Matteo Fischetti, Juan Jose Salazar
Abstract. We study the problem of protecting sensitive data in a statistical table whose entries are subject to a system of linear constraints. This very general setting covers, among others,...
Solving the orienteering problem through branch-and-cut (1998)
In the Orienteering Problem (OP) we are given an undirected graph with edge weights and node prizes. The problem calls for a simple cycle whose total edge weight does not exceed a given threshold,...
Partial Cell Suppression: a new methodology for Statistical Disclosure Control (1998)
In this paper we address the problem of protecting condentiality in statistical tables containing sensitive information that cannot be disseminated. This is an issue of primary importance in...
Matteo Fischetti, Juan Jose Salazar
In this paper we describe theoretical models and practical solution techniques for protecting condentiality in statistical tables containing sensitive information that cannot be disseminated. This is...
Universit`a degli Studi di Bologna (1998)
Dipartimento Di Elettronica, Alberto Caprara, Alberto Caprara, Matteo Fischetti, Matteo Fischetti, Paolo Toth, ...
The Crew Rostering Problem (CRP) aims at determining an optimal sequencing of a given set of duties into rosters satisfying operational constraints deriving from union contract and company...
On the Separation of Maximally Violated mod-k Cuts (Extended Abstract) (1998)
Alberto Caprara, Matteo Fischetti, Adam N. Letchford
Abstract Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the...
Solution of Large-Scale Railway Crew Planning Problems: the Italian Experience (1997)
Alberto Caprara, Matteo Fischetti, Pier Luigi Guida, Paolo Toth, Daniele Vigo
Crew scheduling is a very well known problem which has been historically associated with airlines and mass transit companies; recently also railway applications have come on the scene. This now...
Algorithms for the set covering problem (1996)
Alberto Caprara, Matteo Fischetti, Paolo Toth
The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most...
Vehicle routing problems deal with the optimal use of a eet of vehicles to transport (pick up or deliver) goods between a central depot and a set of clients. Several interesting examples arise in...
A Heuristic Method for the Set Covering Problem (1995)
Alberto Caprara, Matteo Fischetti, Paolo Toth
We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows and...
Modeling and Solving the Crew Rostering Problem (1995)
Alberto Caprara, Alberto Caprara, Matteo Fischetti, Matteo Fischetti, Paolo Toth, Paolo Toth, ...
The Crew Rostering Problem (CRP) aims at determining an optimal sequencing of a given set of duties into rosters satisfying operational constraints deriving from union contract and company...
Optimisation of the interconnecting network of a UMTS radio mobile telephone system
Fischetti, Matteo, Romanin Jacur, Giorgio, Jose Salazar Gonzalez, Juan
Frequency assignment in mobile radio systems using branch-and-cut techniques
Fischetti, Matteo, Lepschy, Chiara, Minerva, Giuseppe, Romanin-Jacur, Giorgio, Toto, Ema
The Linear Ordering Problem with cumulative costs
Bertacco, Livio, Brunetta, Lorenzo, Fischetti, Matteo
The optimization problem of finding a permutation of a given set of items that minimizes a certain cost function is naturally modeled by introducing a complete digraph G whose vertices correspond to...