MPC 2025 - Issue 3
Refine
Year of publication
- 2025 (5)
Document Type
- Article (5)
Language
- English (5)
Has Fulltext
- yes (5)
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.