Beyond Shadow Weights: Quantization-Aware Training as Quantized-Endpoint Descent

Categories Data Science Algorithms, Optimization in Data Science Tags , , , , ,

Quantization-aware training (QAT) updates a full-precision shadow weight \(\mathbf{x}\) but deploys the quantized endpoint \(Q(\mathbf{x})\). Existing explanations for QAT largely view its success through the lens of shadow weights: QAT can move \(\mathbf{x}\) toward flatter basins, gain robustness from quantization-induced oscillations, or balance the shadow loss \(f(\mathbf{x})\) against the quantization error \(\|\mathbf{x}-Q(\mathbf{x})\|_2\). These perspectives do … Read more

Data-Driven Police Staffing

Categories Applications - OR and Management Sciences, Scheduling, Stochastic Programming Tags , , ,

Large police departments usually operate by assigning regular patrol units to pre-defined regions, with backup units covering multiple regions to handle periods of high demand or replace unavailable regular units. We develop a data-driven approach to determine the optimal number and deployment of these backup units across different shifts, minimizing the expected travel time to … Read more

On Spanning-Tree Integrality and a new Branching Rule for the Maximum Cut Problem

Categories Combinatorial Optimization, Integer Programming, Semi-definite Programming Tags , , , , , ,

State-of-the-art exact methods for the Maximum Cut problem are based on solving linear and semidefinite programming relaxations embedded into a branch-and-bound algorithm. For linear programming formulations, it was shown recently that it is thereby sufficient to enforce the integrality of the variables associated with the edges of a spanning tree. Our first contribution is to … Read more

Solution of Binary-Constrained Quadratic-Defined Optimization Problems by a Progressive Integer Programming Method

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , ,

Extending a classic result of Giannessi and Tomasin [\textit{Lecture Notes in Comput. Sci. 3}, Springer, 1973, pp. 437–449], this paper shows that a binary-constrained quadratic-defined optimization problem can be formulated as a binary-constrained linear program with linear complementarity constraints (Bi-LPCC). The term “quadratic-defined problems” encompasses many problems that are defined by quadratic functions in the … Read more

Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization

Categories Branch and Cut Algorithms, Combinatorial Optimization, Integer Programming

We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial xTQx+ cTx+ γ over the integer points of a bounded rational polyhedron Ax ≤b. For n variables and m inequalities, the running time is 2O(n log(n+1))(m+ 1)O(n)φ_{A,Q}^O(n)(1 + φ)O(1), where φ_{A,Q} is one plus the maximum binary encoding length of an entry of … Read more

Bounded Cubic Integer Programming in Fixed Dimension

Categories Integer Programming

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

Two-stage approach for the predispatch problem with uncertain demand using splitting variables in interior-point methods

Categories Applications - Science and Engineering, Quadratic Programming, Stochastic Programming Tags , , ,

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

The best approximation tuple: an extension of the Cheney-Goldstein algorithm and results to the multiple sets case

Categories Convex Optimization, Global Optimization, Nonlinear Optimization Tags , , , , , ,

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

Decomposition of Sparse Integer Programs via Nonlinear Edge Encodings and Column-and-Row Generation

Categories 0-1 Programming, Integer Programming Tags , , , ,

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

An Efficient Adaptive Large Neighborhood Search Algorithm for the Flying Sidekick Traveling Salesman Problem

Categories Combinatorial Optimization, Meta Heuristics Tags , ,

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