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
We develop a mixed-integer nonlinear programming (MINLP) approach for the classical Heilbronn triangle problem, demonstrating the capability of modern global optimization solvers to tackle challenging combinatorial geometry problems. A symmetry-breaking strategy based on boundary structure yields a substantially stronger model: for n=9, we compute an epsilon-globally optimal point in 15 minutes on a standard desktop … 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
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
This work addresses the Close-Enough Traveling Salesman Problem (CETSP), a variant of the classic traveling salesman problem in which we seek to visit neighborhoods of points in the plane (defined as disks) rather than specific points. We present two exact formulations for this problem based on second-order cone programming (SOCP), along with approximated mixed-integer linear … Read more
In many retail industries, the retailer can choose the inventory location or fulfillment center (FC) that fulfills an order, yielding opportunities for inventory pooling and product selection expansion. However, fulfillment decisions are complex and must consider cost and speed, among various factors. With the unprecedented growth of the retail industry, companies must look for strategies … Read more
We study the Heilbronn triangle problem, which involves placing \(n\) points in the unit square such that the minimum area of any triangle formed by these points is maximized. A straightforward maximin formulation of this problem is highly non-linear and non-convex due to the existence of bilinear terms and absolute value equations. We propose two … Read more
ArticleDownload View PDF