Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/153737
Title: A SEMI-DEFINITE RELAXATION BRANCH-AND-BOUND ALGORITHM FOR BINARY INTEGER QUADRATIC PROBLEMS USING SCIPSUITE
Authors: LOH CHENG WAI MATHIAS
Keywords: BIQ, SCIP, Branch, Bound, SDPA, ADMM
Issue Date: 18-Jan-2019
Citation: LOH CHENG WAI MATHIAS (2019-01-18). A SEMI-DEFINITE RELAXATION BRANCH-AND-BOUND ALGORITHM FOR BINARY INTEGER QUADRATIC PROBLEMS USING SCIPSUITE. ScholarBank@NUS Repository.
Abstract: The Binary Quadratic Optimization Problem is a classical problem and studied in many fields. Typical applications include the 0-1 Quadratic Problem (QP), the Maximum Cut Problem (MAXCUT), k-Cluster Problem (kCluster), Maximum Independent Set Problem (MIS) as well as the Exact k-Quadratic Knapsack Problems (EkQKP). This thesis focuses on a branch-and-bound algorithm using the SCIP-SDP framework, a leading non-commercial branch-and-bound software using the SDPA solver to solve the semidefinite programming relaxation problem of each node. However, SDPA is severely limited by its capacity to solve large problems efficiently. We consider a symmetric Gauss-Seidel Alternating Direction Method of Multipliers (sGS-ADMM) solver as an alternative to better handle large problems. To speed up computation, we utilized sparse data structures and other heuristics to better handle large datasets. Our experimental results demonstrate that sGS-ADMM provides improved efficiency for large datasets. Under additional constraints, sGS-ADMM is also able to attain better results for smaller problems.
URI: https://scholarbank.nus.edu.sg/handle/10635/153737
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
LohCWM.pdf302.99 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

24
checked on Jul 10, 2020

Download(s)

3
checked on Jul 10, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.