Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Search

Refine search

Refine search

Access:
Content type:
Publication date:
Apply   From and To filters
Subject: Show more
Journals Show more
Publishers: Show more
Societies Show more
Series: Show more
Collections: Show more

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

1 results

  • Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations

  • Alain Billionnet, Sourour Elloumi, Marie-Christine Plateau
  • Journal:
    RAIRO - Operations Research / Volume 42 / Issue 2 / April 2008
    Published online by Cambridge University Press:
    17 May 2008, pp. 103-121
    Print publication:
    April 2008

  • Many combinatorial optimization problems can be formulated asthe minimization of a 0–1 quadratic function subject to linear constraints. Inthis paper, we are interested in the exact solution of this problem through atwo-phase general scheme. The first phase consists in reformulating theinitial problem either into a compact mixed integer linear program or into a0–1 quadratic convex program. The second phase simply consists insubmitting the reformulated problem to a standard solver. The efficiency ofthis scheme strongly depends on the quality of the reformulation obtained inphase 1. We show that a good compact linear reformulation can be obtained bysolving a continuous linear relaxation of the initial problem. We also showthat a good quadratic convex reformulation can be obtained by solving asemidefinite relaxation. In both cases, the obtained reformulation profitsfrom the quality of the underlying relaxation. Hence, the proposed scheme getsaround, in a sense, the difficulty to incorporate these costly relaxations ina branch-and-bound algorithm.