CompOpt - Seminars

Abstract: Cycle bases provide compact representations of the cycle space of a graph and have various applications in combinatorial optimization, including electrical network optimization and integer programming formulations such as the Periodic Event Scheduling Problem (PESP). In this seminar, we introduce the theory of cycle bases by reviewing the fundamental definitions and structural properties of the cycle space.
We also present new existence and complexity results for weakly and strongly fundamental cycle bases in the setting where the orientation of the arcs in the cycles must coincide with the orientation of the directed graph (forward cycle bases).
Finally, we discuss the Integer Cycle Basis problem, whose minimization complexity remains one of the main open questions in the field. In planar graphs, a surprising structural phenomenon is known: the minimum integer cycle basis problem can be solved by standard minimum cycle basis polynomial algorithms. Generalizing this observation, we study the family of graphs for which minimum cycle basis algorithms always return an integer cycle basis, showing that this family is characterized by a finite set of forbidden minors. An explicit identification of this family could provide important examples for use in a reduction for the minimum integer cycle basis problem.
Abstract: We propose a novel exact algorithm for the transportation problem, one of the paradigmatic network optimization problems. The algorithm, denoted Iterated Inside Out, requires in input a basic feasible solution and is composed by two main phases that are iteratively repeated until an optimal basic feasible solution is computed. In the first “inside” phase, the algorithm progressively improves upon a given basic solution by increasing the value of several non-basic variables with negative reduced cost. This phase typically outputs a non-basic feasible solution interior to the constraint set polytope. The second “out” phase moves in the opposite direction by iteratively setting to zero several variables until a new improved basic feasible solution is reached. Extensive computational tests show that the proposed approach strongly outperforms all versions of network and linear programming algorithms available in commercial solvers such as Cplex and Gurobi and other exact algorithms available in the literature.
The interest in the transportation problem has been renewed recently because of machine learning and artificial intelligence applications requiring the computation of the distance between pairs of images with source and destination quantities being pixel intensities. A set of image processing instances, called DOTmark, is nowadays the benchmark for this problem. We show that also for these instances a tailored version of IIO exploiting a Matryoshka approach and relying on an improved search of negative reduced cost variables strongly dominates the relevant literature and solves to optimality for the first time instances with up 2^36 variables.
joint work with R. Bargetto and R. Scatamacchia
Abstract: In this talk, we will discuss some recent results we have obtained on hard instances of the Travelling Salesperson Problem (TSP), from different perspectives. A common theme through the talk is that, while the problems may initially appear simple or intuitive, their technical details often turn out to be very intricate. We will also present several open questions, some of which may be suitable as Master's thesis topics. We begin by introducing the classic Dantzig–Fulkerson–Johnson (DFJ) formulation of the TSP, which is conjectured to have an integrality gap of 4/3. Since its introduction in 1954, however, this conjecture has remained unproven. We will explain how we have (partially) proved the bound, without relying on a lemma that, although it seems obvious, proved too difficult for us to establish. This naturally leads to several compelling open problems. Next, we focus on subtour elimination constraints (SECs), the novel and central feature of the DFJ formulation. We present an algorithm that computes the minimum number of SECs required to solve a given instance, and then explore worst-case scenarios. Are there instances that require 2ⁿ SECs? This question turns out to be far more complex than one might expect. We show examples of instances that can be solved with only O(n) SECs, and others that appear to require O(n²), though no formal proof currently exists. We then broaden our view and ask a more general question: given a heuristic for the TSP, is it possible to automatically construct a counterexample where the heuristic fails—or at least to prove that one must exist for a given input size? While some specific cases are easy to settle, generalizing these results remains a difficult and open problem. The lecture will be as interactive as possible, encouraging questions and discussion throughout. Given time constraints, students will be invited to choose the order of the topics at the beginning of the session.
Abstract: In this fast-paced world, intelligent systems need to make reliable, real-time decisions in response to changing conditions and unexpected disruptions. Mathematical optimization is instrumental in this process, but it must offer reliable computations and robust solutions, especially in the presence of uncertainty. In this talk, we will explore how we can harness data to develop optimization tools that can handle uncertainty and operate in real-time. We will investigate learning techniques such as clustering and differentiable optimization to design tractable, robust problem formulations. We will also discuss how to use machine learning to design efficient optimization algorithms for continuous and mixed-integer optimization, with a focus on guaranteeing convergence in real-time operations. By customizing problem formulations and solution algorithms to specific tasks, we will show how we can significantly enhance the computational performance and relia