Strengthened formulations for MIP problems in networks

Many real-world problems can be formulated in the framework of mixedinteger programming. This includes many problems in routing, scheduling and other fields, which affect our everyday lives, but are seemingly invisible. Solving such problems of practical size can be difficult even on very powerful computers. This makes it necessary to develop new, better formulations and methods of approaching them. This dissertation studies methods of strengthening the formulations of three problems related to networks that fall under this framework. Chapter 1 gives a short introduction into the field of mathematical optimization. Chapter 2 presents contribution to a strong extended formulation for the convex recoloring problem, which has application in analysing the phylogenetic trees. Chapter 3 proposes and studies a new hierarchy of improving path-based extended formulations for the Steiner tree problem, which has applications in computational biology and network routing and wiring. It shows that this hierarchy provides better lower bounds on the so-called integrality gaps than currently used approaches. Chapter 4 considers the optimal power flow problem with additional binary variables related to decision, whether a power plant is scheduled for operation. It uses the recent semidefinite programming relaxation approach to the problem and studies polyhedral structure of subsets of constraints related to single nodes in the network.