We study the unsplittable multicommodity fixed-charge network design problem, in which every commodity follows a single path and each arc is installed at most once. Its linear relaxation is weak because a commodity may occupy a fraction of an arc. We propose an extended formulation that indexes the variables of each arc by the number … Read more
We prove that deciding whether an integer cubic polynomial takes a value at most one over three nonnegative integers is NP-hard. Hardness holds even when every feasible objective value is a positive integer, so every constructed instance has a finite, attained minimum. This establishes a sharp dimension boundary for the tractability of cubic integer optimization … Read more
State-of-the-art exact methods for solving vehicle routing problems rely on a dynamic program that enumerates the set of feasible routes and their distances. Using relaxations of the dynamic program improves these exact methods. This work is motivated by two observations. First, the dynamic program enumerates some routes with a suboptimal permutation of the locations. Second, … Read more
The Continuous-Time Service Network Design Problem (CTSNDP) arises in consolidation-based transportation systems, where shipments share paths in space and time to reduce cost. The CTSNDP determines minimum-cost transportation plans over a continuous-time horizon. To provide more consolidation opportunities and achieve further cost reductions, CTSNDP with Splittable Deliveries (SCTSNDP) allows each commodity to be divided into … Read more
Binary bilevel programs are challenging to solve due to the lack of compact single-level reformulations. Recent extended network flow-based reformulations have emerged as a promising approach, providing strong dual bounds. However, their increasing size can make them computationally prohibitive. We develop a cutting-plane framework that exploits these networks without requiring an extended-space formulation. We introduce … Read more
We study robust network enhancement problems that improve network performance through component upgrades, where both network utilities and enhancement costs are uncertain. We consider two formulations: a lower-bound problem that improves the minimum utility across feasible network structures and an upper-bound problem that improves the maximum utility. For the lower-bound problem, we develop an exact … Read more
We consider multistage stochastic mixed-integer programs M-SMIPs, and show that these problems are asymptotically convex. That is, we show that the expected cost-to-go functions in the problem converge to convex functions as the variability of the random parameters in the model increases. To derive this result, we first propose a novel adapted Gomory relaxation for … Read more
The integer quadratic moment hull is the closed convex hull of the pairs \((z,zz^{\top})\) with \(z\in\mathbb{Z}^n\). We prove that one round of Chvátal–Gomory (CG) cuts applied to its basic semidefinite relaxation recovers this hull exactly if and only if \(n\le6\). Our approach identifies its facets with perfect Delaunay polyhedra and characterizes their recovery through depth, … Read more
Constraint learning is an emerging paradigm of modeling optimization problems with the help of machine learning. In this paradigm, trained machine learning models are embedded into the optimization model. For example, we can learn constraints empirically from available data, or we can avoid using a nonlinear objective function by learning a simpler approximation for it. … Read more
We study pessimistic bilevel optimization with bilinear objectives and linear constraints. Assuming a compact polyhedral leader domain, nonempty follower solution sets, and a finite pessimistic infimum, we derive mixed-integer linear optimization formulations that attain this infimum, even when the original problem has no optimal solution. This setting has applications such as pricing, security, and decision-focused … Read more