Spelling suggestions: "subject:"lagrangian relaxation"" "subject:"lagrangiana relaxation""
1 
A dualbased approach to a multiobjective location problemAbdelLateef, Bahgat AbdelHameed January 1988 (has links)
No description available.

2 
Optimal Shipping Decisions in an Airfreight Forwarding NetworkLi, Zichao January 2012 (has links)
This thesis explores three consolidation problems
derived from the daily operations of major international airfreight forwarders.
First, we study the freight forwarder's unsplittable shipment planning problem in an airfreight forwarding network where a set of cargo shipments have to be transported to given destinations. We provide mixed integer programming formulations that use piecewiselinear cargo rates and account for volume and weight constraints, flight departure/arrival times, as well as shipmentready times. After exploring the solution of such models using CPLEX, we devise two solution methodologies to handle large problem sizes. The first is based on Lagrangian relaxation, where the problems decompose into a set of knapsack problems and a set of network flow problems. The second is a local branching heuristic that combines branching ideas and local search. The two approaches show promising results in providing good quality heuristic solutions within reasonable computational times, for difficult and large shipment consolidation problems.
Second, we further explore the freight forwarder's shipment planning problem with a different type of discount structure  the systemwide discount. The forwarder's
cost associated with one flight depends not only on the quantity of freight
assigned to that flight, but also on the total freight assigned to other flights
operated by the same carrier. We propose a multicommodity flow formulation that takes shipment volume and overdeclaration into account, and solve it through a Lagrangian relaxation approach. We also model the "doublediscount" scheme that incorporates both the common flightleg discount (the one used in the unsplittable shipment problem) and the systemwide discount
offered by cargo airlines.
Finally, we focus on palletized loading using unit loading devices (ULDs) with pivots, which is different from what we assumed in the previous two research problems. In the international air cargo business, shipments are usually consolidated into containers; those are the ULDs. A ULD is charged depending on whether the total weight exceeds a certain threshold, called the pivot weight. Shipments are charged the underpivot rate up to the pivot weight. Additional weight is charged at the overpivot rate. This scheme is adopted for safety reasons to avoid the ULD overloading. We propose three solution methodologies for the aircargo consolidation problem under the pivotweight (ACPW), namely: an exact solution approach based on branchandprice, a best fit decreasing loading heuristic, and an extended local branching. We found superior computational performance with a combination of the multilevel variables and a relaxationinduced neighborhood search for local branching.

3 
Optimal Shipping Decisions in an Airfreight Forwarding NetworkLi, Zichao January 2012 (has links)
This thesis explores three consolidation problems
derived from the daily operations of major international airfreight forwarders.
First, we study the freight forwarder's unsplittable shipment planning problem in an airfreight forwarding network where a set of cargo shipments have to be transported to given destinations. We provide mixed integer programming formulations that use piecewiselinear cargo rates and account for volume and weight constraints, flight departure/arrival times, as well as shipmentready times. After exploring the solution of such models using CPLEX, we devise two solution methodologies to handle large problem sizes. The first is based on Lagrangian relaxation, where the problems decompose into a set of knapsack problems and a set of network flow problems. The second is a local branching heuristic that combines branching ideas and local search. The two approaches show promising results in providing good quality heuristic solutions within reasonable computational times, for difficult and large shipment consolidation problems.
Second, we further explore the freight forwarder's shipment planning problem with a different type of discount structure  the systemwide discount. The forwarder's
cost associated with one flight depends not only on the quantity of freight
assigned to that flight, but also on the total freight assigned to other flights
operated by the same carrier. We propose a multicommodity flow formulation that takes shipment volume and overdeclaration into account, and solve it through a Lagrangian relaxation approach. We also model the "doublediscount" scheme that incorporates both the common flightleg discount (the one used in the unsplittable shipment problem) and the systemwide discount
offered by cargo airlines.
Finally, we focus on palletized loading using unit loading devices (ULDs) with pivots, which is different from what we assumed in the previous two research problems. In the international air cargo business, shipments are usually consolidated into containers; those are the ULDs. A ULD is charged depending on whether the total weight exceeds a certain threshold, called the pivot weight. Shipments are charged the underpivot rate up to the pivot weight. Additional weight is charged at the overpivot rate. This scheme is adopted for safety reasons to avoid the ULD overloading. We propose three solution methodologies for the aircargo consolidation problem under the pivotweight (ACPW), namely: an exact solution approach based on branchandprice, a best fit decreasing loading heuristic, and an extended local branching. We found superior computational performance with a combination of the multilevel variables and a relaxationinduced neighborhood search for local branching.

4 
A Comparison of MixedInteger Programming Models for NonConvex Piecewise Linear Cost Minimization ProblemsCroxton, Keely L., Gendon, Bernard, Magnanti, Thomas L. 07 1900 (has links)
We study a generic minimization problem with separable nonconvex piecewise linear costs, showing that the linear programming (LP) relaxation of three textbook mixed integer programming formulations each approximates the cost function by its lower convex envelope. We also show a relationship between this result and classical Lagrangian duality theory.

5 
ClusteringBased Simultaneous Task and Voltage Scheduling for NoC SystemsYang, Yu 2011 May 1900 (has links)
NetworkonChip (NoC) is emerging as a promising communication structure, which is scalable with respect to chip complexity. Meanwhile, latest chip designs are increasingly leveraging multiple voltagefrequency domains for energyefficiency improvement. In this work, we propose a simultaneous task and voltage scheduling algorithm for energy minimization in NoC based designs. The energylatency tradeoff is handled by Lagrangian relaxation. The core algorithm is a clustering based approach which not only assigns voltage levels and starting time to each task (or Processing Element) but also naturally finds
voltagefrequency clusters. Compared to a recent previous work, which performs task scheduling and voltage assignment sequentially, our method leads to an average of 20 percent
energy reduction.

6 
The Multiple Retailer Inventory Routing Problem With BackordersAlisan, Onur 01 July 2008 (has links) (PDF)
In this study we consider an inventory routing problem in which a supplier distributes a single product to multiple retailers in a finite planning horizon. Retailers should satisfy the deterministic and dynamic demands of end customers in the planning horizon, but the retailers can backorder the demands of end customers considering the supply chain costs. In each period the supplier decides the retailers to be visited, and the amount of products to be supplied to each retailer by a fleet of vehicles. The decision problems of the supplier are about when, to whom and how much to deliver products, and in which order to visit retailers while minimizing systemwide costs. We propose a mixed integer programming model and a Lagrangian relaxation based solution approach in which both upper and lower bounds are computed. We test our solution approach with test instances taken from the literature and provide our computational results.

7 
Cost minimization in multi−commodity multi−mode generalized networks with time windowsChen, PingShun 25 April 2007 (has links)
The purpose of this research is to develop a heuristic algorithm to minimize total
costs in multicommodity, multimode generalized networks with time windows
problems. The proposed mathematical model incorporates features of the congestion of
vehicle flows and time restriction of delivering commodities. The heuristic algorithm,
HA, has two phases. Phase 1 provides lower and upper bounds based on Lagrangian
relaxations with subgradient methods. Phase 2 applies two methods, early due date with
overduedate costs and total transportation costs, to search for an improved upper bound.
Two application networks are used to test HA for small and mediumscale
problems. A different number of commodities and various lengths of planning time
periods are generated. Results show that HA can provide good feasible solutions within
the reasonable range of optimal solutions. If optimal solutions are unknown, the average
gap between lower and upper bounds is 0.0239. Minimal and maximal gaps are 0.0007
and 0.3330. If optimal solutions are known, the maximal gap between upper bounds and
optimal solutions is less than 10% ranges of optimal solutions.

8 
VlSI Interconnect Optimization Considering Nonuniform Metal StacksTsai, JungTai 16 December 2013 (has links)
With the advances in process technology, comes the domination of interconnect in the overall propagation delay in modern VLSI designs. Hence, interconnect synthesis techniques, such as buffer insertion, wire sizing and layer assignment play critical roles in the successful timing closure for EDA tools. In this thesis, while our aim is to satisfy timing constraints, accounting for the overhead caused by these optimization techniques is of another primary concern.
We utilized a Lagrangian relaxation method to minimize the usage of buffers and metal resources to meet the timing constraints. Compared with the previous work that extended traditional Van Ginneken’s algorithm, which allows for bumping up the wire from thin to thick given significant delay improvement, our approach achieved around 25% reduction in buffer + wire capacitance under the same timing budget.

9 
Nondifferentiable Optimization of Lagrangian Dual Formulations for Linear Programs with Recovery of Primal SolutionsLim, Churlzu 15 July 2004 (has links)
This dissertation is concerned with solving largescale, illstructured linear programming (LP) problems via Lagrangian dual (LD) reformulations. A principal motivation for this work arises in the context of solving mixedinteger programming (MIP) problems where LP relaxations, sometimes in higher dimensional spaces, are widely used for bounding and cutgeneration purposes. Often, such relaxations turn out to be largesized, illconditioned problems for which simplex as well as interior point based methods can tend to be ineffective. In contrast, Lagrangian relaxation or dual formulations, when applied in concert with suitable primal recovery strategies, have the potential for providing quick bounds as well as enabling useful branching mechanisms. However, the objective function of the Lagrangian dual is nondifferentiable, and hence, we cannot apply popular gradient or Hessianbased optimization techniques that are commonly used in differentiable optimization. Moreover, the subgradient methods that are popularly used are typically slow to converge and tend to stall while yet remote from optimality. On the other hand, more advanced methods, such as the bundle method and the space dilation method, involve additional computational and storage requirements that make them impractical for largescale applications. Furthermore, although we might derive an optimal or nearoptimal solution for LD, depending on the dualadequacy of the methodology used, a primal solution may not be available. While some algorithmically simple primal solution recovery schemes have been developed in theory to accompany Lagrangian dual optimization, their practical performance has been disappointing. Rectifying these inadequacies is a challenging task that constitutes the focal point for this dissertation. Many practical applications dealing with production planning and control, engineering design, and decisionmaking in different operational settings fall within the purview of this context and stand to gain by advances in this technology.
With this motivation, our primary interests in the present research effort are to develop effective nondifferentiable optimization (NDO) methods for solving Lagrangian duals of largesized linear programs, and to design practical primal solution recovery techniques. This contribution would then facilitate the derivation of quick bounds/cuts and branching mechanisms in the context of branchandbound/cut methodologies for solving mixedinteger programming problems.
We begin our research by adapting the Volume Algorithm (VA) of Barahona and Anbil (2000) developed at IBM as a directionfinding strategy within the variable target value method (VTVM) of Sherali et al. (2000). This adaptation makes VA resemble a deflected subgradient scheme in contrast with the bundle type interpretation afforded by the modification of VA as proposed by Bahiense et al. (2002). Although VA was originally developed in order to recover a primal optimal solution, we first present an example to demonstrate that it might indeed converge to a nonoptimal primal solution. However, under a suitable condition on the geometric moving average factor, we establish the convergence of the proposed algorithm in the dual space. A detailed computational study reveals that this approach yields a competitive procedure as compared with alternative strategies including the average direction strategy (ADS) of Sherali and Ulular (1989), a modified PolyakKelley cuttingplane strategy (PKC) designed by Sherali et al. (2001), and the modified Volume Algorithm routines RVA and BVA proposed by Bahiense et al. (2002), all embedded within the same VTVM framework. As far as CPU times are concerned, the VA strategy consumed the least computational effort for most problems to attain a nearoptimal objective value. Moreover, the VA, ADS, and PKC strategies revealed considerable savings in CPU effort over a popular commercial linear program solver, CPLEX Version 8.1, when used to derive nearoptimal solutions.
Next, we consider two variable target value methods, the Level Algorithm of BrÃ¤nnlund (1993) and VTVM, which require no prior knowledge of upper bounds on the optimal objective value while guaranteeing convergence to an optimal solution. We evaluate these two algorithms in conjunction with various directionfinding and steplength strategies such as PS, ADS, VA, and PKC. Furthermore, we generalize the PKC strategy by further modifying the cut's righthandside values and additionally performing sequential projections onto some previously generated PolyakKelley's cuttingplanes. We call this a generalized PKC (GPKC) strategy. Moreover, we point out some latent deficiencies in the two aforementioned variable target value algorithms in regard to their target value update mechanisms, and we suggest modifications in order to alleviate these shortcomings. We further explore an additional local search procedure to strengthen the performance of the algorithms. Noting that no related convergence analyses have been presented, we prove the convergence of the Level Algorithm when used in conjunction with the ADS, VA, or GPKC schemes. We also establish the convergence of VTVM when employing GPKC. Based on our computational study, the modified VTVM algorithm produced the best quality solutions when implemented with the GPKC strategy, where the latter performs sequential projections onto the four most recently generated PolyakKelley cuttingplanes as available. Also, we demonstrate that the proposed modifications and the local search technique significantly improve the overall performance. Moreover, the VTVM procedure was observed to consistently outperform the Level Algorithm as well as a popular heuristic subgradient method of Held et al. (1974) that is widely used in practice. As far as CPU times are concerned, the modified VTVM procedure in concert with the GPKC strategy revealed the best performance, providing nearoptimal solutions in about 27.84% of the effort at an average as that required by CPLEX 8.1 to produce the same quality solutions.
We next consider the Lagrangian dual of a boundedvariable equality constrained linear programming problem. We develop two novel approaches for solving this problem, which attempt to circumvent or obviate the nondifferentiability of the objective function. First, noting that the Lagrangian dual function is differentiable almost everywhere, whenever the NDO algorithm encounters a nondifferentiable point, we employ a proposed <i>perturbation technique</i> (PT) in order to detect a differentiable point in the vicinity of the current solution from which a further search can be conducted. In a second approach, called the <i>barrierLagrangian dual reformulation</i> (BLR) method, the primal problem is reformulated by constructing a barrier function for the set of bounding constraints such that an optimal solution to the original problem can be recovered by suitably adjusting the barrier parameter. However, instead of solving the barrier problem itself, we dualize the equality constraints to formulate a Lagrangian dual function, which is shown to be twice differentiable. Since differentiable pathways are made available via these two proposed techniques, we can advantageously utilize differentiable optimization methods along with popular conjugate gradient schemes. Based on these constructs, we propose an algorithmic procedure that consists of two sequential phases. In Phase I, the PT and BLR methods along with various deflected gradient strategies are utilized, and then, in Phase II, we switch to the modified VTVM algorithm in concert with GPKC (VTVMGPKC) that revealed the best performance in the previous study. We also designed two target value initialization methods to commence Phase II, based on the output from Phase I. The computational results reveal that Phase I indeed helps to significantly improve the algorithmic performance as compared with implementing VTVMGPKC alone, even though the latter was run for twice as many iterations as used in the twophase procedures. Among the implemented procedures, the PT method in concert with certain prescribed deflection and Phase II initialization schemes yielded the best overall quality solutions and CPU time performance, consuming only 3.19% of the effort as that required by CPLEX 8.1 to produce comparable solutions. Moreover, we also tested some ergodic primal recovery strategies with and without employing BLR as a warmstart, and observed that an initial BLR phase can significantly enhance the convergence of such primal recovery schemes.
Having observed that the VTVM algorithm requires the finetuning of several parameters for different classes of problems in order to improve its performance, our next research investigation focuses on developing a robust variable target value framework that entails the management of only a few parameters. We therefore design a novel algorithm, called the <i>Trust Region Target Value</i> (TRTV) method, in which a trust region is constructed in the dual space, and its center and size are adjusted in a manner that eventually induces a dual optimum to lie at the center of the hypercube trust region. A related convergence analysis has also been conducted for this procedure. We additionally examined a variation of TRTV, where the hyperrectangular trust region is more effectively adjusted for normalizing the effects of the dual variables. In our computational study, we compared the performance of TRTV with that of the VTVMGPKC procedure. For four directionfinding strategies (PS, VA, ADS, and GPKC), the TRTV algorithm consistently produced better quality solutions than did VTVMGPKC. The best performance was obtained when TRTV was employed in concert with the PS strategy. Moreover, we observed that the solution quality produced by TRTV was consistently better than that obtained via VTVM, hence lending a greater degree of robustness. As far as computational effort is concerned, the TRTVPS combination consumed only 4.94% of the CPU time required by CPLEX 8.1 at an average in order to find comparable quality solutions. Therefore, based on our extensive set of test problems, it appears that the TRTV along with the PS strategy is the best and the most robust procedure among those tested.
Finally, we explore an outerlinearization (or cuttingplane) method along with a trust region approach for refining available dual solutions and recovering a primal optimum in the process. This method enables us to escape from a jamming phenomenon experienced at a nonoptimal point, which commonly occurs when applying NDO methods, as well as to refine the available dual solution toward a dual optimum. Furthermore, we can recover a primal optimal solution when the resulting dual solution is close enough to a dual optimum, without generating a potentially excessive set of constraints. In our computational study, we tested two such trust region strategies, the Boxstep (BS) method of Marsten et al. (1975) and a new Box Trust Region (BTR) approach, both appended to the foregoing TRTVPS dual optimization methodology. Furthermore, we also experimented with deleting nonbinding constraints when the number of cuts exceeds a prescribed threshold value. This proposed refinement was able to further improve the solution quality, reducing the nearzero relative optimality gap for TRTVPS by 20.632.8%. The best strategy turned out to be using the BTR method while deleting nonbinding constraints (BTRD). As far as the recovery of optimal solutions is concerned, the BTRD scheme resulted in the best measure of primal feasibility, and although it was terminated after it had accumulated only 50 constraints, it revealed a better performance than the ergodic primal recovery scheme of Shor (1985) that was run for 2000 iterations while also assuming knowledge of the optimal objective value in the dual scheme.
In closing, we mention that there exist many optimization methods for complex systems such as communication network design, semiconductor manufacturing, and supply chain management, that have been formulated as largesized mixedinteger programs, but for which deriving even nearoptimal solutions has been elusive due to their exorbitant computational requirements. Noting that the computational effort for solving mixedinteger programs via branchandbound/cut methods strongly depends on the effectiveness with which the underlying linear programming relaxations can be solved, applying theoretically convergent and practically effective NDO methods in concert with efficient primal recovery procedures to suitable Lagrangian dual reformulations of these relaxations can significantly enhance the overall computational performance of these methods. We therefore hope that the methodologies designed and analyzed in this research effort will have a notable positive impact on analyzing such complex systems. / Ph. D.

10 
Lagrangian Relaxation / Dual Approaches For Solving LargeScale Linear Programming ProblemsMadabushi, Ananth R. 17 February 1997 (has links)
This research effort focuses on largescale linear programming problems that arise in the context of solving various problems such as discrete linear or polynomial, and continuous nonlinear, nonconvex programming problems, using linearization and branchandcut algorithms for the discrete case, and using polyhedral outerapproximation methods for the continuous case. These problems arise in various applications in production planning, locationallocation, game theory, economics, and many engineering and systems design problems. During the solution process of discrete or continuous nonconvex problems using polyhedral approaches, one has to contend with repeatedly solving largescale linear programming(LP) relaxations. Thus, it becomes imperative to employ an efficient method in solving these problems. It has been amply demonstrated that solving LP relaxations using a simplexbased algorithm, or even an interiorpoint type of procedure, can be inadequately slow ( especially in the presence of complicating constraints, dense coefficient matrices, and illconditioning ) in comparison with a Lagrangian Relaxation approach. With this motivation, we present a practical primaldual 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 and dual solutions.
The proposed primaldual approach is comprised of three stages. Stage I deals with solving the Lagrangian dual problem by using various subgradient deflection strategies such as the Modified Gradient Technique (MGT), the Average Direction Strategy (ADS), and a new direction strategy called the Modified Average Direction Strategy (MADS). In the latter, the deflection parameter is determined based on the process of projecting the unknown optimal direction onto the space spanned by the current subgradient direction and the previous direction. This projected direction approximates the desired optimal direction as closely as possible using the conjugate subgradient concept. The steplength rules implemented in this regard are the Quadratic Fit Line Search Method and a new line search method called the Directional Derivative Line Search Method in which we start with a prescribed steplength and then ascertain whether to increase or decrease the steplength value based on the righthand and lefthand derivative information available at each iteration. In the second stage of the algorithm (Stage II), a sequence of updated primal solutions is generated using some convex combinations of the Lagrangian subproblem solutions. Alternatively, a starting primal optimal solution can be obtained using the complementary slackness conditions. Depending on the extent of feasibility and optimality attained, Stage III applies a penalty function method to improve the obtained primal solution toward a near feasible and optimal solution.
We present computational experience using a set of randomly generated, structured, linear programming problems of the type that might typically arise in the context of discrete optimization. / Master of Science

Page generated in 0.6744 seconds