A network approach for specially structured linear programs arising in 0-1 quadratic optimization |
| |
Authors: | Warren P Adams |
| |
Institution: | a Department of Mathematical Sciences, Clemson University, Clemson, SC, USA b Department of Mathematics, Armstrong Atlantic State University, Savannah, GA, USA |
| |
Abstract: | Reformulation techniques are commonly used to transform 0-1 quadratic problems into equivalent, mixed 0-1 linear programs. A classical strategy is to replace each quadratic term with a continuous variable and to enforce, for each such product, four linear inequalities that ensure the continuous variable equals the associated product. By employing a transformation of variables, we show how such inequalities give rise to a network structure, so that the continuous relaxations can be readily solved. This work unifies and extends related results for the vertex packing problem and relatives, and roof duality. |
| |
Keywords: | Binary optimization Quadratic programming Linearization and network reformulations |
本文献已被 ScienceDirect 等数据库收录! |
|