Argonne National Laboratory

Upcoming Events

BiqCrunch: Solving Binary Quadratic Problems Efficiently Using Semidefinite Optimization

Series 
LANS Informal Seminar
Presenter 
Nathan Krislock, Northern Illinois University
June 20, 2018 10:30AM to 11:30AM
Location 
Building 240, Room 1404-1405
Type 
Seminar

Abstract: BiqCrunch is a branch-and-bound solver using semidefinite optimization to compute high-quality bounds for binary quadratic problems, such as MaxCut, Max-k-Cluster, Maximum-Independent-Set, Exact Quadratic Knapsack, and the Quadratic Assignment Problem. BiqCrunch does not use an interior-point method for computing its bounds. Instead, an eigenvalue solver and a gradient-based method are used to compute tight bounds. We will discuss our bounding procedure and give an update on the new features and performance enhancements of the latest version of BiqCrunch.

This seminar will be streamed