Table of Content

30 March 2025, Volume 13 Issue 1

Previous Issue   

MILP Acceleration: A Survey from Perspectives of Simplex Initialization and Learning-Based Branch and Bound

Meng-Yu Huang, Ling-Ying Huang, Yu-Xing Zhong, Hui-Wen Yang, Xiao-Meng Chen, Wei Huo, Jia-Zheng Wang, Fan Zhang, Bo Bai, Ling Shi

2025, 13(1):  1-55.  doi:10.1007/s40305-023-00493-1

Asbtract ( 75 )   PDF  

References | Related Articles | Metrics

Mixed integer linear programming (MILP) is an NP-hard problem, which can be solved by the branch and bound algorithm by dividing the original problem into several subproblems andforming a search tree. For each subproblem, linear programming(LP) relaxation can be solved to find the boundformaking thefollowing decisions. Recently, with the increasing dimension of MILPs in different applications, how to accelerate the solution process becomes a huge challenge. In this survey, we summarize techniques and trends to speed up MILP solving from two perspectives. First, we present different approaches in simplex initialization, which can help to accelerate the solution of LP relaxation for each subproblem. Second, we introduce the learning-based technologies in branch and bound algorithms to improve decision making in tree search. We also propose several potential directions and extensions to further enhance the efficiency of solving different MILP problems.

Robust Portfolio Selection with Distributional Uncertainty and Integer Constraints

Ri-Peng Huang, Ze-Shui Xu, Shao-Jian Qu, Xiao-Guang Yang, Mark Goh

2025, 13(1):  56-82.  doi:10.1007/s40305-023-00466-4

Asbtract ( 70 )   PDF  

References | Related Articles | Metrics

This paper studies a robust portfolio selection problem with distributional ambiguity and integer constraint. Different from the assumption that the expected returns of risky assets are known, we define an ambiguity set containing the true probability distribution based on Kullback-Leibler (KL) divergence. In contrast to the traditional portfolio optimization model, the invested amounts of risky assets are integers, which is more in line with the real trading scenario. For tractability, we transform the resulting semiinfinite programming into a convex mixed-integer nonlinear programming (MINLP) problem by using Fenchel duality. To solve the convex MINLP problem efficiently, a modified generalized Benders decomposition (GBD) method is proposed. Through the back-test of real market data, the performance of the proposed model is not sensitive to the input parameters. Therefore, the proposed method has much importance value for both individual and institutional investors.

Mirror Frameworks for Relatively Lipschitz and Monotone-Like Variational Inequalities

Hui Zhang, Yu-Hong Dai

2025, 13(1):  83-113.  doi:10.1007/s40305-023-00458-4

Asbtract ( 69 )   PDF  

References | Related Articles | Metrics

Nonconvex-nonconcave saddle-point optimization in machine learning has triggered lots of research for studying non-monotone variational inequalities (VIs). In this work, we introduce two mirror frameworks, called mirror extragradient method and mirror extrapolation method, for approximating solutions to relatively Lipschitz and monotone-like VIs. The former covers the well-known Nemirovski’s mirror prox method and Nesterov’s dual extrapolation method, and the recently proposed Bregman extragradient method; all of them can be reformulated into a scheme that is very similar to the original form of extragradient method. The latter includes the operator extrapolation method and the Bregman extrapolation method as its special cases. The proposed mirror frameworks allow us to present a unified and improved convergence analysis for all these existing methods under relative Lipschitzness and monotone-like conditions that may be the currently weakest assumptions guaranteeing (sub) linear convergence.

Monotone Splitting SQP Algorithms for Two-block Nonconvex Optimization Problems with General Linear Constraints and Applications

Jin-Bao Jian, Guo-Dong Ma, Xiao Xu, Dao-Lan Han

2025, 13(1):  114-141.  doi:10.1007/s40305-023-00523-y

Asbtract ( 55 )   PDF  

References | Related Articles | Metrics

This work discusses a class of two-block nonconvex optimization problems with linear equality, inequality and box constraints. Based on the ideas of alternating direction method with multipliers (ADMM), sequential quadratic programming (SQP) and Armijo line search technique, we propose a novel monotone splitting SQP algorithm. First, the discussed problem is transformed into an optimization problem with only linear equality and box constraints by introduction of slack variables. Second, the idea of ADMM is used to decompose the traditional quadratic programming (QP) subproblem. In particular, the QP subproblem corresponding to the introduction of the slack variable is simple, and it has an explicit optimal solution without increasing the computational cost. Third, the search direction is generated by the optimal solutions of the subproblems, and the new iteration point is yielded by an Armijo line search with augmented Lagrange function. Fourth, the multiplier is updated by a novel approach that is different from the ADMM. Furthermore, the algorithm is extended to the associated optimization problem where the box constraints can be replaced by general nonempty closed convex sets. The global convergence of the two proposed algorithms is analyzed under weaker assumptions. Finally, some preliminary numerical experiments and applications in mid-to-large-scale economic dispatch problems for power systems are reported, and these show that the proposed algorithms are promising.

Maximizing the Ratio of Monotone DR-Submodular Functions on Integer Lattice

Sheng-Min-Jie Chen, Dong-Lei Du, Wen-Guo Yang, Sui-Xiang Gao

2025, 13(1):  142-160.  doi:10.1007/s40305-023-00469-1

Asbtract ( 60 )   PDF  

References | Related Articles | Metrics

In this work, we focus on maximizing the ratio of two monotone DR-submodular functions on the integer lattice. It is neither submodular nor supermodular. We prove that the Threshold Decrease Algorithm is a 1—e^-(1-k_g)—ε approximation ratio algorithm. Additionally, we construct the relationship between maximizing the ratio of two monotone DR-submodular functions and maximizing the difference of two monotone DR-submodular functions on the integer lattice. Based on this relationship, we combine the dichotomy technique and Threshold Decrease Algorithm to solve maximizing the difference of two monotone DR-submodular functions on the integer lattice and prove its approximation ratio is f(x)-g(x) 1—e^-(1-k_g) f (x^*)—g(x^*)—ε. To the best of our knowledge, before us, there was no work to focus on maximizing the ratio of two monotone DR-submodular functions on integer lattice by using the Threshold Decrease Algorithm.

A Variable Metric Extrapolation Proximal Iterative Hard Thresholding Method

Xue Zhang, Xiao-Qun Zhang

2025, 13(1):  161-183.  doi:10.1007/s40305-023-00459-3

Asbtract ( 57 )   PDF  

References | Related Articles | Metrics

In this paper, we propose a variable metric extrapolation proximal iterative hard thresholding (VMEPIHT) method for nonconvex $\ell_0$-norm sparsity regularization problem which has wide applications in signal and image processing, machine learning and so on. The VMEPIHT method is based on the forward-backward splitting (FBS) method, and variable metric strategy is employed in the extrapolation step to speed up the algorithm. The proposed method’s convergence, linear convergence rate and superlinear convergence rate are shown under appropriate assumptions. Finally, we conduct numerical experiments on compressed sensing problem and CT image reconstruction problem to confirm the efficiency of the proposed method, compared with other state-of-the-art methods.

Portfolio-Consumption Choice with Information Cost

Zhou Yang, Rui-Feng Mai, Man-Ni Lv

2025, 13(1):  184-209.  doi:10.1007/s40305-023-00472-6

Asbtract ( 62 )   PDF  

References | Related Articles | Metrics

This paper studies an optimal portfolio-consumption choice with information cost. In financial market, investors collect market information to understand the market parameters,make reasonable investment and consumption choice while controlling risks, and finally gain utility. Information acquisition and portfolio-consumption choice are two important steps of investment behavior, which are a whole. Nevertheless, the existing literature usually only considers the cost of information acquisition or only considers portfolio-consumption choice. In order to study the overall behavior of investors in financial market, these two issues are considered together in this paper. Firstly, based on portfolio-consumption choice model in ambiguity market, a bilevel optimization problem is established to discuss how investors should acquire information and make investment-consumption strategies to maximize their comprehensive utilities. Then, the inner stochastic game problem with constraints is simplified into finding saddle point of a function, and the value function of game problem is provided via the function value at the saddle point, so that the objective function of the outer optimization problem can be represented as a non-convex and non-concave binary function. At last, the existence condition and the range of the optimal strategy are presented, and the sensitivity analysis is studied.

Applying Convexificators in Nonsmooth Multiobjective Semi-infinite Fractional Interval-Valued Optimization

Nazih Abderrazzak Gadhi, Aissam Ichatouhane

2025, 13(1):  210-226.  doi:10.1007/s40305-023-00513-0

Asbtract ( 59 )   PDF  

References | Related Articles | Metrics

In this work, we explore a nonsmooth semi-infinite multiobjective fractional interval-valued optimization problem. Using an adequate constraint qualification, we establish necessary optimality conditions in terms of Karush-Kuhn-Tucker multipliers and upper semiregular convexificators. We do not assume that the interval-valued objective function is smooth or that it is convex. There are examples highlighting both our results and the limits of certain past studies.

The Effect of Retailer’ Social Responsibility and Government Subsidy on the Performance of Low-Carbon Supply Chain

Ping Wang, Xiao-Hui Yu, Qiang Zhang

2025, 13(1):  227-267.  doi:10.1007/s40305-023-00479-z

Asbtract ( 65 )   PDF  

References | Related Articles | Metrics

Based on the cap-and-trade regulation, the effect of retailer’s social responsibility and subsidy are analyzed in a two-level low-carbon supply chain. The government subsidizes manufacturer to encourage low-carbon technological innovation. It is gotten that both retailer’s social responsibility and subsidy can improve the profit of manufacturer and reduce the carbon emission level. Although more subsidies to manufacturer indeed may decrease the profit of retailer, it is good measure to promote the centralized decision-making between the retailer and manufacturer. A certain retailer’s social responsibilities are good for the carbon emission reduction, but it also brings about the decline of profit in the supply chain. The centralized decision-making is always the best choice strategy for the carbon emission reduction, while in the decentralized decision-making situation, the retailer has more possibilities to care about social responsibility.

A Semidefinite Relaxation Method for Linear and Nonlinear Complementarity Problems with Polynomials

Jin-Ling Zhao, Yue-Yang Dai

2025, 13(1):  268-286.  doi:10.1007/s40305-023-00491-3

Asbtract ( 66 )   PDF  

References | Related Articles | Metrics

This paper considers semidefinite relaxation for linear and nonlinear complementarity problems. For some particular copositive matrices and tensors, the existence of a solution for the corresponding complementarity problems is studied. Under a general assumption, we show that if the solution set of a complementarity problem is nonempty, then we can get a solution by the semidefinite relaxation method; while if it does not have a solution, we can obtain a certificate for the infeasibility. Some numerical examples are given.

Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties

Pei-Jia Yang, Wen-Chang Luo

2025, 13(1):  287-296.  doi:10.1007/s40305-023-00478-0

Asbtract ( 62 )   PDF  

References | Related Articles | Metrics

In the k-product uncapacitated facility location problem with penalties, we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be opened. There are k different kinds of products to be supplied by a set of open facilities. Each open facility can supply only a distinct product with a non-negative fixed cost determined by the product it wants to supply. Each client is either supplied with k kinds of products by a set of k different open facilities or completely rejected. There is a non-negative service cost between each pair of locations and also a penalty cost for each client if its service is rejected. These service costs are assumed to be symmetric and satisfy the triangle inequality. The goal is to select a set of clients to reject their service and then choose a set of facilities to be opened to service the remaining clients so that the total cost of opening facilities, servicing the clients, and the penalty is minimized. We address two different integer programs to describe the problem. Based on the linear programming rounding technique, we propose a (2k +1)-approximation algorithm for this problem.

Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs

Si-Nan Hu, Yue-Jian Peng

2025, 13(1):  297-312.  doi:10.1007/s40305-023-00494-0

Asbtract ( 72 )   PDF  

References | Related Articles | Metrics

For graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any coloring of the edges of the complete graph K_N in red or blue yields a red G or a blue H. Denote the union of t disjoint copies of a graph F by tF. We call tK₂ a stripe. In this paper, we completely determine Ramsey numbers of stripes versus trees and unicyclic graphs. Our result also implies that a tree is tK₂-good if and only if the independence number of this tree is no less than t. As an application, we improve the known Ramsey numbers of stars versus fan graphs. Moreover, we determine the bipartite Ramsey numbers of a connected bipartite graph versus stripes.

A Note on R-Linear Convergence of Nonmonotone Gradient Methods

Xin-Rui Li, Ya-Kui Huang

2025, 13(1):  313-325.  doi:10.1007/s40305-023-00468-2

Asbtract ( 65 )   PDF  

References | Related Articles | Metrics

Nonmonotone gradient methods generally perform better than their monotone counterparts especially on unconstrained quadratic optimization. However, the known convergence rate of the monotone method is often much better than its nonmonotone variant. With the aim of shrinking the gap between theory and practice of nonmonotone gradient methods, we introduce a property for convergence analysis of a large collection of gradient methods. We prove that any gradient method using stepsizes satisfying the property will converge R-linearly at a rate of 1-λ₁/M₁, where λ₁ is the smallest eigenvalue of Hessian matrix and M₁ is the upper bound of the inverse stepsize. Our results indicate that the existing convergence rates of many nonmonotone methods can be improved to 1-1/κ with κ being the associated condition number.