Zusätzliche Informationen
Das Buch | Mixed-integer semidefinite programming (MISDP) has been an active research area in recent years, with MISDP formulations appearing in many different applications and often being tackled by problem-specific solution approaches. On the contrary, there is still a severe lack in both theory and software implementations for general mixed-integer semidefinite programming. This thesis covers both issues, in particular discussing the retainment of strong duality and corresponding constraint qualifications in semidefinite programming (SDP) relaxations after variable branchings. Since these are requirements for the convergence proofs of interior-point solvers, which will be used to tackle the subproblems, these are also necessary for the correctness of an SDP-based branch-and-bound algorithm. On the implementational side, many different improvements that are implemented in the MISDP solver SCIP-SDP are introduced. In particular, the generation of cutting planes, a propagation technique based on conic duality, warmst-arting techniques for interior-point SDP-solvers and special cuts for SDP knapsacks, which are MISDPs with all constraint matrices being positive semidefinite, are discussed. Finally, numerical results for multiple applications, in particular robust truss topology design, are present ed, showing that SCIP-SDP is currently one of the fastest solvers for mixed-integer semidefinite programming. |
---|