Linear programming (LP) is arguably the most common optimization problem encountered in practical settings. Important examples include machine learning systems optimization, resource allocation, and other decision-making scenarios. However, even with state-of-the-art (SOTA) solvers, it is extremely challenging to solve large-scale problems arising in industry settings, which could have up to billions of decision variables and require solutions within a time limit to meet business demands. This paper proposes PDAS, a Practical Distributed ADMM System to solve such problems with a variant of the Alternating Direction Method of Multipliers (ADMM) algorithm. PDAS offers user-friendly interfaces and provides near-linear speedup thanks to its high scalability and excellent performance. It also comes with a failover mechanism to ensure the stability of the iterative process. The convergence, feasibility, and optimality of PDAS have been verified on two real-world data-sets, resulting in a 10-4 average relative deviation from Gurobi. Although SOTA solvers do have advantages if only considering the solving time when tested on five small and medium-sized public data-sets, PDAS is more promising after including the modeling time. Moreover, when used to solve large-scale LP problems with up to 109 decision variables and 104 constraints in three real-world scenarios, PDAS achieves at least 2x speedups, well beyond the capabilities of SOTA.

Online allocation is a critical challenge in constrained recommendation systems, where the distribution of goods, ads, vouchers, and other content to users with limited resources needs to be managed effectively. While the existing literature has made significant progress in improving recommendation algorithms for various scenarios, less attention has been given to developing and deploying industry-scale online allocation system in an efficient manner. To address this issue, this paper introduces an integrated and efficient learning framework in constrained recommendation scenarios at Alipay. The framework has been tested through experiments, demonstrating its superiority over other state-of-the-art methods.

Assigning items to owners is a common problem found in various real-world applications, for example, audience-channel matching in marketing campaigns, borrower-lender matching in loan management, and shopper-merchant matching in e-commerce. Given an objective and multiple constraints, an assignment problem can be formulated as a constrained optimization problem. Such assignment problems are usually NP-hard [21], so when the number of items or the number of owners is large, solving for exact solutions becomes challenging. In this paper, we are interested in solving constrained assignment problems with hundreds of millions of items. Thus, with just tens of owners, the number of decision variables is at billion-scale. This scale is usually seen in the internet industry, which makes decisions for large groups of users. We relax the possible integer constraint, and formulate a general optimization problem that covers commonly seen assignment problems. Its objective function is convex. Its constraints are either linear, or convex and separable by items. We study to solve our generalized assignment problems in the Bregman Alternating Direction Method of Multipliers (BADMM) framework where we exploit Bregman divergence to transform the Augmented Lagrangian into a separable form, and solve many subproblems in parallel. The entire solution can thus be implemented using a MapReduce-style distributed computation framework. We present experiment results on both synthetic and real-world datasets to verify its accuracy and scalability.

Credit risk assessment, which aims at identifying high-risk users, plays a critical role in financial institutions. A common method is to use the greedy strategy to generate an interpretable rule set to classify all the users into high-risk or non-risk users. During each iteration, the greedy strategy utilizes a pre-defined indicator function to evaluate which rule is the best and then adds it to the rule set. However, in reality, the indicator function is designed manually and requires much domain knowledge and expert experience. Worse still, we need to design a suitable indicator for every situation, which is tedious and time-consuming work. This motivates us to propose a self-adaptive indicator that can be adapted to different situations without too much human intervention. In this paper, we see the indicator as a weighted sum of several sub-indicators. By tuning the weights, the indicator can be adapted to different situations automatically. That is, we transform this indicator selection problem into a weights tuning problem. To find the best weight of self-adaptive indicators, machine learning methods and black-box optimization are utilized. The experimental results demonstrated that our self-adaptive indicator can select a better rule set to identify more high-risk users compared to the human-defined indicator.