Solution to the quadratic assignment problem usingsemi-Lagrangian relaxation

The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.

A novel Lagrangian relaxation level approach for scheduling steelmaking-refining-continuous casting production

A Lagrangian relaxation(LR) approach was presented which is with machine capacity relaxation and operation precedence relaxation for solving a flexible job shop(FJS) scheduling problem from the steelmaking-refining-continuous casting process. Unlike the full optimization of LR problems in traditional LR approaches, the machine capacity relaxation is optimized asymptotically, while the precedence relaxation is optimized approximately due to the NP-hard nature of its LR problem. Because the standard subgradient algorithm(SSA) cannot solve the Lagrangian dual(LD) problem within the partial optimization of LR problem, an effective deflected-conditional approximate subgradient level algorithm(DCASLA) was developed, named as Lagrangian relaxation level approach. The efficiency of the DCASLA is enhanced by a deflected-conditional epsilon-subgradient to weaken the possible zigzagging phenomena. Computational results and comparisons show that the proposed methods improve significantly the efficiency of the LR approach and the DCASLA adopting capacity relaxation strategy performs best among eight methods in terms of solution quality and running time.

Lagrangian Relaxation Method for Multiobjective Optimization Methods: Solution Approaches

This paper introduces the Lagrangian relaxation method to solve multiobjective optimization problems. It is often required to use the appropriate technique to determine the Lagrangian multipliers in the relaxation method that leads to finding the optimal solution to the problem. Our analysis aims to find a suitable technique to generate Lagrangian multipliers, and later these multipliers are used in the relaxation method to solve Multiobjective optimization problems. We propose a search-based technique to generate Lagrange multipliers. In our paper, we choose a suitable and well-known scalarization method that transforms the original multiobjective into a scalar objective optimization problem. Later, we solve this scalar objective problem using Lagrangian relaxation techniques. We use Brute force techniques to sort optimum solutions. Finally, we analyze the results, and efficient methods are recommended.

A LAGRANGIAN RELAXATION APPROACH FOR SUPPLY CHAIN PLANNING WITH ORDER/SETUP COSTS AND CAPACITY CONSTRAINTS

A heuristic approach is developed for supply chain planning modeled as multi-item multi-level capacitated lot sizing problems. The heuristic combines Lagrangian relaxation (LR) with local search. Different from existing LR approaches that relax capacity constraints and/or inventory balance constraints, our approach only relaxes the technical constraints that each 0-1 setup variable must take value 1 if its corresponding continuous variable is positive. The relaxed problem is approximately solved by using the simplex algorithm for linear programming, while Lagrange multipliers are updated by using a surrogate subgradient method that ensures the convergence of the dual problem in case of the approximate resolution of the relaxed problem. At each iteration, a feasible solution of the original problem is constructed from the solution of the relaxed problem. The feasible solution is further improved by a local search that changes the values of two setup variables at each time. By taking the advantages of a special structure of the lot-sizing problem, the local search can be implemented by using a modified simplex algorithm, which significantly reduces its computation time. Numerical experiments show that our approach can find very good solutions for problems of realistic sizes in a short computation time and is more effective than an existing commercial optimization code.

A LAGRANGIAN RELAXATION-BASED ALGORITHM FOR THE ALLOCATION OF YARD CRANES FOR YARD ACTIVITIES WITH DIFFERENT PRIORITIES

This paper proposes a mixed integer programming model for the allocation of rail mounted gantry cranes for four basic yard activities with different priorities. The model pays special attention to the typical features of this kind of gantry cranes, such as a restricted traveling range and a limited number of adjustments during loading and discharging operations. In contrast to most of the literature dealing with these four yard activities individually, this paper models them into an integrated problem, whose computational complexity is proved to be NP-hard. We are therefore motivated to develop a Lagrangian relaxation-based heuristic to solve the problem. We compare the proposed heuristic with the branch-and-bound method that uses commercial software packages. Extensive computational results show that the proposed heuristic achieves competitive solution qualities for solving the tested problems.

Matrix decomposition and Lagrangian dual method for discrete portfolio optimization under concave transaction costs

In this paper, the discrete mean-variance model is considered for portfolio selection under concave transaction costs. By using the Cholesky decomposition technique, the convariance matrix to obtain a separable mixed integer nonlinear optimization problem is decomposed. A brand-and-bound algorithm based on Lagrangian relaxation is then proposed. Computational results are reported for test problems with the data randomly generated and those from the US stock market.

Relaxation-strategy-based Modification Branch-and-Bound Algorithm for Solving a Class of Transportation-production Problems

In this paper,a new algorithm relaxation-strategy-based modification branchand-bound algorithm is developed for a type of solving the minimum cost transportationproduction problem with concave production costs.The major improvement of the proposed new method is that modification algorithm reinforces the bounding operation using a Lagrangian relaxation,which is a concave minimization but obtains a tighter bound than the usual linear programming relaxation.Some computational results are included.Computation results indicate that the algorithm can solve fairly large scale problems.

A branch-and-bound algorithm for multi-dimensional quadratic 0-1 knapsack problems

In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.

A Dynamic Job Shop Scheduling Method Based on Lagrangian Relaxation

Due to the complexity of dynamic job shop scheduling in flexible manufacturing system(FMS), many heuristic rules are still used today. A dynamic scheduling approach based on Lagrangian relaxation is proposed to improve the quality and guarantee the real time capability of dynamic scheduling. The proposed method makes use of the dynamic predictive optimal theory combined with Lagrangian relaxation to obtain a good solution that can be evaluated quantitatively. The Lagrangian multipliers introduced here are capable of describing machine predictive states and system capacity constraints. This approach can evaluate the suboptimality of the scheduling systems. It can also quickly obtain high quality feasible schedules, thus enabling Lagrangian relaxation to be better used in the dynamic scheduling of manufacturing system. The efficiency and effectiveness of this method are verified by numerical experiments.

An efficient algorithm for multi-dimensional nonlinear knapsack problems

Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.

A branch-and-bound algorithm for discrete multi-factor portfolio optimization model

In this paper, a new branch-and-bound algorithm based on the Lagrangian dual relaxation and continuous relaxation is proposed for discrete multi-factor portfolio selection model with roundlot restriction in financial optimization. This discrete portfolio model is of integer quadratic programming problems. The separable structure of the model is investigated by using Lagrangian relaxation and dual search. Computational results show that the algorithm is capable of solving real-world portfolio problems with data from US stock market and randomly generated test problems with up to 120 securities.

Grid Integration of Wind Generation Considering Remote Wind Farms:Hybrid Markovian and Interval Unit Commitment

Grid integration of wind power is essential to reduce fossil fuel usage but challenging in view of the intermittent nature of wind.Recently,we developed a hybrid Markovian and interval approach for the unit commitment and economic dispatch problem where power generation of conventional units is linked to local wind states to dampen the effects of wind uncertainties.Also,to reduce complexity,extreme and expected states are considered as interval modeling.Although this approach is effective,the fact that major wind farms are often located in remote locations and not accompanied by conventional units leads to conservative results.Furthermore,weights of extreme and expected states in the objective function are difficult to tune,resulting in significant differences between optimization and simulation costs.In this paper,each remote wind farm is paired with a conventional unit to dampen the effects of wind uncertainties without using expensive utility-scaled battery storage,and extra constraints are innovatively established to model pairing.Additionally,proper weights are derived through a novel quadratic fit of cost functions.The problem is solved by using a creative integration of our recent surrogate Lagrangian relaxation and branch-and-cut.Results demonstrate modeling accuracy,computational efficiency,and significant reduction of conservativeness of the previous approach.

An exact algorithm for optimal redundancy in a series system with multiple component choices

In this paper, an exact algorithm was proposed for optimal redundancy in a series system with multiple component choices. A reformulation of the nonseparable reliability function was approximated by a separable integer programming problem. The resulting separable nonlinear integer programming problem is used to compute upper bounds by Lagrangian relaxation and dual search. A special partition scheme was derived to reduce the duality gap in a branch-and-bound process, thus ensure the convergence of the algorithm. Computational results show that the algorithm is efficient for solving this class of reliability optimization problems.

An Approximation Algorithm for P-prize-collecting Set Cover Problem

In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.

An Easily Implementable Algorithm for Efficient Projection onto the Ordered Weighted l_(1)Norm Ball

This paper concerns with efficient projection onto the ordered weighted l_(1)norm ball,which is equivalent to the problem of finding projector onto the intersection of the monotone nonnegative cone and an affine subspace.Based on Lagrangian relaxation and secant approximation method,we propose an easily implementable yet efficient algorithm to solve the projection problem which is proved to terminate after a finite number of iterations.Furthermore,we design efficient implementations for our algorithm and compare it with a semismooth Newton(SSN)algorithm and a root-finding(Root-F)algorithm.Numerical results on a diversity of test problems show that our algorithm is superior than SSN and Root-F.

COORDINATING PRODUCTION AND RECYCLING DECISIONS WITH STOCHASTIC DEMAND AND RETUR

In this paper, the joint production and recycling problem is investigated for a hybrid manufacturing and remanufacturing system where brand-new products are produced in the manufacturing plant and recycled products are remanufactured into as-new products in the remanufacturing facility. Both the brand-new products and remanufactured products are used to satisfy customer demands. Returns of used products that are recycled from customers are assumed to be stochastic and nonlinearly price-dependent. A mathematical model is proposed to maximize the overall profit of the system through simultaneously optimizing the production and recycling decisions, subject to two capacity constraints ？ the manufacturing capacity and the remanufacturing capacity. Based on Lagrangian relaxation method, subgradient algorithm and heuristic algorithm, a solution approach is developed to solve the problem. A representative example is presented to illustrate the system, and managerial analysis indicates that the uncertainties in demand and return have much influence on the production and recycling policy. In addition, twenty randomly produced examples are solved, and computational results show that the solution approach can obtain very good solutions for all examples in reasonable time.

Efficient Location-Aware Data Placement for Data-Intensive Applications in Geo-distributed Scientific Data Centers

Recent developments in cloud computing and big data have spurred the emergence of data-intensive applications for which massive scientific datasets are stored in globally distributed scientific data centers that have a high frequency of data access by scientists worldwide. Multiple associated data items distributed in different scientific data centers may be requested for one data processing task, and data placement decisions must respect the storage capacity limits of the scientific data centers. Therefore, the optimization of data access cost in the placement of data items in globally distributed scientific data centers has become an increasingly important goal.Existing data placement approaches for geo-distributed data items are insufficient because they either cannot cope with the cost incurred by the associated data access, or they overlook storage capacity limitations, which are a very practical constraint of scientific data centers. In this paper, inspired by applications in the field of high energy physics, we propose an integer-programming-based data placement model that addresses the above challenges as a Non-deterministic Polynomial-time（NP）-hard problem. In addition we use a Lagrangian relaxation based heuristics algorithm to obtain ideal data placement solutions. Our simulation results demonstrate that our algorithm is effective and significantly reduces overall data access cost.

FROM MANUFACTURING SCHEDULING TO SUPPLY CHAIN COORDINATION:THE CONTROL OF COMPLEXITY AND UNCERTAINTY

With time-based competition and rapid technology advancements, effective manufacturingscheduling and supply chain coordination are critical to quickly respond to changing marketconditions. These problems, however, are difficult in view of inherent complexity and variousuncertainties involved. Based on a series of results by the authors, decomposition and coordination byusing Lagrangian relaxation is identified in this paper as an effective way to control complexity anduncertainty.A manufacturing scheduling problem is first formulated within the job shop context withuncertain order arrivals, processing times, due dates, and part priorities as a separable optimizationproblem. A solution methodology that combines Lagrangian relaxation, stochastic dynamicprogramming, and heuristics is developed. Method improvements to effectively solve large problemsare also highlighted. To extend manufacturing scheduling within a factory to coordinate autonomicmembers across chains of suppliers, a decentralized supply chai

A solution to unit commitment problem using invasive weed optimization algorithm

Unit commitment （UC） is one of the most important aspect of power generation in the world today. Though, there is no method to find the exact optimized solution, there exists several meta-heuristic algorithms to determine the close to exact solution. This paper proposes a novel solution to effectively determine UC and generation cost using the technique of invasive weed optimization （IWO）. The existing technique distributes the load demand among all the generating units. The method proposed here utilizes the output of UC obtained by using the Lagrangian relaxation （LR） method and calculates the required generation from only the plants that are ON discarding the OFF generator units and thereby giving a faster and more accurate response. Moreover, the results show the comparison between the LR-particle swarm optimization （PSO） and LR-IWO, and prove that the cost of generation for a 4 unit, 8 hour schedule is much less in the case of IWO when compared to PSO.

Low Power State Assignment Algorithm for FSMs Considering Peak Current Optimization

Finite state machine （FSM） plays a vital current which is drawn by state transitions can result in role in the sequential logic design. In an FSM, the high peak large voltage drop and electromigration which significantly affect circuit reliability. Several published papers show that the peak current can be reduced by post-optimization schemes or Boolean satisfiability （SAT）-based formulations. However, those methods of reducing the peak current either increase the overall power dissipation or are not efficient. This paper has proposed a low power state assignment algorithm with upper bound peak current constraints. First the peak current constraints are weighted into the objective function by Lagrangian relaxation technique with Lagrangian multipliers to penalize the violation. Second, Lagrangian sub-problems are solved by a genetic algorithm with Lagrangian multipliers updated by the subgradient optimization method. Finally, a heuristic algorithm determines the upper bound of the peak current, and achieves optimization between peak current and switching power. Experimental results of International Workshop on Logic and Synthesis （IWLS） 1993 benchmark suites show that the proposed method can achieve up to 45.27% reduction of peak current, 6.31% reduction of switching power, and significant reduction of run time compared with previously published results.