binary

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

  • Florian Jarre
  • Felix Lieder
  • Fatameh Bani Asadi Rad
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , , , , ,

    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

  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Scheduling Tags , ,

    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

  • Christos Papahristodoulou
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Facility Planning and Design Tags , , , ,

    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