6533b836fe1ef96bd12a1248
RESEARCH PRODUCT
Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
Jesús Sánchez-oroManuel LagunaRafael MartíAbraham Duartesubject
Discrete mathematicsGeneral Computer ScienceIterated local searchMaximum cutInduced subgraphManagement Science and Operations ResearchComplete bipartite graphCombinatoricsBQPModeling and SimulationBipartite graphBeam searchQuadratic programmingMathematicsofComputing_DISCRETEMATHEMATICSMathematicsdescription
The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in both exact (branch and bound) and heuristic (iterated local search) frameworks. We perform a number of experiments to test individual search components and also to create new benchmarks when comparing against the state of the art, which the proposed procedure outperforms.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-11-01 | Computers & Operations Research |