Cutting Planes for Mixed 0-1 Semidefinite Programs
| Autor: | Garud Iyengar, Mehmet Tolga Cezik |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Semidefinite programming
Mathematical optimization Quadratic assignment problem MathematicsofComputing_GENERAL MathematicsofComputing_NUMERICALANALYSIS Mathematics::Optimization and Control Graph partition Approximation algorithm TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Combinatorial optimization Quadratic programming Interior point method Cutting-plane method MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Integer Programming and Combinatorial Optimization ISBN: 9783540422259 IPCO |
| DOI: | 10.1007/3-540-45535-3_20 |
| Popis: | Since the seminal work of Nemirovski and Nesterov [14], research on semidefinite programming (SDP) and its applications in optimization has been burgeoning. SDP has led to good relaxations for the quadratic assignment problem, graph partition, non-convex quadratic optimization problems, and the TSP. SDP-based relaxations have led to approximation algorithms for combinatorial optimization problems such as the MAXCUT and vertex coloring. SDP has also found nu- merous applications in robust control and, as a natural extension, in robust op- timization for convex programs with uncertain parameters. For a recent survey of semidefinite techniques and applications see [20]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|