Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 16 of 16 for “"Extended formulations"”.
-
The Complexity of Extended Formulations
… theory, operations research, and algorithms. Extended formulations give a powerful approach to solve combinatorial optimization problems: if one can find a concise geometric description of the possible solutions to a problem then one can use convex optimization to solve the problem quickly. …
-
LP and SDP extended formulations: Lower bounds and approximation algorithms
In this thesis we study various aspects of linear and semidefinite programs including their limitations in approximating various combinatorial optimization problems as well as applications of these paradigms in solving problems in machine learning. In the first part we show inapproximability …
-
Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees
… exponentially many facets or be described as an extended formulation (i.e., described in a higher dimensional space). We are interested in polynomially sized formulations, so we focus our study on extended formulations. Our first contribution is a greedy algorithm which finds an optimal solution …
-
A reduction framework for approximate extended formulations and a faster algorithm for convex optimization
… linear and semidefinite programming formulations of combinatorial optimization problems. The hardness of (approximate) linear optimization implied by these lower bounds motivates the lazification technique for conditional gradient type algorithms. This technique allows us to replace …
-
Lower Bounds for Interactive Compression and Linear Programs
… variables. Such linear programs are known as extended formulations or higher dimensional lifts. They also capture the best known algorithms for many combinatorial optimization problems, as well as the LP hierarchies (Sherali-Adams, Lovasz-Schrijver). In recent years, strong lower bounds have …
-
Parameterized Approaches for Large-Scale Optimization Problems
… we provide fixed-parameter tractable extended formulations for independent set in tree-like graphs and for cardinality-constrained vertex covers.
-
The Positive Semidefinite Rank of Matrices and Polytopes
The positive semidefinite (psd) rank of a nonnegative <italic>p</italic> × <italic>q</italic> matrix <italic>M</italic> is defined to be the smallest integer <italic>k</italic> such that there exist <italic>k</italic> × <italic>k</italic> psd matrices <italic>A</italic><sub>1</sub>,…, …
-
Limitations of linear programming as a model of approximate computation
… receiving renewed attention through the model of Extended Formulations.In this model we are concerned whether there are compact formulations or approximaterelaxations for combinatorial optimization problems, allowing the use of any set or typeof variables. The model of Extended Formulations is …
-
Global optimization methods for optimal power flow and transmission switching problems in electric power systems
… conic relaxations, envelopes, disjunctive extended formulations, cutting planes, variable bound tightening techniques and feasibility heuristics. Our approaches scale well to large power systems problems and provide provably good solutions in time compatible with the needs of the system …
-
Integer programming approaches for semicontinuous and stochastic optimization
… convex hull in terms of linear inequalities and extended formulations. We also consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed …
-
A study of power system economic operation
… of assuming a specified water usage, is extended to include operating range bounds and unit commitment aspects. Pontryagin's maximum principle is found to be useful in obtaining suitable solutions to the extended formulations. For the above dynamic type short-range hydro-thermal problems …
-
An investigation into OR techniques for conference scheduling problems
… and solving methods. In chapter 6, we present extended formulations of mathematical models to handle constraints that need to be resolved on time slot level. Lastly, we compare the performance of all developed methods by solving all available instances and highlight the benefits and limitations …
-
Communication Lower Bounds via Query Complexity
… graph whose independent set polytope requires extended formulations of size exponential in Omega(n/log n). Previously, no explicit examples of n-dimensional 0/1-polytopes were known with extension complexity larger than exponential in Theta(sqrt(n)).
-
Almost Symmetries and the Unit Commitment Problem
… known correspondence between integer programming formulations and graphs, this is a first step toward detecting almost symmetries in integer programming formulations. Though we are only able to compute almost symmetries for graphs of modest size, the results indicate that almost symmetry is …
-
Exploring Structure and Reformulations in Different Integer Programming Algorithms
… four topics all related to using problem reformulations in order to solve integer programs, i.e. optimization problems in which the decision variables must be integer. We first consider the polyhedral approach. We start by addressing the ques- tion of lifting valid inequalities, i.e. finding …
-
Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems
… for combinatorial optimization problems involve formulations that make use of Systems of Linear Equations, Linear Programs (LPs), Semidefinite Programs (SDPs), and more generally, Conic and Semi-algebraic Programs. Although, generality often implies flexibility and power in the formulations, in …