Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques

A reformulation of quadratically constrained binary programs as duals of set-copositive linear optimization problems is derived using either \(\{0,1\}\)-formulations or \(\{-1,1\}\)-formulations. The latter representation allows an extension of the randomization technique by Goemans and Williamson. An application to the max-clique problem shows that the max-clique problem is equivalent to a linear program over the max-cut … Read more

Compact linearization for bilinear mixed-integer problems

We present a compact linearization for a broad class of bilinear 0-1 mixed-integer problems subject to assignment constraints. We apply the linearization to three classes of problems: quadratic assignment, multiprocessor scheduling with communication delays, and graph partitioning, and show that it yields faster solution times. Citation DEI, Politecnico di Milano, Working paper, April 2005. Article … Read more

A binary LP model to the facility layout problem

In facility layout problems, a major concern is the optimal design or remodeling of the facilities of an organization. The decision-maker’s objective is to arrange the facility in an optimal way, so that the interaction among functions (i.e. machines, inventories, persons) and places (i.e. offices, work locations, depots) is efficient. A simple pure-binary LP model … Read more