CS Paper Radar

Non-convex integer programming: a deterministic solution method of the large block sale problem

David Nizard, Dominique Quadri

cs.DM math.OC ·submitted 2026-10-10 14:35 UTC · v1

Abstract

We study a non-convex, nonlinear integer mathematical program with a linear constraint. This problem originates in finance and consists of selling a large predetermined quantity of a financial asset over a fixed time horizon, while maximizing the total proceeds. The selling price is modeled using a deterministic penalty function capturing the market's adverse reaction to the selling flow. From a complexity perspective, the problem is in NP. We first solve the problem exactly using dynamic programming and propose several heuristics that yield tight numerical lower bounds. We then reformulate the problem into an equivalent factorable form and derive a tight convex relaxation using McCormick inequalities. This relaxation is embedded within an adapted Branch & Bound algorithm to find the global optimum in finite time. Numerical experiments show that our methods outperform several widely used generic solvers (LocalSolver, Scip, Baron, Couenne, and Bonmin) for selected instances, but do not yield tight upper bounds, beyond small instances.

Closest papers

Nearest neighbours by meaning across the whole index.

Autoregressive Differentiable Method for Integer Programming

cs.LG math.OC ·2026-10-01 ·Ouns El Harzli, Yudong Cao
code/data similarity 0.61
Abstract

We introduce an autoregressive differentiable method to solve 0-1 integer programs. We fix an arbitrary order of the binary variables and we train a transformer to predict the next bit while remaining in the feasible set. Our method is first trained on feasible incumbents provided by any solver, thus allowing us to initialize the transformer in the feasible set. Our procedure then implements a Lagrangian penalty to penalize infeasible solutions, and the transformer is further trained to explore the feasible set using Gumbel-softmax activations on the relaxed objective. We have tested our method on non-convex instances of quadratic knapsack problem and demonstrated consistent improvement upon state-of-the-art open-source solvers for dense problems up to 10,000 binary variables. In particular, we empirically demonstrate a phenomenon akin to a tunneling effect where the effective change of variables from binary variable to the continuous weights of the transformer that the method implements enables crossing barriers in the relaxed objective landscape.

0.37

Feasible Multi-Asset Optimal Execution under Cash Constraints

cs.CE q-fin.TRmath.OCq-fin.CP+1 ·2026-08-18 ·Ryuji Hashimoto, Namid R. Stillman
similarity 0.60
Abstract · 8 pages, 4 figures, 4 tables

Optimal execution (OE) in multi-asset settings involves complex interactions across assets, particularly through shared capital constraints during portfolio rebalancing. While existing models capture cross-impact and portfolio-level dynamics, they largely overlook the role of explicit cash constraints along the execution trajectory. As a result, the feasibility of execution strategies under limited capital remains poorly understood. In this paper, we extend the classical Almgren-Chriss framework to incorporate intertemporal constraints on expected cash consumption, requiring that the expected cumulative cash spent does not exceed a prescribed budget at every trading period. We show that the resulting multi-asset OE problem can be equivalently formulated as a quadratically constrained quadratic program (QCQP), and further establish that it admits a convex representation under mild conditions. This provides a tractable framework for analyzing execution strategies under dynamic capital constraints. Through controlled synthetic experiments, we show that the proposed cash constraints qualitatively alter OE schedules toward cash-feasible sell-first executions as the constraints become tighter. Furthermore, evaluations in an out-of-sample agent-based market simulator demonstrate that our method substantially reduces peak cash drawdown while maintaining implementation shortfall comparable to existing execution strategies. Our results highlight the importance of explicitly modeling financial feasibility in multi-asset execution and provide a foundation for bridging theoretical OE models with practical capital constraints.

0.22

Entropic Column Generation and Lehmer Branch-and-Price for Bin Packing Problem

cs.DM math.OC ·2026-10-31 ·Masoud Ataei
benchmarkcode/data similarity 0.60
Abstract · 38 pages, 1 figure, 8 tables. Code: https://github.com/chimera1001/lehmer-bp

We introduce Lehmer branch-and-price, an exact algorithm for bin packing and cutting stock problems built on the Lehmer transform, the ratio of Mellin transforms of item weights at consecutive orders. The transform maps each bin, a finite multiset of item weights, to a smooth increasing curve, and so gives the discrete problem a continuous representation on which the tools of analysis, such as convexity, exponential families and smoothing, can act. Read along this curve, the problem yields an explicit dual solution, a monotone representation of the dominance order, a family of constructive heuristics with first fit decreasing as its limit, and an integer identity that tells when the linear relaxation can decide an instance and when only a perfect packing can improve the best solution known. Lifted from items to patterns, the transform gives entropic column generation, a new form of column generation that bounds the relaxation from both sides at every iteration without solving the pricing problem exactly, maximizes a smoothed dual at an explicit rate, and measures by an entropy how much the relaxation leaves undecided. We show that the proposed algorithm outperforms the state-of-the-art methods on the standard benchmark in both the number of instances solved and the computational time.

0.40

Constrained Graph Diffusion for Mixed Integer Optimization

cs.LG ·2026-08-13 ·Vincenzo Di Vito, Yusuf Guven, Babak Badnava, Deepjyoti Deka, Kaarthik Sundar +1 more
similarity 0.60
Abstract

This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems. These problems are computationally challenging, as they require jointly determining discrete and continuous decisions while satisfying complex combinatorial constraints. problem-agnostic and can accommodate a broad class of mixed-integer optimization problems through suitable projection operators. We introduce Constrained Graph Diffusion (CGD), a learning-based framework that approximately solves recurring instances of such problems by learning a conditional distribution over their discrete decisions. CGD uses a graph-based diffusion model and incorporates constraint information directly into the reverse diffusion process, steering intermediate predictions toward the feasible region throughout generation. By operating on continuous relaxations of the discrete variables, CGD defines a differentiable constrained generation pathway up to terminal discrete recovery. Once the discrete decision is recovered and fixed, a numerical optimizer solves the remaining continuous problem, avoiding online combinatorial search over the binary variables while retaining numerical optimization for continuous completion. We evaluate CGD on AC-OPF with branch switching and discrete portfolio optimization, demonstrating substantial improvements in feasibility and solution quality over learning-based baselines while achieving speedups of up to $543\times$ over state-of-the-art MIP solvers on large instances.

0.04

On the Power of Determinism in Multi-Item Auctions

cs.GT cs.DM ·2026-09-28 ·Yiannis Giannakopoulos, Johannes Hahn
theory similarity 0.60
Abstract · Improved the upper bound on REV/max{SREV,BREV} from 3 to 2.5 for independent items, and added a lower bound of 2.19. For iid items, improved…

We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. We compare the revenue (REV) of the optimal truthful auction, which in general may be randomized or complicated, with the revenues of three simple deterministic auctions: selling all items separately (SREV), selling them as a single grand bundle (BREV), and choosing the better of the two. Our technical cornerstone is a general upper bound on the optimal multidimensional revenue, parameterized by freely chosen item-wise caps, and expressed in terms of optimal single-item, Myersonian revenues and basic statistics of the value distributions. We derive this inequality through Lagrangian duality for a nonlinear programming formulation of the worst-case approximation ratio of separate-selling. Combining this inequality with carefully chosen caps and a probabilistic analysis of the resulting terms, we obtain improved approximation guarantees for all three deterministic auctions, both for general independent values and for iid values. Notably, we prove that $REV\le 2.5\max\{SREV,BREV\}$, improving the long-standing $5.2$ factor of Ma and Simchi-Levi and the $6$ factor of Babaioff, Immorlica, Lucier, and Weinberg. We complement this upper bound with a construction establishing a lower bound of $2.19$, improving the bound of $2$ by Rubinstein. For two iid items, we determine the exact approximation ratio of selling separately. Our proof constructs tight Lagrangian dual certificates for the aforementioned programming formulation, when item values lie in the grid $\{0,1/K,2/K,\dots,1\}$, for any discretization parameter $K$. Taking $K\to\infty$ yields the tight ratio $1+W(1/e)\approx1.2785$ in the continuous-valued setting, where $W$ is the Lambert-W function, closing the $[1.278,1.368]$ gap left by Hart and Nisan.

0.41

Critical-state algorithms for lot sizing with all-units discounts and variable inventory bounds

cs.DS ·2026-10-16 ·Kleitos Papadopoulos
theory similarity 0.59
Abstract

We study deterministic single-item lot sizing with all-units quantity discounts, linear holding costs, and time-varying end-of-period inventory bounds. Unit prices may vary arbitrarily over time. For one common positive discount threshold, we give an exact algorithm requiring $O(n^3)$ arithmetic operations and $O(n^2)$ working space, including recovery of an optimal purchase plan. The method combines a critical-state theorem in cumulative-purchase coordinates with two prefix-minimum scans per dynamic-programming layer. The structural argument accommodates downward price discontinuities and distinguishes prescribed from free terminal inventory. With a fixed global set of $m$ positive threshold values, the bounds become $O_m(n^{m+2})$ time and $O_m(n^{m+1})$ space. Period-specific thresholds admit the same exact construction, but its state set can be exponential. For commensurate flow data, an inventory-lattice implementation takes $O(PW)$ time, where $P$ is the total number of price tiers and $W$ is the largest inventory-lattice width. We also derive a conditional optimality certificate from a monotone one-threshold relaxation; this certificate does not imply a near-linear worst-case algorithm for arbitrary prices. Exact-arithmetic implementations are checked against exhaustive inventory dynamic programs and tier-enumeration linear programs. An illustrative timing study identifies settings in which the lattice implementation is preferable.

0.23

FIXP-Completeness in Second-Price Auctions

cs.GT cs.CC ·2026-10-31 ·Nobutaka Shimizu
theory similarity 0.59
Abstract

Computing equilibria is a fundamental algorithmic problem in game theory and economics. Although general frameworks are available for proving membership in FIXP, the class capturing exact fixed-point computation, establishing FIXP-completeness often remains challenging. We prove FIXP-completeness of exact equilibrium computation in three second-price auction models: (1). pacing with return-on-investment constraints, with multiplier cap $1+δ$ for every fixed rational $δ>0$ [Filos-Ratsikas, Hansen, Høgh, and Hollender (2024)]; (2). budget-constrained generalized second-price sponsored shopping [Hansen, Li, and Nie (2026)]; (3). budget-constrained throttling [Liu (2026)]. These results resolve open questions on the exact complexity of automated bidding. Our technical ingredient is a FIXP-complete generalized-circuit problem using only clipped affine gates and the reciprocal $x\mapsto1/(1+τx)$, for any fixed positive rational $τ$. This gate basis provides a common framework for the three auction reductions: simulating these gates in each model establishes FIXP-hardness without directly implementing multiplication or squaring.

0.15

Computing Equilibria in Integer Programming Games with Shared Constraints

cs.GT math.OC ·2026-10-03 ·Bainian Hao, Hyunwoo Lee, Robert Hildebrand, Carla Michini
similarity 0.58
Abstract

We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.

0.41