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
In this paper 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 the consideration of more than two sets. The other is the ability to handle each set as an intersections of a finite … 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 investigates the Flying Sidekick Traveling Salesman Problem (FSTSP), and proposes an efficient Adaptive Large Neighborhood Search (ALNS) algorithm. Our proposed framework operates directly on a complete solution representation, eliminating the reconstruction step required by indirect encodings and making temporal information immediately accessible during the search process. A stage-based mechanism is introduced to efficiently … 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
This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, which is directly applicable to solving Nash equilibria. The fixed-point bundle for VIs on the product-of-simplex domain reveals a composite fiber bundle structure. The key innovation is to construct an equivalent VI on the simplex … 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