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 19 of 19 for “"Extended formulation"”.
-
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. …
-
OPTIMIZATION ALGORITHMS FOR THE SYMMETRIC AND ASYMMETRIC ELECTRIC TRAVELING SALESMAN PROBLEM
… versions of the problem. We propose an extended formulation for the symmetric problem and a column generation algorithm to solve it, where columns correspond to station-to-station paths. When dealing with the asymmetric version, we consider the possibility of negative cost arcs in the …
-
Facets for Continuous Multi-Mixing Set and Its Generalizations: Strong Cuts for Multi-Module Capacitated Lot-Sizing Problem
… properties. We also present a compact extended formulation for this set and an exact separation algorithm to separate over the set of all n’-step cycle inequalities for a given n’ ϵ {1; : : : ; n}. In the next step, we extend the results of the first step to the case where conditions on …
-
Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees
… problems, when the natural integer programming formulation is relaxed to a linear program, the integrality gap is O(n). Previous work on UFPT and UFPP has established that the addition of rank constraints to the linear program can be effective in some cases at reducing the integrality gap. …
-
Formulation and simulation of impact dynamics for multilayer fabrics with various weaves
… methods developed for fabric modeling. The extended formulation closely replicates the tensile load response and contact-impact dynamics of highly flexible yarns, by generalizing the kinematic model and density interpolation used in previous work. The formulation has been validated in three …
-
Mathematical Programming Models for Influence Maximization on Social Networks
… More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a …
-
SEMICLASSICAL VIBRATIONAL SPECTROSCOPY BEYOND POWER SPECTRA
… on model systems and small molecules, an extended formulation (e-SC IR) based on mode-by-mode simulations is introduced to treat larger molecular systems with improved efficiency. These developments extend semiclassical vibrational spectroscopy beyond power spectra toward a more realistic …
-
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 …
-
Hierarchical Game Theory based Control for Large Scale Multi-Agent Systems: A Hybrid Reinforcement Learning Approach
… function (PDF). However, conventional MFG formulations often lack the ability to capture diverse coordination behaviors due to their reliance on a single global PDF, leading to suboptimal performance in heterogeneous or structured systems. To enhance flexibility and coordination efficiency, …
-
Geometric modelling and shape optimisation of pharmaceutical tablets. Geometric modelling and shape optimisation of pharmaceutical tablets using partial differential equations.
… numerically. This work also presents an extended formulation of the PDE method to a higher dimensional space by increasing the number of pa-rameters responsible for describing the surface in order to generate a solid tab-let. The shape and size of the generated solid tablets can be …
-
Geometric modelling and shape optimisation of pharmaceutical tablets. Geometric modelling and shape optimisation of pharmaceutical tablets using partial differential equations.
… numerically. This work also presents an extended formulation of the PDE method to a higher dimensional space by increasing the number of pa-rameters responsible for describing the surface in order to generate a solid tab-let. The shape and size of the generated solid tablets can be …
-
Mixed integer programming approaches for nonlinear and stochastic programming
… development and analysis of small but strong extended LP/MILP formulations and approximations. In the first part of this work we develop an LP based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a lifted polyhedral relaxation of conic …
-
Algorithms for Distributionally Risk-Receptive and Robust Stochastic Integer Programs and Interdiction Problems
… solution methods based on cutting plane and reformulation techniques. We further extend these results to multi-stage stochastic disjunctive programs by introducing an extended formulation for their feasible sets. These models are demonstrated on multi-period interdiction problems for network …
-
Power Systems for Sustainability
… Switching Problem is performed. An integral extended formulation of this substructure is constructed, and a practical approach to obtain valid inequalities is proposed. These valid inequalities are used in a branch-and-bound approach improving on both default and feasibility-oriented CPLEX. …
-
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 …
-
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 …
-
Structural and aerodynamic mistuning in blade aeroelasticity
… framework of the multi-scale method has been extended to accommodate unsteady flow and grid deformation effects. The applications of the multi-scale method on aeroelasticity problems are also the first of its kind. On the other hand, the new extended formulation as well as the novel …
-
Real-time guarantees in distributed edge computing
… the latency/quality trade-off and propose an extended formulation that captures both computation and communication times. I present scheduling of computation and communication tasks as a quality optimization problem in terms of computation and communication budget assignments for systems. I …