We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n×n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a “relaxed rank” obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. … Read more
Electric power infrastructure faces increasing risk of damage and disruption due to wildfire. Operators of power grids in wildfire-prone regions must consider the potential impacts of unpredictable fires. However, traditional wildfire models do not effectively describe worst-case, or even high-impact, fire behavior. To address this issue, we propose a mixed-integer conic program to characterize an … Read more
Motivated by the need for reliable traffic management under fluctuating travel demand, we study the problem of determining the worst-case congestion in a multi-commodity traffic network subject to demand uncertainty. To this end, we stress-test a given network by identifying demand realizations and corresponding travelers’ route choices that maximize congestion. The users of the traffic … Read more
For mixed-integer linear programming and linear programming it is well known that symmetries can have a negative impact on the performance of branch-and-bound and linear optimization algorithms. A common strategy to handle symmetries in linear programs is to reduce the dimension of the linear program by aggregating symmetric variables and solving a linear program of … Read more
Inverse optimization problems are bilevel optimization problems in which the leader modifies the follower’s objective such that a prescribed feasible solution becomes an optimal solution of the follower. They capture hierarchical decision-making problems like parameter estimation tasks or situations where a planner wants to steer an agent’s choice. In this work, we study integral inverse … Read more
We develop an optimize-then-refine framework for the classical Heilbronn triangle problem that integrates global mixed-integer nonlinear programming with exact symbolic computation. A novel symmetry-breaking strategy, together with the exploitation of structural properties of determinants, yields a substantially stronger optimization model: for n=9, the problem can be solved to certified global optimality in 15 minutes on … Read more
This paper introduces Zimpler, a free tool built on the ZIMPL modeling language to streamline the solution of mixed-integer linear programs (MILP). Zimpler extends existing ZIMPL workflows by integrating native data sources—such as Excel spreadsheets—without requiring manual conversion to text-based tables. In addition, it supports solution refinement by adapting solver outputs into alternative formats, including … Read more
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