Linear programming has been practically solved mainly by simplex and interior point methods. Compared with the weakly polynomial complexity obtained by the interior point methods, the existence of strongly polynomial bounds for the length of the pivot path generated by the simplex methods remains a mystery. In this paper, we propose two novel pivot experts that leverage both global and local information of the linear programming instances for the primal simplex method and show their excellent performance numerically. The experts can be regarded as a benchmark to evaluate the performance of classical pivot rules, although they are hard to directly implement. To tackle this challenge, we employ a graph convolutional neural network model, trained via imitation learning, to mimic the behavior of the pivot expert. Our pivot rule, learned empirically, displays a significant advantage over conventional methods in various linear programming problems, as demonstrated through a series of rigorous experiments.

Integer programming with block structures has received considerable attention recently and is widely used in many practical applications such as train timetabling and vehicle routing problems. It is known to be NP-hard due to the presence of integer variables. We define a novel augmented Lagrangian function by directly penalizing the inequality constraints and establish the strong duality between the primal problem and the augmented Lagrangian dual problem. Then, a customized augmented Lagrangian method is proposed to address the block-structures. In particular, the minimization of the augmented Lagrangian function is decomposed into multiple subproblems by decoupling the linking constraints and these subproblems can be efficiently solved using the block coordinate descent method. We also establish the convergence property of the proposed method. To make the algorithm more practical, we further introduce several refinement techniques to identify high-quality feasible solutions. Numerical experiments on a few interesting scenarios show that our proposed algorithm often achieves a satisfactory solution and is quite effective.

The cardinality constrained mean–variance (CCMV) portfolio selection model aims to identify a subset of the candidate assets such that the constructed portfolio has a guaranteed expected return and minimum variance. By formulating this model as the mixed-integer quadratic program (MIQP), the exact solution can be solved by a branch-and-bound algorithm. However, computational efficiency is the central issue in the time-sensitive portfolio investment due to its NP-hardness properties. To accelerate the solution speeds to CCMV portfolio optimization problems, we develop various heuristic methods based on techniques such as continuous relaxation, l1-norm approximation, integer optimization, and relaxation of semi-definite programming (SDP). We evaluate our heuristic methods by applying them to the US equity market dataset. The experimental results show that our SDP-based method is effective in terms of the computation time and the approximation ratio. Our SDP-based method performs even better than a commercial MIQP solver when the computational time is limited. In addition, several investment companies in China have adopted our methods, gaining good returns. This paper sheds light on the computation optimization for financial investments.