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 20 of 20 for “"Lagrangian dual"”.
-
Nondifferentiable optimization algorithms with application to solving Lagrangian dual problems
… decomposition, Benders decomposition, Lagrangian duality, penalty function methods, and minimax problems. The importance and necessity of having effective solution methods for NDO problems has long been recognized by many scientists and engineers. However, the practical use of NDO …
-
Nondifferentiable Optimization of Lagrangian Dual Formulations for Linear Programs with Recovery of Primal Solutions
… linear programming (LP) problems via Lagrangian dual (LD) reformulations. A principal motivation for this work arises in the context of solving mixed-integer programming (MIP) problems where LP relaxations, sometimes in higher dimensional spaces, are widely used for bounding and …
-
Convex relaxation methods for graphical models : Lagrangian and maximum entropy approaches
… general problem is intractable, so we consider a Lagrangian relaxation (LR) approach to obtain a tractable dual problem. This involves using the Lagrangian decomposition technique to break up an intractable graph into tractable subgraphs, such as small "blocks" of nodes, embedded trees or thin …
-
Renewable energy in electric utility capacity planning: a decomposition approach with application to a Mexican utility
… first phase, two algorithms, based on a Lagrangian Dual decomposition and a Generalized Benders Decomposition, are developed. The Lagrangian Dual formulation results in a subproblem which can be separated into single-year plantmix problems that are easily solved using a breakeven …
-
A reformulation-linearization based implicit enumeration algorithm for the rectilinear distance location-allocation problem
… order to get a quick lower bound via a suitable Lagrangian dual formulation. This lower bounding scheme is embedded within a finitely convergent Branch and Bound algorithm that enumerates over the location decision variable space. An illustrative example and computational experience are provided …
-
Unit commitment : tight formulation and pricing
… of UC based on a primal formulation of the Lagrangian dual problem. This convex relaxation is used (i) to solve the convex hull pricing problem in polynomial time, providing prices with better incentives in non-convex electricity markets, and (ii) to construct a computationally efficient GEP …
-
An Optimisation-Based Approach to FKPP-Type Equations
… a second representation which can be seen as a dual problem to the first optimisation problem. We note that this is a new type of dual problem and we compare it to the standard Lagrangian dual formulation. By choosing controls in the optimisation problems we obtain upper and lower bounds on the …
-
Algorithmic Approaches for Solving the Euclidean Distance Location and Location-Allocation Problems
… differentiable formulation is derived via a Lagrangian dual approach based on the optimum of a linear function over a unit ball (circle). For this dual approach, which recovers Francis and Cabot's (1972) dual problem, we also characterize the recovery of primal location decisions, hence …
-
Recovery of primal solution in dual subgradient schemes
… we employ the subgradient method to solve the Lagrangian dual of a convex constrained problem, and use a primal-averaging scheme to obtain near-optimal and near-feasible primal solutions. We numerically evaluate the performance of the scheme in the framework of Network Utility Maximization …
-
Sequential Decision-making Under Uncertainty: Novel Methodologies and Applications
… integer decisions is difficult. We introduce Lagrangian dual decision rules (LDDRs) for MSMIP that overcome this difficulty by applying decision rules in Lagrangian duals of the MSMIP. We propose two new bounding techniques based on stagewise and nonanticipative Lagrangian duals. Our proposal …
-
Design and operation of electricity markets: dynamics, uncertainty, pricing and competition
… for obtaining a global maximizer of the Lagrangian dual problem, interpreted as the convex hull price with the potential to reduce or eliminate uplift payments, is proposed. Numerical experiments illustrate the finite-termination property and show that the performance of the algorithm …
-
A primal-dual conjugate subgradient algorithm for large- scale/specially structured linear programming problems
This dissertation deals with a primal-dual conjugate subgradient-based algorithm for solving large-scale and/or specially structured linear programming problems. The proposed algorithm coordinates a Lagrangian dual function and a primal penalty function which satisfies a flexible set of specified …
-
Enhanced intersection cutting plane and reformulation-linearization enumeration based approaches for linear complementarity problems
… developed is a composite impliCit enumeration-Lagrangian relaxation scheme. In addition to the bounds provided by the RLT-based relaxation, we further tighten these bounds at each node of the branch-and-bound tree through the use of strongest surrogate cuts, and strengthened intersection cuts. …
-
Risk-bounded Programming using Constrained, Hierarchical, Stochastic Shortest Path Problems
… planner responsible for addressing individual tasks, and RHCP, a coordinating planner that decomposes hierarchically structured tasks into individual tasks and resolves them through ACDC calls. To solve individual tasks while adhering to Zeppelin’s anytime property, ACDC employs a …
-
Network Design and Analysis Problems in Telecommunication, Location-Allocation, and Intelligent Transportation Systems
… of the proposed model. We also design efficient Lagrangian dual schemes for solving the linear programming relaxation of the various enhanced models, and construct an effective heuristic procedure for deriving good quality solutions in this process. Extensive computational results are provided to …
-
Lagrangian Relaxation / Dual Approaches For Solving Large-Scale Linear Programming Problems
… and ill-conditioning ) in comparison with a Lagrangian Relaxation approach. With this motivation, we present a practical primal-dual subgradient algorithm that incorporates a dual ascent, a primal recovery, and a penalty function approach to recover a near optimal and feasible pair of primal …
-
Tight Flow-Based Formulations for the Asymmetric Traveling Salesman Problem and Their Applications to some Scheduling Problems
… by using deflected subgradient methods on Lagrangian dual formulations. We solve the LP relaxation of our tightest formulation, ATSP6, to (near-) optimality by using a deflected subgradient algorithm with average direction strategy (SA_ADS) (see Sherali and Ulular [69]). We also use two …
-
Efficient energy management in ultra-dense wireless networks
… and linear optimization one. This, combined with Lagrangian dual decomposition, is used to create a distributed solution. After cellassociation and resource allocation phases, the proposed solution in order to further reduce power consumption performs Cell On/Off. Then, by using the computer …
-
Enhanced Formulations for Minimax and Discrete Optimization Problems with Applications to Scheduling and Routing
… Specifically, we investigate RLT-enhanced Lagrangian dual formulations for the class of minimax mixed-integer 0-1 problems in concert with deflected/conjugate subgradient algorithms. In addition, we propose two general purpose lifting mechanisms for tightening the mathematical programming …
-
Discrete Two-Stage Stochastic Mixed-Integer Programs with Applications to Airline Fleet Assignment and Workforce Planning Problems
… requires the optimization of several non-smooth Lagrangian dual problems using subgradient methods in the bounding process, which turns out to be computationally very expensive. We begin with proposing a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic …