Optimization Online


A Penalized Quadratic Convex Reformulation Method for Random Quadratic Unconstrained Binary Optimization

Karthik Natarajan(natarajan_karthik***at***sutd.edu.sg)
Dongjian Shi(shidongjian***at***nus.edu.sg)
Kim Chuan Toh(mattohkc***at***nus.edu.sg)

Abstract: The Quadratic Convex Reformulation (QCR) method is used to solve quadratic unconstrained binary optimization problems. In this method, the semidefinite relaxation is used to reformulate it to a convex binary quadratic program which is solved using mixed integer quadratic programming solvers. We extend this method to random quadratic unconstrained binary optimization problems. We develop a Penalized QCR method where the objective function in the semidefinite program is penalized with a separable term to account for the randomness in the objective.

Keywords: quadratic unconstrained binary optimization, penalized quadratic convex reformulation, semidefinite relaxation

Category 1: Integer Programming (0-1 Programming )

Category 2: Global Optimization (Stochastic Approaches )


Download: [PDF]

Entry Submitted: 06/14/2013
Entry Accepted: 06/15/2013
Entry Last Modified: 06/14/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society