Improving Local Search Algorithm for Pseudo Boolean Optimization
Authors: Yujiao Zhao, Yiyuan Wang, Yi Chu, Wenbo Zhou, Shaowei Cai, Minghao Yin
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conduct experiments on a broad range of public benchmarks, including three large-scale practical application benchmarks, two benchmarks from PB competitions, an integer linear programming optimization benchmark, a crafted combinatorial benchmark, and a combinatorial optimization knapsack benchmark to compare our proposed algorithm against twelve state-of-the-art competitors... Experimental results indicate that the proposed algorithm outperforms the current state-of-the-art solvers on almost all the benchmarks, with performance that rivals the strongest commercial solver Gurobi. |
| Researcher Affiliation | Academia | YUJIAO ZHAO, School of Computer Science and Information Technology, Northeast Normal University, China YIYUAN WANG, School of Computer Science and Information Technology, Northeast Normal University, China and Key Laboratory of Applied Statistics of MOE, Northeast Normal University, China YI CHU, Institute of Software, Chinese Academy of Sciences, China WENBO ZHOU, School of Computer Science and Information Technology, Northeast Normal University, China and Key Laboratory of Applied Statistics of MOE, Northeast Normal University, China SHAOWEI CAI, Key Laboratory of System Software, Institute of Software, Chinese Academy of Sciences and School of Computer Science and Technology, University of Chinese Academy of Sciences, China MINGHAO YIN, School of Computer Science and Information Technology, Northeast Normal University, China and Key Laboratory of Applied Statistics of MOE, Northeast Normal University, China |
| Pseudocode | Yes | Algorithm 1: Deep Opt Algorithm 2: Solution Space Exploration (SSE) Algorithm 3: Pick PB Algorithm 4: Pick Obj Algorithm 5: Diversity Flip Algorithm 6: Nu PBO-Deep Opt+ |
| Open Source Code | Yes | The codes of all competitors were kindly provided by the authors and we employ the default parameters in the corresponding literature, respectively. Our code is available at https://github.com/yiyuanwang1988/Nu PBODeep Opt-plus. |
| Open Datasets | Yes | We selected all used instances from [26, 14] as well as from the recent PB competition 2024. To be specific, we considered 4146 instances obtained from three application benchmarks and five standard benchmarks: MWCB: 24 instances from the minimum-width confidence band problem [3]... WSNO: 18 instances from the wireless sensor network optimization problem [23, 24]... SAP: 21 instances from the seating arrangements problem [1]... PB2016: 1600 OPT-SMALL-INT instances from PB competition 20163. PB2024: 478 OPT-LIN instances form the the most recent PB competition 20244. MIPLIB: The 0-1 integer linear programming optimization benchmark contains 267 instances from the mixed integer programming library MIPLIB 20175. CRAFT: 955 crafted combinatorial instances are provided in the literature [39]. KNAP: The Knapsack benchmark consists of a total of 783 instances [29]. |
| Dataset Splits | No | For the application benchmarks, our proposed algorithm and the seven comparative pure local search algorithms are each run 20 times on every instance using different random seeds ranging from 1 to 20, whereas the two exact PBO solvers and the two MIP solvers are run only once per instance. For the other five standard benchmarks (i.e., PB2016, PB2024, MIPLIB, CRAFT and KNAP), following the settings of previous works [14, 34], all the algorithms are run only once on each instance. This describes how experiments are run on instances rather than dataset splits like train/test/validation. It talks about running multiple times on every instance, but not about how the instances themselves are split for training, validation, or testing. |
| Hardware Specification | Yes | All algorithms are implemented in C++ and compiled by g++ with -O3 option. All the algorithms are run on Intel Xeon Gold 6238 CPU @ 2.10GHz with 512GB RAM under Cent OS 7.9. |
| Software Dependencies | Yes | All algorithms are implemented in C++ and compiled by g++ with -O3 option... SCIP: one of the fastest non-commercial solvers for MIP. The version used is 7.0.3 [4]. Gurobi: one of the most powerful commercial MIP solvers [18]. The version used is 10.0.2. |
| Experiment Setup | Yes | Table 2. Tuned parameters of our proposed algorithm. Parameter Range Final value... Min Step {103,104,105,106,107} 106, πΏ {32,64,128,256,512} 128, Min Hard {5,10,15,20,25} 10, πΎ {0.02,0.05,0.08,0.11,0.13} 0.05, Max Hard {30,50,70,90,110} 50, πΏπππ‘ {10,30,50,70,90} 50, MAB model π {0.6,0.7,0.8,0.9,1} 0.9, π {10,20,30,40,50} 20, Num Sample {10,20,30,40,50} 20, SSE π½ {50,100,150,200,250} 100. |