Refine
Year of publication
Document Type
- Article (283)
Language
- English (283)
Keywords
- Software (191)
- Theoretical Computer Science (187)
The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a multitude of applications, among them mathematical finance, machine learning (clustering), and modeling in biosciences (e.g., selection and ecology). This paper deals with such StQPs under an additional sparsity or cardinality constraint, which, even for convex objectives, renders NP-hard problems. One motivation to study StQPs under such sparsity restrictions is the high-dimensional portfolio selection problem with too many assets to handle, in particular, in the presence of transaction costs. Here, relying on modern conic optimization techniques, we present tractable convex relaxations for this relevant but difficult problem. We propose novel equivalent reformulations of these relaxations with significant dimensional reduction, which is essential for the tractability of these relaxations when the problem size grows. Moreover, we propose an instance generation procedure which systematically avoids too easy instances. Our extensive computational results illustrate the high quality of the relaxation bounds in a significant number of instances. Furthermore, in contrast with exact mixed-integer quadratic programming models, the solution time of the relaxations is very robust to the choices of the problem parameters. In particular, the reduced formulations achieve significant improvements in terms of the solution time over their counterparts.
We optimize the running time of the primal-dual algorithms by optimizing their stopping criteria for solving convex optimization problems under affine equality constraints, which means terminating the algorithm earlier with fewer iterations. We study the relations between four stopping criteria and show under which conditions they are accurate to detect optimal solutions. The uncomputable one: "Optimality gap and Feasibility error", and the computable ones: the "Karush–Kuhn–Tucker error", the "Projected Duality Gap", and the "Smoothed Duality Gap". Assuming metric sub-regularity or quadratic error bound, we establish that all of the computable criteria provide practical upper bounds for the optimality gap, and approximate it effectively. Furthermore, we establish comparability between some of the computable criteria under certain conditions. Numerical experiments on basis pursuit, and quadratic programs with(out) non-negative weights corroborate these findings and show that the smoothed duality gap is more widely applicable than the rest.
A caterpillar is a connected graph such that the removal of all its vertices with degree results in a path. Given a graph G, a caterpillar-packing of G is a set of vertex-disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of caterpillar-packings of a graph, which corresponds to feasible solutions of the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) presented by Rinaldi and Franz (Eur J Oper Res 183:1371–1384, 2007) We show new facet-preserving procedures for this polytope, and we present a general cut-generating strategy based on these procedures. Computational experiments show that this approach is effective in practice.
Mixed-integer nonlinear optimization encompasses a broad class of problems that
present both theoretical and computational challenges. We propose a new type of
method to solve these problems based on a branch-and-bound algorithm with convex node relaxations. These relaxations are solved with a Frank–Wolfe algorithm over the convex hull of mixed-integer feasible points instead of the continuous relaxation via calls to a mixed-integer linear solver as the linear minimization oracle. The proposed method computes feasible solutions while working on a single representation of the polyhedral constraints, leveraging the full extent of mixed-integer linear solvers without an outer approximation scheme and can exploit inexact solutions of node subproblems.
We propose a reference framework to apply the multiparent path relinking (MPR) methodology. MPR is an extension of path relinking (PR) that has been proposed and described but, to the best of our knowledge, it has never been applied. PR is a trajectory-based neighborhood search strategy that explores paths that traverse pairs of solutions. PR has been widely used for search intensification purposes within metaheuristic implementations. To show how MPR can be embedded in more than one setting, our proposal consists of both employing MPR as a post-processing step in a greedy randomized adaptive search procedure (GRASP) and as the combination method in a scatter search (SS). We use the power dominating set problem (PDSP) as our testing platform because its difficulty and structure enable the design and assessment of various strategies. The PDSP seeks to find the minimum placement of measurement devices in an electrical network to monitor the entire system. Our computational experiments are designed to identify the contribution of each element of our proposed MRP implementations.
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.