Invited speakers

Matteo Fischetti

DEI, University of Padova
Via Gradenigo 6/A
I-35100 Padova, Italy

Hybridisation of metaheuristic and exact optimisation techniques for Mixed Integer Programs

Mixed-integer linear programming plays a central role in modelling difficult-to-solve (NP-hard) combinatorial problems. Exact MIP solvers are very sophisticated tools designed to deliver, within acceptable computing time, a provable optimal solution of the input MIP model, or at least a heuristic solution with a practically-acceptable error. Unfortunately, in some hard cases a general-purpose MIP solver may not prove adequate even after clever tuning. This may lead to quitting the MIP framework to design ad-hoc heuristics for the specific problem at hand, thus loosing the advantage of working in a generic framework.

In this talk we will first address the benefits derived from use of an exact MIP solver within a metaheuristic scheme for general MIPs. We will review the recently-proposed Local Branching paradigm that uses (as a black-box ) a general-purpose MIP solver to explore large solution neighbourhoods defined through the introduction in the MIP model of invalid linear inequalities called local branching cuts. We will also consider very hard MIPs where finding any feasible solution is extremely hard in practice, and we will describe a variant of the Local Branching scheme, called Feasibility Pump, where the black-box MIP solver is replaced by an LP solver.

In addition a “dual” scenario will be considered whereby the role of the heuristic and of the exact modules is reversed—with the heuristic being enslaved to the exact MIP solver. More specifically, we will study the benefits of a MIP heuristic to derive dual information (cutting planes) enhancing the convergence of an exact solver for general MIPs.

About the speaker

Born in 1958, Matteo Fischetti received his degree in Electrical Engineering (cum laude) at the University of Bologna and in 1987, was awarded his PhD degree in System Engineering also from the University of Bologna. He has been full professor of Operations Research at the Department of Information Engineering of the University of Padova since 1997.

His research interests include Integer Programming, Polyhedral Combinatorics, Graph Theory, Combinatorial Optimisation, and Vehicle Routing and Crew Scheduling Problems, publishing more than 60 scientific papers in the top-level journals. He is also co-founder of Double-Click sas, an Italian software house that develops and commercialises TURNI, a state-of-the art crew scheduling package currently used by several public and private mass transit companies.

Matteo Fischetti won first prize "Best PhD Dissertation on Transportation" (awarded by the Operations Research Society of America, 1987); the first prize "FASTER" awarded by the Italian railways for the best computer code for solving very large set-covering problems arising in railway scheduling (jointly with P. Toth and A. Caprara, 1994), and the first prize "FARO", awarded by the Italian railways for the best computer code for solving a crew scheduling problem arising in railway applications (jointly with P. Toth, D. Vigo and A. Caprara,1995).

Alberto Piazza

Università degli Studi di Torino

Coevolution of Genes and Languages

About the speaker

Personal page