In this paper, we compare the strength of alternate formulations (polyhedra) of the binary knapsack set. We introduce a specific class of knapsack sets for which we prove that the polyhedra based on their minimal cover inequalities (together with the bounds on the variables) are strictly contained inside the polyhedra defined by their continuous knapsack … Read more
This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth … Read more
Dantzig-Wolfe reformulation is a widely used technique for obtaining stronger relaxations in the context of branch-and-bound methods for solving integer optimization problems. Arc-Flow reformulations are a lesser known technique related to dynamic programming that has experienced a resurgence as result of the recent popularization of decision diagrams as a tool for solving integer programs. Although … Read more
Algorithms based on polyhedral outer approximations provide a powerful approach to solving mixed-integer nonlinear optimization problems. An initial relaxation of the feasible set is strengthened by iteratively adding linear inequalities and separating infeasible points. However, when the constraints are nonconvex, computing such separating hyperplanes becomes challenging. In this article, the moment-/sums-of-squares hierarchy is used in … Read more
We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by the existing LP and SDP relaxations for this class of optimization … Read more
Screening is widely utilized for Mixed-Integer Programming (MIP) presolving. It aims to certify a priori whether one or multiple specific binary variables can be fixed to optimal values based on solutions from convex relaxations. This paper studies the challenge of solving Sparsity-constrained (strongly) Convex Quadratic Programming (SCQP) and proposes the Screening-based Cut Presolving Framework (SCPF). … Read more
We study a two-stage admission and assignment problem under uncertainty arising in university admission systems. In the first stage, applicants are admitted to an initial two-year program. In the second stage, admitted applicants are assigned to degree programs through an articulation mechanism subject to capacity constraints. Uncertainty stems from the academic performance of admitted applicants … Read more
We present an exact formulation of the symmetric Traveling Salesman Problem (TSP) that replaces the classical edge-selection view with a surface-building approach. Instead of selecting edges to form a cycle, the model selects a set of connected triangles where the boundary of the resulting surface forms the tour. This method yields a mixed-integer linear programming … Read more
We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly … Read more
In modern Formula~1, strict regulations and highly optimized cars limit performance gains through hardware, increasing the importance of strategic decision-making. This work tackles the problem of computing a race strategy that minimizes total race time by jointly optimizing tire stints, compound selection, fuel load, and Energy Recovery System (ERS) deployment. We present a high-performance simulation … Read more