Non-convex integer programming: a deterministic solution method of the large block sale problem
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.
Related
- On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
- Convex Mixed-Integer Programming for Invariant Predictions from Multi-environment Data
- A New Perspective on Clustering: A Mixed-norm Model and its Solution by Progressive Integer Programming
- Solving a PDE-constrained antenna design problem by mixed-integer programming
- A complete solution to the reverse isoperimetric problem for λ-convex bodies
BibTeX
@misc{nizard2026nonconvex,
title = {{Non-convex integer programming: a deterministic solution method of the large block sale problem}},
author = {David Nizard and Dominique Quadri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14962},
eprint = {2610.14962},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14962},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Non-convex integer programming: a deterministic solution method of the large block sale problem
AU - David Nizard
AU - Dominique Quadri
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14962
UR - https://arxiv.org/abs/2610.14962
AB - 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.
ER -