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.8293481469154358
0 references
0.8200982213020325
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