The Vertex Coloring Problem and its generalizations

This is a summary of the author’s PhD thesis supervised by Paolo Toth and defended on 29 May 2007 at the Università di Bologna. The thesis is written in English and is available from the author upon request. The first part of this work deals with the Vertex Coloring Problem and its generalizations, for which models, bounds and algorithms are proposed. The Second Part is dedicated to a different problem on graphs, namely a Routing Problem in telecommunication networks where not only the efficiency, but also the fairness of the solution is considered.      

Optimization models and algorithms for the hyperplane clustering problem

This is a summary of the author’s PhD thesis supervised by Edoardo Amaldi and defended on 3 April 2009 at the Politecnico di Milano. The thesis is written in English and is available from the author upon request. In this work, we extensively study two challenging variants of the general problem of clustering a given set of data points with respect to hyperplanes so as to extract collinearity between them. After pointing out the similarities and differences with previous work on related problems, we propose mathematical programming formulations for our problem variants. Since these problems are difficult to handle due to the nonlinear nonconvexity that arises because of the ℓ ₂-norm in the distance function and a large number of binary assignment variables, we develop column generation algorithms and heuristics to tackle them. The efficiency of the methods developed is demonstrated on realistic randomly generated instances along with applications in piecewise linear model fitting and line segment detection in digital images.     

Some classical combinatorial problems on circulant and claw-free graphs: the isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs

This is a summary of the author’s Ph.D. thesis supervised by Sara Nicoloso and Gianpaolo Oriolo and defended on 3 April 2008 at Sapienza Università di Roma. The thesis is written in English and is available from the author upon request. This work deals with three classical combinatorial problems, namely the isomorphism, the vertex-coloring and the stable set problem, restricted to two graph classes, namely circulant and claw-free graphs. In the first part (joint work with Sara Nicoloso), we derive a necessary and sufficient condition to test isomorphism of circulant graphs, and give simple algorithms to solve the vertex-coloring problem on this class of graphs. In the second part (joint work with Gianpaolo Oriolo and Gautier Stauffer), we propose a new combinatorial algorithm for the maximum weighted stable set problem in claw-free graphs, and devise a robust algorithm for the same problem in the subclass of fuzzy circular interval graphs, which also provides recognition when the stability number is greater than three.     

Enhanced mixed integer programming techniques and routing problems

This is a summary of the author’s PhD thesis supervised by Andrea Lodi and Paolo Toth and defended on 16 April 2009 at the Università di Bologna. The thesis is written in English and is available from the author upon request. This work is focused on Mixed Integer Programming (MIP). In particular, the first part of the thesis deals with general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. The second part is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications.     

Approximation and resolution of min–max and min–max regret versions of combinatorial optimization problems

This is a summary of the most important results presented in the author’s PhD thesis. This thesis, written in French, was defended on November 2005 and supervised by Cristina Bazgan and Daniel Vanderpooten. A copy is available from the author upon request. This thesis deals with the complexity, approximation and resolution of the min–max and min–max versions of classical combinatorial optimization problems. In addition to these theoretical aspects, a practical application of robustness approaches to the problem of data association is considered.     

Scheduling with earliness–tardiness penalties and parallel machines

This is a summary of the author’s PhD thesis supervised by Francis Sourd and Philippe Chrétienne and defended on 30 January 2007 at the Université Pierre et Marie Curie, Paris. The thesis is written in French and is available from the author upon request. This work is about scheduling on parallel machines in order to minimize the total sum of earliness and tardiness costs. To solve some variants of this problem we propose: an exact method based on continuous relaxations of convex reformulations derived from a 0–1 quadratic program; a heuristic algorithm that relies on a new exponential size neighborhood search; finally, a lower bound method based on a polynomial time solution of a preemptive scheduling problem for which the cost functions of the jobs have been changed into so called position costs functions. Partial funding provided by CONACyT (Mexican Council for Science&Technology).     

Multidimensional Lipschitz global optimization based on efficient diagonal partitions

This is a summary of the author’s PhD thesis, supervised by Yaroslav D. Sergeyev and defended on May 5, 2006, at the University of Rome “La Sapienza”. The thesis is written in English and is available from the author upon request. In this work, the global optimization problem of a multidimensional “black-box” function satisfying the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant is considered. The objective function is assumed hard to evaluate. A new efficient diagonal scheme for constructing fast algorithms for solving this problem is examined and illustrated by developing several powerful global optimization methods. A deep theoretical study is performed which highlights the benefit of the approach introduced over traditionally used diagonal algorithms. Theoretical conclusions are confirmed by results of extensive numerical experiments.      

Algorithms for some graph theoretical optimization problems

This is a summary of the main results presented in the author’s PhD thesis. This thesis, written in English, was supervised by Frits Spieksma and defended on September 23, 2005 at the Katholieke Universiteit Leuven. A copy of the thesis is available from the authors website (http://www.econ. kuleuven.be/linda.moonen/public/). The thesis can be roughly split into two parts. The first part is dedicated to the problem of partitioning partially ordered sets into chains of limited size. The second part deals with the structure and the connectivity of the Internet.     

Models and algorithms for the reconfiguration of distributed wireless switching systems

This paper is a summary of the author’s PhD thesis entitled “Models and algorithms for the reconfiguration of wireless switching systems”. The thesis deals with the study of a strongly NP-hard resource-constrained scheduling problem arising from the telecommunication industry. This work was supervised by Jacques Carlier and Dritan Nace, both from Université de Technologie de Compiègne, and carried out while the author was a System Architect within Nortel GSM Access R&D organization. The thesis, which is written in both French and English, has been defended on 29 March 2007 and is available by email request to the author. This research was supported in part by Association Nationale de la Recherche Technique grant CIFRE-121/2004.     

Enhancing CP-based column generation for integer programs

This is a summary of the author’s Ph.D. thesis supervised by Federico Malucelli and defended on 15 May 2008 at the Politecnico di Milano. The thesis is written in English and is available from the author upon request. This work presents new methods for enhancing the Column Generation approach based on Constraint Programming when it is used for solving combinatorial optimization problems. The methods proposed focus on the interactions between the linear programming solver and the constraint programming solver, and on how they impact on both a single iteration and the overall execution of the Column Generation procedure. The result of this work is the design and implementation of general-purpose optimization algorithms, whose efficiency is proven by solving two very different problems: the Minimum Graph Coloring Problem and a resource allocation problem arising in Wireless Ad Hoc Networks.     

Exact and heuristic algorithms for routing problems

This is a summary of the authors PhD thesis supervised by Daniele Vigo and defended on 30 March 2010, at the Università di Bologna. The thesis is written in English and is available from the author upon request. Several rich routing problems attaining to the transportation area have been studied. “Simple” algorithms have been proposed to solve them, both exact and heuristic, producing high quality solutions and transferrable methods.     

Multicast problems in telecommunication networks

This is a summary of the author’s PhD thesis supervised by Paolo Nobili and defended on 20 April 2007 at the Università del Salento (Lecce). The thesis is written in English and is available from the author upon request. This work deals with multicast problems in wireless Ad-Hoc networks and some related variants.      

An Extension of Schreier Unconditionality

The main result of the paper extends the classical result of E. Odell on Schreier unconditionality to arrays in Banach spaces. An application is given on the “multiple of the inclusion plus compact" problem which is further applied to a hereditarily indecomposable Banach space constructed by N. Dew. The present paper is part of the Ph.D thesis of the second author who is partially supported under Prof. Girardi’s NSF grant DMS-0306750.     

Teoremi di unicità della magnetoidrodinamica in domini illimitati

Riassunto In questa nota si stabiliscono due teoremi di unicità della soluzione per il problema del moto di un fluido omogenco, incomprimibile, perfetto, elettricamente conduttore attorno ad un ostacolo fisso, anch'esso elettricamente conduttore. Nelprimo teorema viene trascurata la corrente di spostamento, mentre nel secondo si tiene conto anche di quest'ultima. Per la dimostrazione si utilizza il “metodo della funzione peso” usato da G. P. Galdi e S. Rionero in un analogo teorema di unicità per magnetofluidi viscosi.

---

Summary The Author establishes two solution uniqueness theorems for the problem of homogeneous, incompressible, perfect, electrically conducting fluid motion around a fixed, electrically conducting solid body. In the first theorem displacemt current is disregarded, in the other one this current is considered. The proof is obtained by using the “weight function method” adopted by G. P. Galdi and S. Rionero in an analogous uniqueness theorem for viscous magnetofluids.

     

Structure of the linearized problem for compressible parallel fluid flows

We consider the linearized compressible Navier-Stokes equation near a parallel flow in a cylindrical domain restricting our study to perturbations periodic in the generatrix direction. For any parameter values, we show that the initial value linear evolution problem is solved by the direct sum of a (strictly) contraction semi-group and an analytic semi-group. Any unbounded in time solution of this linear problem comes from isolated eigenvalues with finite multiplicities, which have non negative real part, and whose imaginary part is bounded. In addition, we precise the structure of the spectrum of the generator of the semi-group, locating the essential spectrum stricly on the left side of the complex plane.

---

Sunto Si linearizzano le equazioni di Navier-Stokes comprimibili attorno ad un moto lineare in un cilindro. Senza imporre restrizioni sul moto di base, si studia il problema lineare per perturbazioni periodiche nella direzione della generatrice del cilindro. Si prova che il problema di evoluzione lineare è dato dalla somma diretta di un semigruppo di stretta contrazione ed un semigruppo analitico. Ogni soluzione temporalmente non limitata deriva da autovalori isolati di molteplicità finita, aventi parte reale positiva e parte immaginaria limitata. Si studia anche la struttura dello spettro del generatore del semigruppo, costituito nel lato destro del piano complesso da autovalori di molteplicità finita, e nel lato sinistro di autovalori e da uno spettro essenziale situato su di una retta parallela all’asse immaginario.

     

Cauchy problem for some non-Kovalewskian equations

Some evolution equations with constant leading coefficients and real characteristic roots are considered. The wellposedness of Cauchy problem is proved inH ^∞ and in Gevrey classes, if an assumption is made on the lower order terms. Finally the results are generalized to nonlinear equations.

---

Sunto Si considerano equazioni differenziali di evoluzione con coefficienti costanti nella parte principale e radici caratteristiche reali. Si dimostra la buona positura del problema di Cauchy inH ^∞ e nelle classi di Gevrey, sotto un’ipotesi sui termini di ordine inferiore. Infine, i risultati vengono estesi alle equazioni non lineari.

     

Exact and approximate resolution of integral multiflow and multicut problems: algorithms and complexity

This is a summary of the author’s PhD thesis supervised by Marie- Christine Costa and Frédéric Roupin and defended on 20 November 2006 at the Conservatoire National des Arts et Métiers in Paris (France). The thesis is written in French and is available upon request from the author. This work deals with two well-known optimization problems from graph theory: the maximum integral multiflow and the minimum multicut problems. The main contributions of this thesis concern the polynomial-time solvability and the approximation of these two problems (and of some of their variants) in classical classes of graphs: bounded tree-width graphs, planar graphs and grids, digraphs, etc.      

Models and algorithms for combinatorial optimization problems arising in railway applications

This is a summary of the author’s PhD thesis supervised by Alberto Caprara and Paolo Toth and defended on 29 May 2007 at the Università di Bologna. The thesis is written in English and is available from the author upon request. This work deals with Railway Optimization, and in particular it focuses on the Train Timetabling Problem (in the basic version on a corridor and in the extension to a railway network), and on the Train Unit Assignment Problem. Integer Linear Programming (ILP) formulations are proposed for both problems, and their continuous and Lagrangian relaxations are used to obtain optimal and heuristic solutions to real-world instances.      

Methods to solve multi-skill project scheduling problem

This is a summary of the author’s PhD thesis supervised by P. Martineau and E. Néron and defended on 28 November 2006 at the Université François-Rabelais de Tours. The thesis is written in French, and is available upon request from the author. This work deals with the problem of scheduling a project. The activities of this project requires skills that may not be mastered by all persons involved. First of all, the problem is defined in the introduction part. Then we propose different methods to solve it: lower bounds in part 2, different heuristics and meta-heuristics in part 3, and finally a branch-and-bound procedure in the last part.     

Game Theory applied to gene expression analysis

This is a summary of the author’s Ph.D. thesis supervised by Fioravante Patrone and Stefano Bonassi and defended on 25 May 2006 at the Università degli Studi di Genova. The thesis in written in English and a copy is available from the author upon request. This work deals with the discussion and the application of a methodology based on Game Theory for the analysis of gene expression data. Nowadays, microarray technology is available for taking “pictures” of gene expressions. Within a single experiment of this sophisticated technology, the level of expression of thousands of genes can be estimated in a sample of cells under given conditions. Roughly speaking, the starting point is the observation of a “picture” of gene expressions in a sample of cells under a biological condition of interest, for example a tumor. Then, Game Theory plays a primary role to quantitatively evaluate the relevance of each gene in regulating or provoking the condition of interest, taking into account the observed relationships in all subgroups of genes.