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"”.

  1. 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. …

    gatech Repository record for The Complexity of Extended Formulations (opens in a new tab)

  2. 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 …

    gatech Repository record for LP and SDP extended formulations: Lower bounds and approximation algorithms (opens in a new tab)

  3. 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 …

    ubc Repository record for Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees (opens in a new tab) Download PDF for Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees (opens in a new tab)

  4. 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 …

    gatech Repository record for A reduction framework for approximate extended formulations and a faster algorithm for convex optimization (opens in a new tab)

  5. 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 …

    washington Repository record for Lower Bounds for Interactive Compression and Linear Programs (opens in a new tab)

  6. 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.

    tamu Repository record for Parameterized Approaches for Large-Scale Optimization Problems (opens in a new tab)

  7. 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>,…, …

    washington Repository record for The Positive Semidefinite Rank of Matrices and Polytopes (opens in a new tab)

  8. 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 …

    greece Repository record for Limitations of linear programming as a model of approximate computation (opens in a new tab)

  9. 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 …

    gatech Repository record for Global optimization methods for optimal power flow and transmission switching problems in electric power systems (opens in a new tab)

  10. 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 …

    gatech Repository record for Integer programming approaches for semicontinuous and stochastic optimization (opens in a new tab)

  11. 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 …

    ubc Repository record for A study of power system economic operation (opens in a new tab) Download PDF for A study of power system economic operation (opens in a new tab)

  12. 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 …

    lancaster Download PDF for An investigation into OR techniques for conference scheduling problems (opens in a new tab)

  13. 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)).

    toronto-retro Repository record for Communication Lower Bounds via Query Complexity (opens in a new tab)

  14. 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 …

    utk-theses Repository record for Almost Symmetries and the Unit Commitment Problem (opens in a new tab)

  15. 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 …

    liege Repository record for Exploring Structure and Reformulations in Different Integer Programming Algorithms (opens in a new tab) Download PDF for Exploring Structure and Reformulations in Different Integer Programming Algorithms (opens in a new tab)

  16. 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 …

    waterloo Repository record for Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems (opens in a new tab)