Shanwen Pu

Shanwen Pu

Auto-generated profile, based on publicly available information

Shanwen Pu

Zuse Institute Berlin Germany

Research Focus & Metrics

Academic Career Length

3Years (2024-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 June 2024 in IEEE Transactions on Pattern Analysis and Machine Intelligence
Verified
Journal Article
Closed access
RWRui Wang
Rui Wang
CZChuwen Zhang
Chuwen Zhang
SPShanwen Pu
Shanwen Pu
JGJianjun Gao
Jianjun Gao
ZWZaiwen Wen
Zaiwen Wen
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.

8 January 2025 in arXiv
Verified
Preprint
Open access
PDF file
GMGioni Mexi
Gioni Mexi
DKDominik Kamp
Dominik Kamp
YSYuji Shinano
Yuji Shinano
SPShanwen Pu
Shanwen Pu
AHAlexander Hoen
Alexander Hoen
TKThorsten Koch
Thorsten Koch
The Pseudo-Boolean problem deals with linear or polynomial constraints with integer coefficients over Boolean variables. The objective lies in optimizing a linear objective function, or finding a feasible solution, or finding a solution that satisfies as many constraints as possible. In the 2024 Pseudo-Boolean competition, solvers incorporating the SCIP framework won five out of six categories it was competing in. From a total of 1,207 instances, SCIP successfully solved 759, while its parallel version FiberSCIP solved 776. Based on the results from the competition, we further enhanced SCIP's Pseudo-Boolean capabilities. This article discusses the results and presents the winning algorithmic ideas.