No label defined (Q4247439)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1302172
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1302172

      Statements

      19 April 2000
      0 references
      combinatorial optimization
      0 references
      interior method
      0 references
      0 references
      0 references
      0 references
      One of the major breakthroughs of the last decades in solving large scale linear optimization problems is the interior point algorithm initiated by N. Karmarkar (published in 1984). The present paper gives an overview on how to apply this algorithm to the solution of combinatorial optimization (CO) problems. After introducing the basic principle for linear programs -- in particular in the context of network flows -- the authors describe its use in branch and bound (branch and cut) approaches. As prominent examples the quadratic assignment problem, the linear ordering problem, and the spin glass problem are covered in some depth. The paper is concluded by working out the interrelation between interior point methods and nonlinear optimization approaches to solve CO like semidefinite optimization and nonconvex potential functions. For the entire collection see [Zbl 0903.90001].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references