MPC 2026 - Issue 1
Refine
Year of publication
- 2026 (5)
Document Type
- Article (5)
Language
- English (5)
Has Fulltext
- yes (5)
Doubly nonnegative (DNN) relaxation usually provides a tight lower bound for a
mixed-binary quadratic program (MBQP). However, solving DNN problems is chal-
lenging because: (1) the problem size is ((n + l)2) for an MBQP with n variables
and l inequality constraints, and (2) the rank of optimal solutions cannot be estimated
a priori due to the absence of theoretical bounds. In this work, we propose RiNNAL+,
a Riemannian augmented Lagrangian method (ALM) for solving DNN problems. We
prove that the DNN relaxation of an MBQP, with matrix dimension (n + l + 1), is
equivalent to the SDP-RLT relaxation (based on the reformulation-linearization tech-
nique) with a smaller matrix dimension (n + 1). In addition, we develop a hybrid
method that alternates between two phases to solve the ALM subproblems. In phase
one, we apply low-rank matrix factorization and random perturbation to transform the
feasible region into a lower-dimensional manifold so that we can use the Riemannian
gradient descent method. In phase two, we apply a single projected gradient step to
update the rank of the underlying variable and escape from spurious local minima
arising in the first phase if necessary. To reduce the computation cost of the projected
gradient step, we develop pre-processing and warm-start techniques for acceleration.
Unlike traditional rank-adaptive methods that require extensive parameter tuning, our
hybrid method requires minimal tuning. Extensive experiments confirm the efficiency
and robustness of RiNNAL+ in solving various classes of large-scale DNN problems
In this paper, we introduce a novel semidefinite programming framework for designing custom frugal resolvent splitting algorithms which find a zero in the sum of n monotone operators. This framework features a number of design choices which facilitate creating resolvent splitting algorithms with specific communication structure. We illustrate these design choices using a variety of constraint sets and objective functions, as well as the use of a mixed-integer SDP to minimize time per iteration or required number of communications between the resolvents which define the splitting. Using the Performance Estimation Problem (PEP) framework, we provide parameter selections, such as step size, which for high dimensional problems provide optimal contraction factors in the algorithms. Among the algorithm design choices we introduce, we provide a characterization of algorithm designs which provide minimal convergence time given structural properties of the monotone operators, resolvent computation times, and communication latencies.
Adjustable robust optimization (ARO) is a powerful tool to model problems that have uncertain data and that feature a two-stage decision-making process. Computationally, they are often addressed using the column-and-constraint generation (CCG) algorithm introduced by Zeng and Zhao [45]. While it was empirically shown that the algorithm scales well if all second-stage decisions are continuous, the presence of integer variables in the second stage rapidly leads to challenging large-scale mixed-integer problems within CCG. These problems can no longer be solved to global optimality within reasonable time limits in general. In this work, we explicitly focus on ARO problems with mixed-integer second-stage decisions and discuss the main difficulties of successfully applying CCG to this problem class. We then introduce, for a large set of problems with specific structural properties, a stronger formulation, which can be used in place of the master problem in the classic CCG algorithm. We show how this model can be effectively solved by column generation (CG). Additionally, we introduce a new CG-based heuristic that is able to generate new feasible points to speed up the overall method. We apply this nested scheme, combining CCG and CG, to three problems from logistics and scheduling to show the applicability of our approach.
Support matrix machine (SMM) is a successful supervised classification model for matrix-type samples. Unlike support vector machines, it employs low-rank regularization on the regression matrix to effectively capture the intrinsic structure embedded in each input matrix. When solving a large-scale SMM, a major challenge arises from the potential increase in sample size, leading to substantial computational and storage burdens. To address these issues, we design a semismooth Newton-CG (SNCG) based augmented Lagrangian method (ALM) for solving the SMM. The ALM exhibits an asymptotic R-superlinear convergence if a strict complementarity condition is satisfied. The SNCG method is employed to solve the ALM subproblems, achieving at least a superlinear convergence rate under the nonemptiness of an index set. Furthermore, the sparsity of samples and the low-rank nature of solutions enable us to reduce the computational cost and storage demands for the Newton linear systems. Additionally, we develop an adaptive sieving strategy that generates a solution path for the SMM by exploiting sample sparsity. The finite convergence of this strategy is also demonstrated. Numerical experiments on both large-scale real and synthetic datasets validate the effectiveness of the proposed methods.
A conflict graph represents logical relations between binary variables, and effective use of the graph can significantly accelerate branch-and-cut solvers for mixed-integer programming (MIP). In this paper we develop efficient parallel conflict graph management: conflict detection; maximal clique generation; clique extension; and clique merging. We leverage parallel computing in order to intensify computational effort on the conflict graph, thereby generating a much larger pool of cutting planes than what can be practically achieved in serial. Computational experiments demonstrate that the expanded pool of cuts enabled by parallel computing lead to substantial reductions in total MIP solve time, especially for more challenging cases.