A regular timetable is a collection of events that repeat themselves every specific time span. This even structure, whenever applied at a whole network, leads to several benefits both for users and the company, although some issues are introduced, especially about dimensioning the service. It is therefore fundamental to properly consider the interaction between the … Read more
In this paper, we describe an algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range … Read more
This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable … Read more
We present a novel formulation for startup cost computation in the unit commitment problem (UC). Both the proposed formulation and existing formulations in the literature are placed in a formal, theoretical dominance hierarchy based on their respective linear programming relaxations. The proposed formulation is tested empirically against existing formulations on large-scale unit commitment instances drawn … Read more
Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid … Read more
We formulate an integer program to solve a highly constrained academic timetabling problem at the United States Merchant Marine Academy. The IP instance that results from our real case study has approximately both 170,000 rows and columns and solves to near optimality in 12 hours, using a commercial solver. Our model is applicable to both … Read more
We present a generalization of the average shadow price in 0-1-Mixed Integer Linear Programming problems and its relation with bottlenecks including the analysis relative to the coefficients matrix of resource constraints. A mathematical programming approach to find the strategy for investment in resources is presented. Citation Escuela de Computación, Facultad de Ciencias, Universidad Central de … Read more
We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on $n$ vertices, with a polynomial number of constraints, requires $\Omega(\sqrt{\sfrac{n}{\log n}})$ many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical … Read more
We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more
We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more