Intersection Cuts for Mixed-Integer Nonlinear Programs via Decision-Diagram-Free Sets

We introduce a novel decision-diagram-based framework for generating intersection cuts to strengthen polyhedral relaxations of bounded mixed-integer nonlinear programs (MINLPs) with general nonlinear constraints. Building on decision diagrams (DDs) that provide outer approximations of MINLP feasible regions, we propose the concept of DD-free sets, which are convex regions whose interiors do not intersect the sets … Read more

Quantum Optimization: from origins to current challenges and future perspectives

Quantum optimization has emerged at the intersection of quantum computing and operations research, driven by the prospect of addressing challenging combinatorial optimization problems through quantum and quantum-inspired computational approaches. This paper provides a structured review of the field from a past, present, and future perspective. We first trace the evolution of quantum optimization from the … Read more

Tightening bilinear relaxations using geometric rotation

A classical approach for handling non-convex optimization problems involving bilinear terms is to approximate the bilinear expressions using McCormick relaxations. Such relaxations are central to global optimization methods, with the spatial branch-and-bound (sBB) algorithm being one of the most widely used approaches. In the spatial branching step, the algorithm partitions the feasible region using axis-aligned … Read more

Cubic Optimization over Three Nonnegative Integers Is NP-hard

We prove that deciding whether an integer cubic polynomial takes a value at most one over three nonnegative integers is NP-hard. Hardness holds even when every feasible objective value is a positive integer, so every constructed instance has a finite, attained minimum. This establishes a sharp dimension boundary for the tractability of cubic integer optimization … Read more

Steering the Feedback Loop: Policy Gradients for Online Performative Optimization

Performative decision-making arises in many real-world problems where decisions influence the populations that generate future data. A major line of existing research focuses on learning performatively stable solutions. We study average-reward performative optimization, where the learner observes an evolving population through sample batches of fixed size and learns from a single continuing trajectory with unknown … Read more

Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?

For more than 20 years, single-leader multi-follower (SLMF) problems have been treated as a more difficult class of problems in comparison to bilevel optimization. In this work we challenge this common belief, studying whether SLMF problems can be reformulated as equivalent bilevel optimization problems. We consider both optimistic and pessimistic formulations. For the optimistic case … Read more

Treewidth and the complexity of box-constrained quadratic programs

We consider the problem of minimizing a sparse quadratic function over the unit hypercube. In binary quadratic programming, treewidth of the interaction graph is a central parameter for tractability: bounded treewidth yields polynomial-time solvability. Motivated by this fact, we investigate whether treewidth plays a similar role when the binary domain is replaced by the unit … Read more

Redundant objectives in multiobjective optimization

This work examines three different concepts of objective redundancy in multiobjective optimization. Multiobjective optimization is known to suffer from the curse of dimensionality and we aim at reducing the number of objective functions which need to be considered. In this context, a set of objectives is called redundant if the sets of weakly efficient, efficient, … Read more

A branch-and-bound algorithm for the computation of optimal point mappings of parametric optimization problems

We propose a novel branch‑and‑bound algorithm that constructs rigorous outer approximations of the optimal point mapping for parametric optimization problems with guaranteed feasibility and optimality tolerances. The method uses the improvement‑function reformulation to define discarding and inclusion tests on sub-boxes, constructing a rigorous outer approximation. Under the same regularity conditions that ensure exactness of this … Read more

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

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