Author name cluster

Chuan Luo 0002

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

ICLR Conference 2022 Conference Paper

Automatic Loss Function Search for Predict-Then-Optimize Problems with Strong Ranking Property

Boshi Wang
Jialin Yi
Hang Dong 0004
Bo Qiao 0001
Chuan Luo 0002
Qingwei Lin

Combinatorial optimization problems with parameters to be predicted from side information are commonly seen in a variety of problems during the paradigm shift from reactive decision making to proactive decision making. Due to the misalignment between the continuous prediction results and the discrete decisions in optimization problems, it is hard to achieve a satisfactory prediction result with the ordinary $l_2$ loss in the prediction phase. To properly connect the prediction loss with the optimization goal, in this paper we propose a total group preorder (TGP) loss and its differential version called approximated total group preorder (ATGP) loss for predict-then-optimize (PTO) problems with strong ranking property. These new losses are provably more robust than the usual $l_2$ loss in a linear regression setting and have great potential to extend to other settings. We also propose an automatic searching algorithm that adapts the ATGP loss to PTO problems with different combinatorial structures. Extensive experiments on the ranking problem, the knapsack problem, and the shortest path problem have demonstrated that our proposed method can achieve a significant performance compared to the other methods designed for PTO problems.

Details

SAT Conference 2021 Conference Paper

Efficient Local Search for Pseudo Boolean Optimization

Zhendong Lei
Shaowei Cai 0001
Chuan Luo 0002
Holger H. Hoos

Abstract Pseudo-Boolean Optimization (PBO) can be used to model many combinatorial optimization problems. PBO instances encoded from real-world applications are often large and difficult to solve; in many cases, close-to-optimal solutions are useful and can be found reasonably efficiently, using incomplete algorithms. Interestingly, local search algorithms, which are known to be effective for solving many other combinatorial optimization problems, have been rarely considered in the context of PBO. In this paper, we are introducing a new and surprisingly effective local search algorithm, LS-PBO, for PBO. LS-PBO adopts a well designed weighting scheme and a new scoring function. We compare LS-PBO with previous PBO solvers and with solvers for related problems, including MaxSAT, Extended CNF and Integer Linear Programming (ILP). We report results on three real-world application benchmarks, from the Minimum-Width Confidence Band, Wireless Sensor Network Optimization and Seating Arrangement Problems, as well as on benchmarks from the most recent PB Competition. These results demonstrate that our LS-PBO algorithm achieves much better performance than previous state-of-the-art solvers on real-world benchmarks.

Details

SAT Conference 2015 Conference Paper

CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability

Shaowei Cai 0001
Chuan Luo 0002
Kaile Su

Abstract This paper presents a stochastic local search (SLS) solver for SAT named CCAnr, which is based on the configuration checking strategy and has good performance on non-random SAT instances. CCAnr switches between two modes: it flips a variable according to the CCA (configuration checking with aspiration) heuristic if any; otherwise, it flips a variable in a random unsatisfied clause (which we refer to as the focused local search mode). The main novelty of CCAnr lies on the greedy heuristic in the focused local search mode, which contributes significantly to its good performance on structured instances. Previous two-mode SLS algorithms usually utilize diversifying heuristics such as age or randomized strategies to pick a variable from the unsatisfied clause. Our experiments on combinatorial and application benchmarks from SAT Competition 2014 show that CCAnr has better performance than other state-of-the-art SLS solvers on structured instances, and its performance can be further improved by using a preprocessor CP3. Our results suggest that a greedy heuristic in the focused local search mode might be helpful to improve SLS solvers for solving structured SAT instances.

Details

ECAI Conference 2012 Conference Paper

Improving Local Search for Random 3-SAT Using Quantitative Configuration Checking

Chuan Luo 0002
Kaile Su
Shaowei Cai 0001

Configuration Checking (CC) was proposed as a new diversification strategy for Stochastic Local Search (SLS) algorithm for solving Minimum Vertex Cover, and has been successfully used for solving the Boolean Satisfiability problems, leading to an SLS algorithm called Swcc. However, the CC strategy for SAT is in the early stage of study, and Swcc cannot compete with the best SLS solvers for SAT in SAT Competition 2011. This paper presents a new strategy called Quantitative Configuration Checking (QCC), which is a quantitative version of the CC strategy for SAT. QCC is based on a new definition of "configuration" and works in a different way from the CC strategy does. Specifically, while previous CC strategies work only in the greedy mode, QCC firstly works in the random mode. We use QCC to improve the Swcc algorithm, resulting in a new SLS algorithm for SAT called Swqcc. Experimental results show that the QCC strategy is more effective than the CC strategy. Furthermore, Swqcc outperforms the best local search SAT solver in SAT Competition 2011 called Sparrow2011 on random 3-SAT instances.

Details