Conférenciers invités
A new algorithm for increasing the weight of minimum spanning trees and hypertrees
The 4/3 Conjecture: Is it true or false?Abstract The well-known 4/3 Conjecture states that the integrality ratio of the subtour linear programming relaxation for the metric Travelling Salesman Problem is at most 4/3. This conjecture has been around for almost 40 years and has been the focus of much research, yet it remains unresolved. In this talk we survey results that support the conjecture, as well as discuss properties that a possible counter example might possess.
Perspective Formulations for piecewise convex functions: a theoretical and computational comparisonAbstract In this talk, we focus on mixed integer nonlinear problems with piecewise convex inequalities. This class of mixed integer nonlinear programs (MINLP) arise as subproblems solved at each iteration by the Sequential Convex MINLP method. We generalize the classic formulation for piecewise linear functions to the case of piecewise convex ones and strengthen them through perspective reformulation. Moreover, we compare the different formulations and we show that they are not equivalent, contrarily to what has been shown in the literature for the piecewise linear formulations.
Identification problems in graphs and other discrete structuresAbstract We will address selected topics in the area of identification problems on graphs and other discrete structures. In this type of problems, we wish to select a small set of elements (usually vertices, but sometimes edges, paths, etc) with the goal of distinguishing a set of structures (usually, the vertices or the edges of the graph) by means of membership, neighbourhood or distances to the elements in the solution set. We will highlight a number of recent interesting results, problems and conjectures in the area.
Mathematical Formulations for Consistent Travelling Salesman ProblemsAbstract: The consistent travelling salesman problem looks for a minimum-cost set of Hamiltonian routes, one for every day of a given time period. When a customer requires service over several days, the service times on different days must differ by no more than a given threshold (for example, one hour). We analyze two variants of the problem, depending on whether the vehicle is allowed to wait or not at a customer location before its service starts. There are three mathematical models in the literature for the problem without waiting times, and this paper describes a new model appropriate to be solved with a branch-and-cut algorithm. The new model is a multi-commodity flow formulation on which Benders’ Decomposition helps manage a large number of flow variables. There were no mathematical models in the literature for the variant with waiting times, and this paper adapts the four mathematical models to it. We analyze the computational results of the formulations on instances from the literature with up to 100 customers
and three days.
Geometric Packing, Hitting and Representation: the simplest Open Challenges on Geometric Intersection Graphs Abstract Packing and Covering problems are the alpha and the omega (or better: nu and tau ;=) ) of combinatorial optimization, and have been largely explored in the past decades as the most recent seminal books of the field show. For some combinatorial objects minmax relations provide `good characterizations' and efficient algorithms, while for some others, NP-hardness is accompanied by a constant duality gap or/and approximation algorithms. In this talk I would like to explain some old conjectures and recent developments on packing and hitting the simplest objects in the plane: rectangles, squares and segments, place them in the forest of results and open problems of the field, and present the most frustrating challenges. This is joint work with Marco Caoduro
Orcival |
| Personnes connectées : 2 | Flux RSS | Vie privée |
|
