Abstract Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present,
ABSTRACT Polynomial-Time Algorithm for On-Chip Scratchpad Memory Partitioning (2008)
Federico Angiolini, Luca Benini, Alberto Caprara
Focusing on embedded applications, scratchpad memories (SPMs) look like a best-compromise solution when taking into account performance, energy consumption and die area. The main challenge in SPM...
A Branch-and-Cut Algorithm for Multiple Sequence Alignment (2008)
Ernst Althaus, Alberto Caprara, Hans-peter Lenhof, Knut Reinert
Abstract. We consider a branch-and-cut approach for solving the multiple sequence alignment problem, which is a central problem in computational biology. We propose a general model for this problem...
Recoverable Robustness for Railway Rolling Stock Planning (2008)
Cacchiani, Valentina, Caprara, Alberto, Galli, Laura, Kroon, Leo, Maróti, Gábor
In this paper we explore the possibility of applying the notions of Recoverable Robustness and Price of Recoverability (introduced by [5]) to railway rolling stock planning, being interested in...
SIAM J. DISCRETE MATH. c (2007)
Abstract. We analyze the strong relationship among three combinatorial problems, namely, the problem of sorting a permutation by the minimum number of reversals (MIN-SBR), the problem of finding the...
We deal with the practical solution of the problem of Sorting a permutation By Reversals (SBR), which has relevant applications in computational biology. We present a successful approach based on the...
Algorithms Based on LP Relaxations for Combinatorial Optimization Problems (2007)
We survey the main results presented in the author's Ph.D Thesis [12], which addresses the use of Linear Programming (LP) relaxations within exact and heuristic algorithms for the solution of...
Properties of Some ILP Formulations of a Class of Partitioning Problems (2007)
We discuss possible integer linear programming formulations of a class of partitioning problems, which includes vertex (and edge) coloring and bin packing, and present some basic properties of the...
Alberto Caprara, David Pisinger, Paolo Toth
The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are...
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
Properties of Some ILP Formulations of a Class of Partitioning Problems (2007)
We discuss possible integer linear programming formulations of a class of partitioning problems, which includes vertex (and edge) coloring and bin packing, and present some basic properties of the...
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...
Approximation schemes for ordered vector packing problems (2007)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy
In this paper we deal with the d-dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d...
On the separation of split cuts and related inequalities (2007)
Alberto Caprara, Adam N. Letchford
The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split...
Alberto Caprara, Alessandro Panconesi, Romeo Rizzi
Given an undirected graph G with n nodes and m edges, we address the problem of nding a largest collection of edge-disjoint cycles in G. The problem, dubbed Cycle Packing, is very closely related to...
Wavelength rerouting in optical networks, or the Venetian routing problem (2007)
Alberto Caprara, G. Mohan, Alessandro Panconesi, Aravind Srinivasan
Wavelength rerouting has been suggested as a viable and cost-eective method to improve the blocking performance of wavelength-routed Wavelength-Division Multiplexing (WDM) networks. This method leads...
On the separation of split cuts and related inequalities (2007)
Alberto Caprara, Adam N. Letchford
The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split...
Alberto Caprara, Alessandro Panconesi, Romeo Rizzi
Given an undirected graph G with n nodes and m edges, we address the problem of nding a largest collection of edge-disjoint cuts in G. In particular, we study the complexity of the problem, dubbed...
Claudio Arbib, Alberto Caprara
Let G be the graph obtained as the edge intersection of two graphs G 1; G 2 on the same vertex set V. We show that if at least one of G 1; G 2 is perfect, then (G) (G 1) (G 2), where () is the...
Algorithms Based on LP Relaxations for Combinatorial Optimization Problems (2007)
We survey the main results presented in the author's Ph.D Thesis [12], which addresses the use of Linear Programming (LP) relaxations within exact and heuristic algorithms for the solution of...
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...
Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, 3 2 is the best known approximation ratio achievable in...
A Cutting Plane Algorithm for the Linear Arrangement Problem (2007)
Alberto Caprara, Adam N. Letchford
Given a graph G = (V, E) on n vertices, the Minimum Linear Arrangement Problem (MinLA) calls for a one-to-one function ψ: V → {1,..., n} which minimizes � {i,j}∈E |ψ(i) − ψ(j)|. MinLA is...
04. Solution of the Train Platforming Problem (2007)
Caprara, Alberto, Galli, Laura, Toth, Paolo
In this paper we study a general formulation of the train platforming problem, which contains as special cases all the versions previously considered in the literature as well as a case study from...
06. Solving a Real-World Train Unit Assignment Problem (2007)
Cacchiani, Valentina, Caprara, Alberto, Toth, Paolo
We face a real-world train unit assignment problem for an operator running trains in a regional area. Given a set of timetabled train trips, each with a required number of passenger seats, and a set...
Laying out sparse graphs with provably minimum bandwidth (2005)
informs ® doi 10.1287/ijoc.1040.0083 © 2005 INFORMS Finding a linear layout of a graph having minimum bandwidth is a combinatorial optimization problem that has been studied since the 1960s. Unlike...
Computing Good Allocations for Combinatorial Optimization Games (2004)
Alberto Caprara, Michel X. Goemans, Adam N. Letchford
Much of the literature on cooperative games associated with combinatorial optimization problems is concerned with only one question: whether or not the core is empty. In this paper however we are...
A 3/4-approximation algorithm for multiple subset sum (2003)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy
The Multiple Subset Sum Problem (MSSP) is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The...
The reversal median problem (2003)
In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology and is a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for...
Packing Triangles in Bounded Degree Graphs (2002)
Caprara, Alberto, Rizzi, Romeo
We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (resp. second) problem is polynomially...
Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals (2002)
Caprara, Alberto, Rizzi, Romeo
Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, 3/2 is the best known approximation ratio achievable in...
Althaus,Ernst, Caprara,Alberto, Lenhof,Hans-Peter, Reinert,Knut
Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In...
Althaus, Ernst, Caprara, Alberto, Lenhof, Hans-Peter, Reinert, Knut, Lengauer, Thomas
Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In...
Alberto Caprara, Federico Malucelli, Daniele Pretolani
We give a partial characterization of graphs of bandwidth two, whose structure has been exploited to a very limited extent so far. Our results are used to derive a new linear-time recognition...
Structural Alignment of Large-Size Proteins via Lagrangian Relaxation (Extended Abstract) (2002)
Alberto Caprara, Giuseppe Lancia
Alberto Caprara DEIS, University of Bologna Viale Risorgimento 2 40136 Bologna, Italy acaprara@deis.unibo.it Giuseppe Lancia DEI, University of Padova Via Gradenigo 6-A 35131 Padova, Italy...
Althaus, Ernst, Caprara, Alberto, Lenhof, Hans-Peter, Reinert, Knut
Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In...
A global method for crew planning in railway applications (2001)
Alberto Caprara, Michele Monaci, Paolo Toth
Abstract. Crew planning is a typical problem arising in the management of large transit systems (such as railway and airline companies). Given a set of train services to be performed every day, the...
Lower Bounds and Algorithms for the 2-Dimensional Vector Packing Problem (2001)
Given n items, each having, say, a weight and a length, and n identical bins with a weight and a length capacity, the 2-Dimensional Vector Packing Problem (2-DVPP) calls for packing all the items...
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...
Sorting Permutations by Reversals through Branchand -Price (2001)
We describe an exact algorithm for the problem of sorting a permutation by the minimum number of reversals, originating from evolutionary studies in molecular biology. Our approach is based on an...
Lower Bounds and Algorithms for the 2-Dimensional Vector Packing Problem (2001)
Given n items, each having, say, a weight and a length, and n identical bins with a weight and a length capacity, the 2-Dimensional Vector Packing Problem (2-DVPP) calls for packing all the items...
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...
Approximation algorithms for knapsack problems with cardinality constraints (2000)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy, David Pisinger
We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock...
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...
The Multiple Subset Sum Problem (2000)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy
The Multiple Subset Sum Problem (MSSP) is the selection of items from a given ground set and their packing into a given number of identical bins such that the sum of the item weights in every bin...
Approximation algorithms for knapsack problems with cardinality constraints (2000)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy, David Pisinger
y--We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting...
Experimental and statistical analysis of sorting by reversals (2000)
Sorting by reversals is one of the most widely studied models of genome rearrangements in molecular biology. In this paper, we rst brie y review the state{of{the{ art methods to solve the problem....
Exact solution of the quadratic knapsack problem (1999)
Alberto Caprara, David Pisinger, Paolo Toth
The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are...
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...
Separating lifted odd-hole inequalities to solve the index selection problem (1999)
The Index Selection Problem (ISP) is a phase of fundamental importance in the physical design of databases, calling for a set of indexes to be built in a database so as to minimize the overall...
On the tightness of the alternating-cycle lower bound for sorting by reversals (1999)
We give a theoretical answer to a natural question arising from a few years of computational experiments on the problem of sorting a permutation by the minimum number of reversals, which has relevant...
Separating lifted odd-hole inequalities to solve the index selection problem (1999)
The Index Selection Problem (ISP) is a phase of fundamental importance in the physical design of databases, calling for a set of indexes to be built in a database so as to minimize the overall...
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...
Improving a Family of Approximation Algorithms to Edge Color Multigraphs (1998)
Caprara, Alberto, Rizzi, Romeo
Given a multigraph G=(V,E), the Edge Coloring Problem (ECP) calls for the minimum number X of colors needed to color the edges in E so that all edges incident with a common node are assigned...
Improving a family of approximation algorithms to edge color multigraphs (1998)
Given a multigraph G = (V; E), the Edge Coloring Problem (ECP) calls for the minimum number of colors needed to color the edges in E so that all edges incident with a common node are assigned dierent...
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...
Formulations and Hardness of Multiple Sorting by Reversals (1998)
We consider two generalizations of signed Sorting By Reversals (SBR), both aimed at formalizing the problem of reconstructing the evolutionary history of a set of species. In particular, we address...
Approximation Algorithms for Knapsack Problems with Cardinality Constraints (1997)
Alberto Caprara, Hans Kellerer, Ulrich Pferschy, David Pisinger
We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock...
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...
Sorting Permutations by Reversals and Eulerian Cycle Decompositions (1997)
We analyze the strong relationship among three combinatorial problems, namely the problem of sorting a permutation by the minimum number of reversals (MIN-SBR), the problem of finding the maximum...
We introduce a generalization of the well-known Uncapacitated Facility Location Problem, in which clients can be served not only by single facilities but also by sets of facilities. The problem,...
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...
A Branch-and-Cut Algorithm for the Index Selection Problem (1996)
Alberto Caprara, Juan José Salazar
The Index Selection Problem (ISP) is a phase of fundamental importance in the physical design of databases, calling for a set of indexes to be built in a database so as to minimize the overall...
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...
A Column-Generation Based Branch-And-Bound Algorithm For Sorting By Reversals (1995)
Alberto Caprara, Giuseppe Lancia, See-Kiong Ng
We consider the problem of sorting a permutation by reversals (SBR), calling for the minimum number of reversals transforming a given permutation of f1; : : : ; ng into the identity permutation. SBR...
Approximation algorithms for knapsack problems with cardinality constraints
Caprara, Alberto, Kellerer, Hans, Pferschy, Ulrich, Pisinger, David
A Column-Generation Based Branch-And-Bound Algorithm For Sorting By Reversals
Alberto Caprara, Giuseppe Lancia, See-Kiong Ng
this paper we present an exact branch--and--bound algorithm for SBR. Our lower bound is based on the results of Bafna and Pevzner [1] (see also Kececioglu and Sankoff [11]) where the reversal...