We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, … Read more
This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: … Read more
\(\) Symmetry handling inequalities (SHIs) are an appealing and popular tool for handling symmetries in integer programming. Despite their practical application, little is known about their interaction with optimization problems. This article focuses on Schreier-Sims (SST) cuts, a recently introduced family of SHIs, and investigate their impact on the computational and polyhedral complexity of optimization … Read more
LTL freight carriers operate consolidation networks that utilize cross-docking terminals to facilitate thetransfer of freight between trailers and enhance trailer utilization. This research addresses the problem ofdetermining an optimal schedule for unloading inbound trailers at specific unloading doors using teams ofdock workers. The optimization objective is chosen to ensure that outbound trailers are loaded with … Read more
We present a proof system for establishing the correctness of results produced by optimization algorithms, with a focus on mixed-integer programming (MIP). Our system generalizes the seminal work of Bogaerts, Gocht, McCreesh, and Nordström (2022) for binary programs to handle any additional difficulties arising from unbounded and continuous variables, and covers a broad range of … Read more
In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce “skewed $k$-trees” which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also … Read more
The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similarly to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all these set-partitioning-based approaches have strong assumptions … Read more
We propose an extension of matrix games where the row player may select rows and remove columns, subject to a budget constraint. We present an exact mixed-integer linear programming (MILP) formulation for the problem, provide analytical results concerning its solution, and discuss applications in the security domain. Our computational experiments show heuristic approaches on average … Read more
Given a set of jobs (or items), each of which being characterized by its resource demand and its lifespan, and a sufficiently large number of identical servers (or bins), the busy time minimization problem (BTMP) requires to find a feasible schedule (i.e., a jobs-to-servers assignment) having minimum overall power-on time. Although being linked to the … Read more
We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time … Read more