Refine
Document Type
- Article (4) (remove)
Language
- English (4)
Has Fulltext
- no (4)
Is part of the Bibliography
- no (4)
We investigate the Robust Multiperiod Network Design Problem, a generalization
of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical
CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against
traffic volume uncertainty, we propose a Robust Optimization model based
on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem
may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.
This study investigates how to model and solve the problem of optimally designing FTTx telecommunications access networks integrating wired and wireless technologies, while taking into account the uncertainty of wireless signal propagation. We propose an original robust optimization model for the related robust 3-architecture Connected Facility Location problem, which includes additional variables and constraints to model wireless signal coverage represented through signal-to-interference ratios. Since the resulting robust problem can prove very challenging even for a modern state-of-the art optimization solver, we propose to solve it by an original primal heuristic that combines a probabilistic variable fixing procedure, guided by peculiar Linear Programming relaxations, with a Mixed Integer Programming heuristic, based on an exact very large neighborhood search. A numerical study carried out on a set of realistic instances show that our heuristic can find solutions of much higher quality than a state-of-the-art solver.
We find previously unknown families of sets which ensure Frankl's conjecture holds for all families that contain them using an algorithmic framework. The conjecture states that for any nonempty finite union-closed (UC) family there exists an element of the ground set in at least half the sets of the considered UC family. Poonen's Theorem characterizes the existence of weights which determine whether a given UC family implies the conjecture for all UC families which contain it. We design a cutting-plane method that computes the explicit weights which satisfy the existence conditions of Poonen's Theorem. This method enables us to answer several open questions regarding structural properties of UC families, including the construction of a counterexample to a conjecture of Morris from 2006.
We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs.The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chvátal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result we are able to provide a first machine-assisted proof that
Chvátal's conjecture holds for all downsets whose union of sets contains seven elements or less.