We consider the exact minimization of a rational cubic polynomial over the integer points of a rational polytope in fixed dimension. Del Pia, Hildebrand, Weismantel, and Zemmer proved polynomial-time solvability in dimension two, while quartic polynomial minimization is already NP-hard in dimension two. We show that the bounded cubic result extends to every fixed dimension. … Read more
The stochastic predispatch optimal power flow problem aims to minimize generation costs and transmission losses subject to network constraints under demand uncertainty. We formulate it as a two-stage stochastic quadratic optimization problem with fixed recourse, in which hydroelectric generation constitutes the here-and-now decision, while thermal generation and transmission flows are recourse decisions. Using a splitting-variable … Read more
We extend the algorithm and several results published in the celebrated 1959 paper of Cheney and Goldstein about the best approximation pair (BAP) problem in two separate directions. One is, for the first time, the ability to consider more than two sets, a task which has been in the mind of researchers for many years … Read more
A wide range of sparse integer programs admit a block structure in which subproblems interact through a small set of shared variables. Dualizing the linking equalities yields a decomposable Lagrangian relaxation, but generally introduces a duality gap. Recent work shows that this gap can be closed while preserving decomposability by dualizing exponentially large families of … Read more
This paper proposes an efficient Adaptive Large Neighborhood Search (ALNS) algorithm for the Flying Sidekick Traveling Salesman Problem (FSTSP). The algorithm integrates a stage-based truck–drone solution representation, two complementary destroy–repair operator groups, and six local-search neighborhoods focusing on drone operations and truck–drone interactions. Computational efficiency is enhanced through constant-time move evaluation after preprocessing and Static … Read more
Classical robust optimization relies on convex and bounded uncertainty sets, an assumption that is inadequate for sparse uncertainty, where only a small, unknown subset of parameters deviates from its nominal value. This sparsity makes the uncertainty set nonconvex and turns separation into a combinatorial problem, so standard duality-based reformulations do not apply. We study two … Read more
Developing general-purpose algorithms with global asymptotic convergence guarantees for Nash equilibria of general-sum games remains a longstanding challenge. This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from simplex domains to product-of-simplex domains, enabling its direct application to Nash equilibrium computation. The resulting fixed-point bundle exhibits a composite fiber bundle structure. The … Read more
We give a deterministic polynomial-time algorithm for integer quadratic programming in every fixed dimension: it minimizes an arbitrary rational quadratic exactly over the integer points of a rational polyhedron, or certifies infeasibility or integer unboundedness. The core is a sign test that decides whether \(d^{\mathsf{T}}Qd\ge 0\) for every integer point \(d\) of a bounded symmetric … Read more
Facility location decisions are typically made before demand is fully known, yet most applied studies solve a single deterministic model using expected or nominal demand. This paper formulates and solves a capacitated facility location problem using a real academic benchmark instance, then extends it to a two-stage stochastic program in which facility-opening decisions are made … Read more
When linearizing binary quadratic programs, the most usual way is to replace bilinear products with additional variables constrained to take on consistent values in any feasible solution. In this setting, column generation is a principally desirable solution technique, for instance because the number of such additional linearization variables may be large while many of them … Read more