Optimization modeling is fundamental to decision-making in fields such as supply chain management, logistics, and financial engineering, but its complexity presents a major barrier to adoption. Automating model creation from natural language is key to improving efficiency and access. However, while Large Language Models (LLMs) are a promising tool for this, they often produce flawed or infeasible results due to errors and hallucinations. To address this issue, we propose Solver-Informed Reinforcement Learning (SIRL), a framework that uses Reinforcement Learning with Verifiable Reward to improve LLMs’ ability to generate accurate and executable optimization models. Specifically, SIRL automatically assesses the executable code and the instance-level mathematical model represented by the associated .lp files. This process yields precise feedback on syntactic validity, feasibility, and solution quality, which serves as a direct reward signal to guide the reinforcement learning process. Furthermore, this verification mechanism also supports our instance-enhanced self-consistency method for creating high-quality training data. Extensive experiments on diverse public benchmarks demonstrate that models trained with our SIRL framework achieve state-of-the-art performance, substantially outperforming existing methods in generating accurate and executable optimization models. Specifically, our SIRL-32B model surpasses DeepSeek-V3 and OpenAI-o3 on the majority of these benchmarks. Our code is publicly available at https://github.com/Cardinal-Operations/SIRL.

The alternating-direction-method-of-multipliers-based (ADMM-based) interior point method, or ABIP method, is a hybrid algorithm that effectively combines interior point method (IPM) and first-order methods to achieve a performance boost in large-scale linear optimization. Different from traditional IPM that relies on computationally intensive Newton steps, the ABIP method applies ADMM to approximately solve the barrier penalized problem. However, similar to other first-order methods, this technique remains sensitive to condition number and inverse precision. In this paper, we provide an enhanced ABIP method with multiple improvements. First, we develop an ABIP method to solve the general linear conic optimization and establish the associated iteration complexity. Second, inspired by some existing methods, we develop different implementation strategies for the ABIP method, which substantially improve its performance in linear optimization. Finally, we conduct extensive numerical experiments in both synthetic and real-world data sets to demonstrate the empirical advantage of our developments. In particular, the enhanced ABIP method achieves a 5.8× reduction in the geometric mean of run time on 105 selected linear optimization instances from Netlib, and it exhibits advantages in certain structured problems, such as support vector machine and PageRank. However, the enhanced ABIP method still falls behind commercial solvers in many benchmarks, especially when high accuracy is desired. We posit that it can serve as a complementary tool alongside well-established solvers. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: This research was supported by the National Natural Science Foundation of China [Grants 72394360, 72394364, 72394365, 72225009, 72171141, and 72150001] and by the Program for Innovative Research Team of Shanghai University of Finance and Economics. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0017 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0017 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Identifying optimal basic feasible solutions to linear programming problems is a critical task for mixed integer programming and other applications. The crossover method, which aims at deriving an optimal extreme point from a suboptimal solution (the output of a starting method such as interior-point methods or first-order methods), is crucial in this process. This method, compared with the starting method, frequently represents the primary computational bottleneck in practical applications. We propose approaches to overcome this bottleneck by exploiting problem characteristics and implementing customized strategies. For problems arising from network applications and exhibiting network structures, we take advantage of the graph structure of the problem and the tree structure of the optimal solutions. Based on these structures, we propose a tree-based crossover method, aiming to recovering basic solutions by identifying nearby spanning tree structures. For general linear programs, we propose recovering an optimal basic solution by identifying the optimal face and employing controlled perturbations based on the suboptimal solution provided by interior-point methods. We prove that an optimal solution for the perturbed problem is an extreme point, and its objective value is at least as good as that of the initial interior-point solution. Computational experiments show significant speed-ups achieved by our methods compared with state-of-the-art commercial solvers on classical linear programming problem benchmarks, network flow problem benchmarks, and optimal transport problems. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: D. Ge was supported by the National Natural Science Foundation of China [Grants 72150001, 72225009, 72394360, and 72394365]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0291 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0291 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

HDSDP is a numerical software solving semidefinite programming problems. The main framework of HDSDP resembles the dual-scaling interior point solver DSDP and several new features, including a dual method based on the simplified homogeneous self-dual embedding, have been implemented. The embedding technique enhances the stability of the dual method, and several new heuristics and computational techniques are designed to accelerate its convergence. HDSDP aims to show how the dual-scaling algorithm benefits from the self-dual embedding, and it is developed in parallel to DSDP 5.8. Numerical experiments over several classical benchmark datasets exhibit their robustness and efficiency, particularly their advantages on SDP instances featuring low-rank structure and sparsity. HDSDP is open sourced under an MIT license and available at https://github.com/Gwzwpxz/HDSDP .

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.

Value Iteration (VI) is one of the most classic algorithms for solving Markov Decision Processes (MDPs), which lays the foundations for various more advanced reinforcement learning algorithms, such as Q-learning. VI may take a large number of iterations to converge as it is a first-order method. In this paper, we introduce the Newton Value Iteration (NVI) algorithm, which eliminates the impact of action space dimension compared to some previous second-order methods. Consequently, NVI can efficiently handle MDPs with large action spaces. Building upon NVI, we propose a novel approach called Sketched Newton Value Iteration (SNVI) to tackle MDPs with both large state and action spaces. SNVI not only inherits the stability and fast convergence advantages of second-order algorithms, but also significantly reduces computational complexity, making it highly scalable. Extensive experiments demonstrate the superiority of our algorithms over traditional VI and previously proposed second-order VI algorithms.

In many important machine learning applications, the standard assumption of having a globally Lipschitz continuous gradient may fail to hold. This paper delves into a more general (L0, L1)-smoothness setting, which gains particular significance within the realms of deep neural networks and distributionally robust optimization (DRO). We demonstrate the significant advantage of trust region methods for stochastic nonconvex optimization under such generalized smoothness assumption. We show that first-order trust region methods can recover the normalized and clipped stochastic gradient as special cases and then provide a unified analysis to show their convergence to first-order stationary conditions. Motivated by the important application of DRO, we propose a generalized high-order smoothness condition, under which second-order trust region methods can achieve a complexity of O(epsilon(-3.5)) for convergence to second-order stationary points. By incorporating variance reduction, the second-order trust region method obtains an even better complexity of O(epsilon(-3)), matching the optimal bound for standard smooth optimization. To our best knowledge, this is the first work to show convergence beyond the first-order stationary condition for generalized smooth optimization. Preliminary experiments show that our proposed algorithms perform favorably compared with existing methods.

Gradient dominance property is a condition weaker than strong convexity, yet sufficiently ensures global convergence even in non-convex optimization. This property finds wide applications in machine learning, reinforcement learning (RL), and operations management. In this paper, we propose the stochastic homogeneous second-order descent method (SHSODM) for stochastic functions enjoying gradient dominance property based on a recently proposed homogenization approach. Theoretically, we provide its sample complexity analysis, and further present an enhanced result by incorporating variance reduction techniques. Our findings show that SHSODM matches the best-known sample complexity achieved by other second-order methods for gradient-dominated stochastic optimization but without cubic regularization. Empirically, since the homogenization approach only relies on solving extremal eigenvector problem at each iteration instead of Newton-type system, our methods gain the advantage of cheaper computational cost and robustness in ill-conditioned problems. Numerical experiments on several RL tasks demonstrate the better performance of SHSODM compared to other off-the-shelf methods.

SOLNP \(+\) is a derivative-free solver for constrained nonlinear optimization. It starts from SOLve Nonlinear Programming (SOLNP) proposed in 1989 by Ye. The main ideas are to use finite difference to approximate the gradient of the objective function and constraints, and use augmented Lagrangian method and sequential quadratic programming to deal with nonlinear constraints. We incorporate the techniques of implicit filtering, a new restart mechanism, and a modern quadratic programming solver into this new version with an ANSI C implementation. The algorithm exhibits a great advantage in running time and robustness under noise compared with the old version implemented in MATLAB. The numerical experiments show that SOLNP \(+\) is comparable with two widely used solvers, COBYLA and NOMAD. SOLNP \(+\) is available at https://github.com/COPT-Public/SOLNP_plus .

This paper presents fast first-order methods for solving linear programs (LPs) approximately. We adapt online linear programming algorithms to offline LPs and obtain algorithms that avoid any matrix multiplication. We also introduce a variable-duplication technique that copies each variable $K$ times and reduces the optimality gap and constraint violation by a factor of $\sqrt{K}$. Furthermore, we show how online algorithms can be effectively integrated into sifting, a column generation scheme for large-scale LPs. Numerical experiments demonstrate that our methods can serve as either an approximate direct solver, or an initialization subroutine for exact LP solving.

Computing the Wasserstein barycenter of a set of probability measures under the optimal transport metric can quickly become prohibitive for traditional second-order algorithms, such as interior-point methods, as the support size of the measures increases. In this paper, we overcome the difficulty by developing a new adapted interior-point method that fully exploits the problem's special matrix structure to reduce the iteration complexity and speed up the Newton procedure. Different from regularization approaches, our method achieves a well-balanced tradeoff between accuracy and speed. A numerical comparison on various distributions with existing algorithms exhibits the computational advantages of our approach. Moreover, we demonstrate the practicality of our algorithm on image benchmark problems including MNIST and Fashion-MNIST.

Consider the regularized sparse minimization problem, which involves empirical sums of loss functions for $n$ data points (each of dimension $d$) and a nonconvex sparsity penalty. We prove that finding an $\mathcal{O}(n^{c_1}d^{c_2})$-optimal solution to the regularized sparse optimization problem is strongly NP-hard for any $c_1, c_2\in [0,1)$ such that $c_1+c_2<1$. The result applies to a broad class of loss functions and sparse penalty functions. It suggests that one cannot even approximately solve the sparse optimization problem in polynomial time, unless P $=$ NP.

We propose a non-asymptotic approach to analyze kidney exchange that builds on the random graph model of kidney exchange introduced in Ashlagi, Garmarnik, Rees and Roth's "The need for (long) chains in kidney exchange" (2012). We analyze a two phase procedure where random walks are used to allocate chains, followed by allocation via matching in cycles. Random walks preserve the probabilistic structure of residual graphs, greatly facilitating analysis without sending the number of nodes to infinity. We derive useful analytical bounds that illustrate the performance of our procedure and more general kidney allocation procedures. Our results complement previous asymptotic results for large (limit) graphs on the benefits of using chains in kidney exchange and empirical results based on data from fielded kidney exchanges.

Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log/sub B/N block transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. A modified version of the van Emde Boas layout is proposed, whose expected block transfers between any two levels of the memory hierarchy arbitrarily close to [lg e + O(lg lg B/ lgB)] logB N + O(1). This factor approaches lg e /spl ap/ 1.443 as B increases. The expectation is taken over the random placement of the first element of the structure in memory. As searching in the disk access model (DAM) can be performed in log/sub B/N + 1 block transfers, this result shows a separation between the 2-level DAM and cache-oblivious memory-hierarchy models. By extending the DAM model to k levels, multilevel memory hierarchies can be modeled. It is shown that as k grows, the search costs of the optimal k-level DAM search structure and of the optimal cache-oblivious search structure rapidly converge. This demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure.

In the Freeze-Tag Problem, the objective is to awaken a set of "asleep" robots, starting with only one "awake" robot. A robot awakens a sleeping robot by moving to the sleeping robot's position. When a robot awakens, it is available to assist in awakening other slumbering robots. The objective is to compute an optimal awakening schedule/ such that all robots are awake by time t*, for the smallest possible value of t*. Because of its resemblance to the children's game of freeze-tag, this problem has been called Freeze-Tag Problem (FTP).A particularly intriguing aspect of the FTP is that any algorithm that is not purposely unproductive yields an O(log n)-approximation, while no o(log n)-approximation algorithms are known for general metric spaces.This paper presents an O(1)-approximation algorithm for the FTP in unweighted graphs, in which there is one asleep robot at each node. We show that this version of the FTP is NP-hard.We generalize our methods to the case in which there are multiple robots at each node and edges are unweighted; we obtain a θ(∗log n)-approximation in this case. In the case of weighted edges, our methods yield an O((L/d)log n)-approximation algorithm, where L is the length of the longest edge and d is the diameter of the graph.