The 10 most recently published documents
Learning to use local cuts
(2025)
An essential component in modern solvers for mixed-integer (linear) programs (MIPs)
is the separation of additional inequalities (cutting planes) to tighten the linear pro-
gramming relaxation. Various algorithmic decisions are necessary when integrating
cutting plane methods into a branch-and-bound (B&B) solver as there is always the
trade-off between the efficiency of the cuts and their overhead, given that they tend
to slow down the solution time of the relaxation. One of the most crucial questions
is: Should cuts only be generated globally at the root or also locally at nodes of the
tree? We address this question by a machine learning approach for which we train a
regression forest to predict the speed-up (or slow-down) provided by using local cuts.
We demonstrate with an open implementation that this helps to improve the perfor-
mance of the FICO Xpress MIP solver on a public test set of general MIP instances.
We further report on the impact of a practical implementation inside Xpress on a large,
diverse set of real-world industry MIPs.
We consider the problem of maximizing a convex quadratic function over a bounded
polyhedral set. We design a new framework based on SDP relaxations and cutting
plane methods for solving the associated reference value problem. The major novelty
is a new way to generate valid cuts through the doubly nonnegative (DNN) relaxation.
We establish various theoretical properties of the DNN relaxation, including its equiv-
alence with the Shor relaxation of an equivalent quadratically constrained problem,
the strong duality, and the generation of valid cuts from an approximate solution of
the DNN relaxation returned by an arbitrary SDP solver. Computational results on
both real and synthetic data demonstrate the efficiency of the proposed method and
its ability to solve high-dimensional problems with dense data. In particular, our new
algorithm successfully solves in 3 days the reference value problem arising from com-
putational biology for a dataset containing more than 300,000 instances of dimension
78. In contrast, CPLEX or Gurobi is estimated to require years of computational time
for the same dataset on the same computing platform.
MATRS: heuristic methods for noisy derivative-free bound-constrained mixed-integer optimization
(2025)
This paper introduces MATRS, a novel matrix adaptation trust-region strategy designed
to solve noisy derivative-free mixed-integer optimization problems with simple bounds
in low dimensions. MATRS operates through a repeated cycle of five phases: mutation,
selection, recombination, trust-region, and mixed-integer, executed in this sequence.
But if in the mutation phase a new best point (the point with the lowest inexact function
value among all evaluated points so far) is found, the selection, recombination, and
trust-region phases are skipped. Similarly, if the recombination phase finds a new best
point, the trust-region phase is skipped. The mixed-integer phase is always performed.
To search for a new best point, the mutation and recombination phases use extrapolation whereas the mixed-integer phase performs a mixed-integer line search along directionsn estimated to go into a valley. Numerical results on several collections of test problems show that MATRS is competitive with state-of-the-art derivative-free mixedinteger solvers.
This paper studies generalized semi-infinite programs (GSIPs) given by polynomials. We propose a hierarchy of polynomial optimization relaxations to solve them. They are based on Lagrange multiplier expressions and polynomial extensions. Moment-SOS relaxations are applied to solve the polynomial optimization. The convergence of this hierarchy is shown under certain conditions. In particular, the classical semi-infinite programs can be solved as a special case of GSIPs. We also study GSIPs that have convex infinity constraints and show that they can be solved exactly by a single polynomial optimization relaxation. The computational efficiency is demonstrated by extensive numerical results.
In this paper, we propose an adaptive sieving (AS) strategy for solving general sparse machine learning models by effectively exploring the intrinsic sparsity of the solutions, wherein only a sequence of reduced problems with much smaller sizes need to be solved. We further apply the proposed AS strategy to generate solution paths for large-scale sparse optimization problems efficiently. We establish the theoretical guarantees for the proposed AS strategy including its finite termination property. Extensive numerical experiments are presented in this paper to demonstrate the effectiveness and flexibility of the AS strategy to solve large-scale machine learning models.
Optimization over an embedded submanifold defined by equality constraints c(x) = 0
has attracted much interest over the past few decades due to its wide applications in var-
ious areas, including computer vision, signal processing, numerical linear algebra, and
deep learning. For solving such problems, many related optimization packages have
been developed based on Riemannian optimization approaches, which rely on some
basic geometrical materials of Riemannian manifolds, including Riemannian gradi-
ents, retractions, vector transports, etc. These geometrical materials can be challenging
to determine in general. In fact, existing packages only accommodate a few well-known
manifolds whose geometrical materials are more easily accessible. For other mani-
folds that are not contained in these packages, the users have to develop the geometric
materials by themselves. In addition, it is not always tractable to adapt the advanced fea-
tures from various state-of-the-art unconstrained optimization solvers to Riemannian
optimization approaches. Here we introduce a user-friendly Python package, CDOpt
(available at https://cdopt.github.io/ under BSD 3-clause license), for solving a class of
Riemannian optimization problems. CDOpt is designed to complement existing Riemannian optimization packages by transforming Riemannian optimization problems
into their unconstrained counterparts through the constraint dissolving approach. We
prove that the when the penalty parameter in the constraint dissolving approach is suffi-
ciently large, Riemannian optimization problems and their unconstrained counterparts
are equivalent. Therefore, solving Riemannian optimization problems through CDOpt
can directly benefit from various existing solvers and the rich expertise gained over
the past few decades for unconstrained optimization. Moreover, all the computations
in CDOpt related to any manifold in question are conducted through its constraints
expression, hence users can easily define new manifolds in CDOpt without any back-
ground on differential geometry. Furthermore, CDOpt extends the neural layers from
PyTorch and Flax, thus allowing users to train manifold constrained neural networks
directly by the solvers for unconstrained optimization. Extensive numerical experi-
ments demonstrate that CDOpt is highly efficient and robust in solving various classes
of Riemannian optimization problems.
In this paper, we propose a branch-and-bound algorithm for solving nonconvex
quadratic programming problems with box constraints (BoxQP). Our approach com-
bines existing tools, such as semidefinite programming (SDP) bounds strengthened
through valid inequalities, with a new class of optimality-based linear cuts which leads
to variable fixing. The most important effect of fixing the value of some variables is
the size reduction along the branch-and-bound tree, allowing to compute bounds by
solving SDPs of smaller dimension. Extensive computational experiments over large
dimensional (up to n = 200) test instances show that our method is the state-of-the-art
solver on large-scale BoxQPs. Furthermore, we test the proposed approach on the class
of binary QP problems, where it exhibits competitive performance with state-of-the-art
solvers.
In this paper, we address the problem of approximating and over/under-estimating
univariate functions with piecewise linear (PWL) functions with the minimum num-
ber of linear segments given a bound on the allowed pointwise approximation error.
Through a new geometric approach and building on the work of Ngueveu (Eur J Oper
Res 275:1058–1071, 2019), we develop new algorithms that can solve the problem in
quasi-logarithmic time on a very broad class of error types. Such algorithms find many
applications, mostly related to solving certain classes of (mixed-integer) nonlinear and
nonconvex programming (MINLP) problems by mixed-integer linear programming
(MILP) techniques. An efficient implementation of our algorithms is available as a
Julia package. Benchmarks are also provided to showcase how our method outper-
forms the state-of-the-art for this problem. Finally, we show how our algorithms can
be used to efficiently solve certain classes of MINLP problems through a case study
on multicommodity network design problems with congestion.
The top-k-sum operator computes the sum of the largest k components of a given
vector. The Euclidean projection onto the top-k-sum sublevel set serves as a cru-
cial subroutine in iterative methods to solve composite superquantile optimization
problems. In this paper, we introduce a solver that implements two finite-termination
algorithms to compute this projection. Both algorithms have O(n) complexity of float-
ing point operations when applied to a sorted n-dimensional input vector, where the
absorbed constant is independent of k. This stands in contrast to an existing grid-
search-inspired method that has O(k(n − k)) complexity, a partition-based method
with O(n + D log D) complexity, where D ≤ n is the number of distinct elements
in the input vector, and a semismooth Newton method with a finite termination prop-
erty but unspecified floating point complexity. The improvement of our methods over
the first method is significant when k is linearly dependent on n, which is frequently
encountered in practical superquantile optimization applications. In instances where
the input vector is unsorted, an additional cost is incurred to (partially) sort the vector,
whereas a full sort of the input vector seems unavoidable for the other two methods.
To reduce this cost, we further derive a rigorous procedure that leverages approx-
imate sorting to compute the projection, which is particularly useful when solving
a sequence of similar projection problems. Numerical results show that our methods
solve problems of scale n = 10 7 and k = 10 4 within 0.05 s, whereas the most compet-
itive alternative, the semismooth Newton-based method, takes about 1 s. The existing
grid-search method and Gurobi’s QP solver can take from minutes to hours
In this paper we introduce a new algorithm for the k-Shortest Simple Paths (k-SSP)
problem with an asymptotic running time matching the state of the art from the liter-
ature. It is based on a black-box algorithm due to Roditty and Zwick [30] that solves
at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without
specifying how this is done. We fill this gap using a novel approach: we turn the scalar
2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on
grid graphs and on road networks show that the new algorithm is very efficient in
practice.