A geometric characterization of unbounded integer cubic optimization problems via thin rays

Categories (Mixed) Integer Nonlinear Programming

We study geometric characterizations of unbounded integer polynomial optimization problems. Unboundedness along a ray characterizes unbounded integer linear and quadratic optimization problems with rational coefficients. We show that this is no longer true in degree three, already in dimension three, in contrast with the continuous setting, where rays certify unboundedness up to degree three. To … Read more

Projection-width as a structural parameter for discrete separable optimization

Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, 0-1 Programming

While several classes of integer linear optimization problems are known to be solvable in polynomial time, far fewer tractability results exist for integer nonlinear optimization. In this work, we narrow this gap by identifying a broad class of discrete nonlinear optimization problems that admit polynomial-time algorithms. Central to our approach is the notion of projection-width, … Read more

Branch-and-Cut for Computing Approximate Equilibria of Mixed-Integer Generalized Nash Games

Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Game Theory Tags , , , ,

Generalized Nash equilibrium problems with mixed-integer variables constitute an important class of games in which each player solves a mixed-integer optimization problem, where both the objective and the feasible set is parameterized by the rivals’ strategies. However, such games are known for failing to admit exact equilibria and also the assumption of all players being … Read more

Accelerated proximal gradient algorithm for weakly convex function

Categories Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

In this work, we investigate the accelerated proximal gradient algorithm (APGα) for weakly convex composite optimization problems. Building upon the framework of B¨ohm and Wright, and additionally assuming that f is convex and coercive while g is bounded below, we establish an objective residual convergence rate of O(1⁄j²) for α≥3. Moreover, when α›3, this rate … Read more

Distributionally Robust Optimization with Integer Recourse: Convex Reformulations and Critical Recourse Decisions

Categories Integer Programming, Robust Optimization, Stochastic Programming Tags , , , ,

The paper studies distributionally robust optimization models with integer recourse. We develop a unified framework that provides finite tight convex relaxations under conic moment-based ambiguity sets and Wasserstein ambiguity sets.  They provide tractable primal representations without relying on sampling or semi-infinite optimization. Beyond tractability, the relaxations offer interpretability that captures the criticality of recourse decisions. … Read more

Improving Directions in Mixed Integer Bilevel Linear Optimization

Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , ,

We consider the central role of improving directions in solution methods for mixed integer bilevel linear optimization problems (MIBLPs). Current state-of-the-art methods for solving MIBLPs employ the branch-and-cut framework originally developed for solving mixed integer linear optimization problems. This approach relies on oracles for two kinds of subproblems: those for checking whether a candidate pair … Read more

On the Convexification of a Class of Mixed-Integer Conic Sets

Categories (Mixed) Integer Nonlinear Programming, Cone Programming

We investigate mixed-integer second-order conic (SOC) sets with a nonlinear right-hand side in the SOC constraint, a structure frequently arising in mixed-integer quadratically constrained programming (MIQCP). Under mild assumptions, we show that the convex hull can be exactly described by replacing the right-hand side with its concave envelope. This characterization enables strong relaxations for MIQCPs … Read more

Closing the Gap: Efficient Algorithms for Discrete Wasserstein Barycenters

Categories Integer Programming, Optimization in Data Science Tags , , , ,

The Wasserstein barycenter problem seeks a probability measure that minimizes the weighted average of the Wasserstein distances to a given collection of probability measures. We study the discrete setting, where each measure has finite support — a regime that frequently arises in machine learning and operations research. The discrete Wasserstein barycenter problem is known to … Read more

An Exact Penalty Method for Stochastic Equality-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization

In this paper, we study a penalty method for stochastic equality-constrained optimization, where both the objective and constraints are expressed in general expectation form. We introduce a novel adaptive strategy for updating the penalty parameter, guided by iteration progress to balance reductions in the penalty function with improvements in constraint violation, while each penalty subproblem … Read more

GPU-Accelerated First-Order Method with Randomized Sampling for Binary Integer Programs

Categories 0-1 Programming, Constrained Nonlinear Optimization, Parallel Algorithms Tags , ,

We present a scalable, GPU-accelerated algorithmic framework for large binary integer programs that operates end-to-end with minimal synchronization overhead. The proposed method combines a first-order routine that guides search in the continuous relaxation with a randomized, feasibility-aware sampling module that generates batched binary candidates. We establish a residual convergence guarantee for the first-order component in … Read more