Journal articles: 'Lagrangian relaxation bounds'

1

Berezovskyi, Oleg. "Improving Lagrange Dual Bounds for Quadratic Extremal Problems." Cybernetics and Computer Technologies, no. 1 (March 31, 2020): 15–22. http://dx.doi.org/10.34229/2707-451x.20.1.2.

Full text

Abstract:

Introduction. Due to the fact that quadratic extremal problems are generally NP-hard, various convex relaxations to find bounds for their global extrema are used, namely, Lagrangian relaxation, SDP-relaxation, SOCP-relaxation, LP-relaxation, and others. This article investigates a dual bound that results from the Lagrangian relaxation of all constraints of quadratic extremal problem. The main issue when using this approach for solving quadratic extremal problems is the quality of the obtained bounds (the magnitude of the duality gap) and the possibility to improve them. While for quadratic convex optimization problems such bounds are exact, in other cases this issue is rather complicated. In non-convex cases, to improve the dual bounds (to reduce the duality gap) the techniques, based on ambiguity of the problem formulation, can be used. The most common of these techniques is an extension of the original quadratic formulation of the problem by introducing the so-called functionally superfluous constraints (additional constraints that result from available constraints). The ways to construct such constraints can be general in nature or they can use specific features of the concrete problems. The purpose of the article is to propose methods for improving the Lagrange dual bounds for quadratic extremal problems by using technique of functionally superfluous constraints; to present examples of constructing such constraints. Results. The general concept of using functionally superfluous constraints for improving the Lagrange dual bounds for quadratic extremal problems is considered. Methods of constructing such constraints are presented. In particular, the method proposed by N.Z. Shor for constructing functionally superfluous constraints for quadratic problems of general form is presented in generalized and schematized forms. Also it is pointed out that other special techniques, which employ the features of specific problems for constructing functionally superfluous constraints, can be used. Conclusions. In order to improve dual bounds for quadratic extremal problems, one can use various families of functionally superfluous constraints, both of general and specific type. In some cases, their application can improve bounds or even provide an opportunity to obtain exact values of global extrema.

APA, Harvard, Vancouver, ISO, and other styles

2

Dolatabadi, Mohammad, Andrea Lodi, and Zahra Afsharnejad. "Improving spectral bounds for clustering problems by Lagrangian relaxation." International Transactions in Operational Research 18, no. 6 (August 30, 2011): 647–61. http://dx.doi.org/10.1111/j.1475-3995.2011.00825.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Brown, Nathanael, Bryan Arguello, Linda Nozick, and Ningxiong Xu. "A Heuristic Approach to Satellite Range Scheduling With Bounds Using Lagrangian Relaxation." IEEE Systems Journal 12, no. 4 (December 2018): 3828–36. http://dx.doi.org/10.1109/jsyst.2018.2821094.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Mirzaian, Andranik. "Lagrangian relaxation for the star-star concentrator location problem: Approximation algorithm and bounds." Networks 15, no. 1 (1985): 1–20. http://dx.doi.org/10.1002/net.3230150102.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Brown, David B., and James E. Smith. "Index Policies and Performance Bounds for Dynamic Selection Problems." Management Science 66, no. 7 (July 2020): 3029–50. http://dx.doi.org/10.1287/mnsc.2019.3342.

Full text

Abstract:

We consider dynamic selection problems, where a decision maker repeatedly selects a set of items from a larger collection of available items. A classic example is the dynamic assortment problem with demand learning, where a retailer chooses items to offer for sale subject to a display space constraint. The retailer may adjust the assortment over time in response to the observed demand. These dynamic selection problems are naturally formulated as stochastic dynamic programs (DPs) but are difficult to solve because the optimal selection decisions depend on the states of all items. In this paper, we study heuristic policies for dynamic selection problems and provide upper bounds on the performance of an optimal policy that can be used to assess the performance of a heuristic policy. The policies and bounds that we consider are based on a Lagrangian relaxation of the DP that relaxes the constraint limiting the number of items that may be selected. We characterize the performance of the Lagrangian index policy and bound and show that, under mild conditions, these policies and bounds are asymptotically optimal for problems with many items; mixed policies and tiebreaking play an essential role in the analysis of these index policies and can have a surprising impact on performance. We demonstrate these policies and bounds in two large scale examples: a dynamic assortment problem with demand learning and an applicant screening problem. This paper was accepted by Yinyu Ye, optimization.

APA, Harvard, Vancouver, ISO, and other styles

6

Bomze, Immanuel M. "Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems." SIAM Journal on Optimization 25, no. 3 (January 2015): 1249–75. http://dx.doi.org/10.1137/140987997.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Hosseinian, Seyedmohammadhossein, Dalila B. M. M. Fontes, and Sergiy Butenko. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem." INFORMS Journal on Computing 32, no. 3 (July 2020): 747–62. http://dx.doi.org/10.1287/ijoc.2019.0898.

Full text

Abstract:

This paper explores the connections between the classical maximum clique problem and its edge-weighted generalization, the maximum edge weight clique (MEWC) problem. As a result, a new analytic upper bound on the clique number of a graph is obtained and an exact algorithm for solving the MEWC problem is developed. The bound on the clique number is derived using a Lagrangian relaxation of an integer (linear) programming formulation of the MEWC problem. Furthermore, coloring-based bounds on the clique number are used in a novel upper-bounding scheme for the MEWC problem. This scheme is employed within a combinatorial branch-and-bound framework, yielding an exact algorithm for the MEWC problem. Results of computational experiments demonstrate a superior performance of the proposed algorithm compared with existing approaches.

APA, Harvard, Vancouver, ISO, and other styles

8

Mellouli, Racem, Imed Kacem, Chérif Sadfi, and Chengbin Chu. "Lagrangian relaxation and column generation-based lower bounds for the Pm,hj1‖∑wiCi scheduling problem." Applied Mathematics and Computation 219, no. 22 (July 2013): 10783–805. http://dx.doi.org/10.1016/j.amc.2013.05.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Lv, Xiaofeng, Deyun Zhou, Ling Ma, Yuyuan Zhang, and Yongchuan Tang. "An Improved Lagrange Particle Swarm Optimization Algorithm and Its Application in Multiple Fault Diagnosis." Shock and Vibration 2020 (June 27, 2020): 1–8. http://dx.doi.org/10.1155/2020/1091548.

Full text

Abstract:

The fault rate in equipment increases significantly along with the service life of the equipment, especially for multiple fault. Typically, the Bayesian theory is used to construct the model of faults, and intelligent algorithm is used to solve the model. Lagrangian relaxation algorithm can be adopted to solve multiple fault diagnosis models. But the mathematical derivation process may be complex, while the updating method for Lagrangian multiplier is limited and it may fall into a local optimal solution. The particle swarm optimization (PSO) algorithm is a global search algorithm. In this paper, an improved Lagrange-particle swarm optimization algorithm is proposed. The updating of the Lagrangian multipliers is with the PSO algorithm for global searching. The difference between the upper and lower bounds is proposed to construct the fitness function of PSO. The multiple fault diagnosis model can be solved by the improved Lagrange-particle swarm optimization algorithm. Experiment on a case study of sensor data-based multiple fault diagnosis verifies the effectiveness and robustness of the proposed method.

APA, Harvard, Vancouver, ISO, and other styles

10

Kim, Sunyoung, Masakazu Kojima, and Kim-Chuan Toh. "A Lagrangian–DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems." Mathematical Programming 156, no. 1-2 (February 21, 2015): 161–87. http://dx.doi.org/10.1007/s10107-015-0874-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Lin, Frank Yeong-Sung, Chiu-Han Hsiao, Kuo-Chung Chu, and Yi-Heng Liu. "Minimum-Cost QoS-Constrained Deployment and Routing Policies for Wireless Relay Networks." Journal of Applied Mathematics 2013 (2013): 1–19. http://dx.doi.org/10.1155/2013/517846.

Full text

Abstract:

With the continued evolution of wireless communication technology, relaying is one of the features proposed for the 4G LTE Advanced (LTE-A) system. The aim of relaying is to enhance both coverage and capacity. The idea of relays is not new, but relaying is being considered to ensure that the optimum performance is achieved to enable the expectations or good quality of service (QoS) of the users to be met while still keeping capital expenditure (CAPEX) within the budgeted bounds of operators. In this paper, we try to stand for an operator to propose a solution that determines where and how many relays should be deployed in the planning stages to minimize the development cost. In the planning stages, we not only derive a multicast tree routing algorithm to both determine and fulfill the QoS requirements to enhance throughput, but we also utilize the Lagrangian relaxation (LR) method in conjunction with optimization-based heuristics and conduct computational experiments to evaluate the performance. Our contribution is utilizing the LR method to propose an optimal solution to minimize the CAPEX of operators to build up a relay network with more efficiency and effectiveness and the QoS can be guaranteed by service level agreement.

APA, Harvard, Vancouver, ISO, and other styles

12

Ribeiro, Glaydston Mattos, and Luiz Antonio Nogueira Lorena. "Lagrangean relaxation bounds for point-feature cartographic label placement problem." Pesquisa Operacional 26, no. 3 (December 2006): 459–71. http://dx.doi.org/10.1590/s0101-74382006000300002.

Full text

Abstract:

The objective of the point-feature cartographic label placement problem (PFCLP) is to give more legibility to an automatic map creation, placing point labels in clear positions. Many researchers consider distinct approaches for PFCLP, such as to obtain the maximum number of labeled points that can be placed without overlapping or to obtain the maximum number of labeled points without overlaps considering that all points must be labeled. This paper considers another variant of the problem in which one has to minimize the number of overlaps while all points are labeled in the map. A conflict graph is initially defined and a mathematical formulation of binary integer linear programming is presented. Commercial optimization packages could not solve large instances exactly using this formulation over instances proposed in the literature. A heuristic is then examined considering a Lagrangean relaxation performed after an initial partition of the conflict graph into clusters. This decomposition allowed us to introduce tight lower and upper bounds for PFCLP.

APA, Harvard, Vancouver, ISO, and other styles

13

Ayala, Maria, Christian Artigues, and Bernat Gacias. "Lagrangian relaxation-based lower bound for resource-constrained modulo scheduling." Electronic Notes in Discrete Mathematics 36 (August 2010): 191–98. http://dx.doi.org/10.1016/j.endm.2010.05.025.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Litvinchev, Igor, and Edith L. Ozuna. "Lagrangian Bounds and a Heuristic for the Two-Stage Capacitated Facility Location Problem." International Journal of Energy Optimization and Engineering 1, no. 1 (January 2012): 59–71. http://dx.doi.org/10.4018/ijeoe.2012010104.

Full text

Abstract:

In the two-stage capacitated facility location problem, a single product is produced at some plants in order to satisfy customer demands. The product is transported from these plants to some depots and then to the customers. The capacities of the plants and depots are limited. The aim is to select cost minimizing locations from a set of potential plants and depots. This cost includes fixed cost associated with opening plants and depots, and variable cost associated with both transportation stages. In this work, two different mixed integer linear programming formulations are considered for the problem. Several Lagrangian relaxations are analyzed and compared, and a Lagrangian heuristic producing feasible solutions is presented. The results of a computational study are reported.

APA, Harvard, Vancouver, ISO, and other styles

15

Smith, T. H. C., T. W. S. Meyer, and G. L. Thompson. "Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations." Discrete Applied Mathematics 26, no. 2-3 (March 1990): 209–17. http://dx.doi.org/10.1016/0166-218x(90)90101-h.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Fabri, Marcelus, Helena Ramalhinho, Mauricio C. de Souza, and Martin G. Ravetti. "The Lagrangean Relaxation for the Flow Shop Scheduling Problem with Precedence Constraints, Release Dates and Delivery Times." Journal of Advanced Transportation 2019 (December 23, 2019): 1–10. http://dx.doi.org/10.1155/2019/3176074.

Full text

Abstract:

This work aims to present a methodology to support a company in the automotive business on scheduling the jobs on its final processes. These processes are: (i) checking the final product and (ii) loading the dispatch trucks. These activities are usually found in the outbound area of any manufacturing company. The problem faced is defined as the flow shop problem with precedence constraints, release dates, and delivery times. The major objective is to minimize the latest date a client receives its products. We present a time-indexed integer mathematical model to compute feasible solutions for the presented problem. Moreover, we take advantage of the Lagrangean Relaxation procedure to compute valid lower and upper bounds. The experiments were held based on the company’s premises. As a conclusion, the results showed that the methodology proposed was able to compute feasible solutions for all the instances tested. Also, the Lagrangean Relaxation approach was able to calculate better bounds in a shorter computational time than the Mathematical problem for the more complicated instances.

APA, Harvard, Vancouver, ISO, and other styles

17

Bornstein, Claudio Thomas, and Manoel Campêlo. "An ADD/DROP procedure for the capacitated plant location problem." Pesquisa Operacional 24, no. 1 (April 2004): 151–62. http://dx.doi.org/10.1590/s0101-74382004000100008.

Full text

Abstract:

The capacitated plant location problem with linear transportation costs is considered. Exact rules and heuristics are presented for opening or closing of facilities. A heuristic algorithm based on ADD/DROP strategies is proposed. Procedures are implemented with the help of lower and upper bounds using Lagrangean relaxation. Computational results are presented and comparisons with other algorithms are made.

APA, Harvard, Vancouver, ISO, and other styles

18

Litvinchev, I., M. Mata, and J. Rangel. "Calculating the best dual bound for problems with multiple Lagrangian relaxations." Journal of Computer and Systems Sciences International 49, no. 6 (December 2010): 915–22. http://dx.doi.org/10.1134/s1064230710060109.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Li, Minghuang, and Fusheng Yu. "Semidefinite Programming-Based Method for Implementing Linear Fitting to Interval-Valued Data." International Journal of Fuzzy System Applications 1, no. 3 (July 2011): 32–46. http://dx.doi.org/10.4018/ijfsa.2011070103.

Full text

Abstract:

Building a linear fitting model for a given interval-valued data set is challenging since the minimization of the residue function leads to a huge combinatorial problem. To overcome such a difficulty, this article proposes a new semidefinite programming-based method for implementing linear fitting to interval-valued data. First, the fitting model is cast to a problem of quadratically constrained quadratic programming (QCQP), and then two formulae are derived to develop the lower bound on the optimal value of the nonconvex QCQP by semidefinite relaxation and Lagrangian relaxation. In many cases, this method can solve the fitting problem by giving the exact optimal solution. Even though the lower bound is not the optimal value, it is still a good approximation of the global optimal solution. Experimental studies on different fitting problems of different scales demonstrate the good performance and stability of our method. Furthermore, the proposed method performs very well in solving relatively large-scale interval-fitting problems.

APA, Harvard, Vancouver, ISO, and other styles

20

Shi, Jianmai, and Yiping Bao. "Multiproduct Multiperiod Newsvendor Problem with Dynamic Market Efforts." Discrete Dynamics in Nature and Society 2016 (2016): 1–10. http://dx.doi.org/10.1155/2016/7674027.

Full text

Abstract:

We study a multiperiod multiproduct production planning problem where the production capacity and the marketing effort on demand are both considered. The accumulative impact of marketing effort on demand is captured by the Nerlove and Arrow (N-A) advertising model. The problem is formulated as a discrete-time, finite-horizon dynamic optimization problem, which can be viewed as an extension to the classic newsvendor problem by integrating with the N-A model. A Lagrangian relaxation based solution approach is developed to solve the problem, in which the subgradient algorithm is used to find an upper bound of the solution and a feasibility heuristic algorithm is proposed to search for a feasible lower bound. Twelve kinds of instances with different problem size involving up to 50 products and 15 planning periods are randomly generated and used to test the Lagrangian heuristic algorithm. Computational results show that the proposed approach can obtain near optimal solutions for all the instances in very short CPU time, which is less than 90 seconds even for the largest instance.

APA, Harvard, Vancouver, ISO, and other styles

21

Alenezy, Eiman J. "Solving Capacitated Facility Location Problem Using Lagrangian Decomposition and Volume Algorithm." Advances in Operations Research 2020 (February 4, 2020): 1–7. http://dx.doi.org/10.1155/2020/5239176.

Full text

Abstract:

In this research, we will focus on one variant of the problem: the capacitated facility location problem (CFLP). In many formulations of the CFLP, it is assumed that each demand point can be supplied by only one open facility, which is the simplest case of the problem. We consider the case where each demand point can be supplied by more than one open facility. We first investigate a Lagrangian relaxation approach. Then, we illustrate in the problem decomposition how to introduce tighter constraints, which solve the CFLP faster while achieving a better quality solution as well. At the same time, we apply the volume algorithm to improve both the lower and the upper bound on the optimum solution of the original problem for the large problem size.

APA, Harvard, Vancouver, ISO, and other styles

22

Hasan, M. Babul, and Md Toha. "An Improved Subgradiend Optimization Technique for Solving IPs with Lagrangean Relaxation." Dhaka University Journal of Science 61, no. 2 (November 18, 2013): 135–40. http://dx.doi.org/10.3329/dujs.v61i2.17059.

Full text

Abstract:

The objective of this paper is to improve the subgradient optimization method which is used to solve non-differentiable optimization problems in the Lagrangian dual problem. One of the main drawbacks of the subgradient method is the tuning process to determine the sequence of step-lengths to update successive iterates. In this paper, we propose a modified subgradient optimization method with various step size rules to compute a tuning- free subgradient step-length that is geometrically motivated and algebraically deduced. It is well known that the dual function is a concave function over its domain (regardless of the structure of the cost and constraints of the primal problem), but not necessarily differentiable. We solve the dual problem whenever it is easier to solve than the primal problem with no duality gap. However, even if there is a duality gap the solution of the dual problem provides a lower bound to the primal optimum that can be useful in combinatorial optimization. Numerical examples are illustrated to demonstrate the method. DOI: http://dx.doi.org/10.3329/dujs.v61i2.17059 Dhaka Univ. J. Sci. 61(2): 135-140, 2013 (July)

APA, Harvard, Vancouver, ISO, and other styles

23

Tanaka, Shunji, and Mituhiko Araki. "A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines." International Journal of Production Economics 113, no. 1 (May 2008): 446–58. http://dx.doi.org/10.1016/j.ijpe.2007.10.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Guignard, Monique. "Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0–1 optimization problems with linear constraints." Annals of Operations Research 286, no. 1-2 (November 21, 2018): 173–200. http://dx.doi.org/10.1007/s10479-018-3092-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Qin, Xiao Wei, and Feng Chen. "Multicommodity-Based Delay Analysis for Heterogeneous Wireless Services in Core Network." Applied Mechanics and Materials 198-199 (September 2012): 1733–38. http://dx.doi.org/10.4028/www.scientific.net/amm.198-199.1733.

Full text

Abstract:

With the explosive growth of wireless applications, the subscribers’ requirements of QoS (Quality of Service) are increasing as well. In this paper, the upper bound of the tolerant delay of services in wireless access network is investigated, by mapping core network onto a cost-variable directed graph, where the cost is construed as the average service delay of the ﬂows traveling in core network that depends on the current load. A multicommodity minimal cost ﬂow mathematics problem is then derived and solved by Price-directive Decomposition and Lagrangian Relaxation. Simulations are carried out in two typical core networks and some valuable conclusions are gained.

APA, Harvard, Vancouver, ISO, and other styles

26

Campello, Ruy Eduardo, and Nelson F. Maculan. "Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: properties and algorithms." Discrete Applied Mathematics 18, no. 2 (November 1987): 119–36. http://dx.doi.org/10.1016/0166-218x(87)90015-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Kim, Jinho, Chang Seob Kim, and Zong Woo Geem. "A Memetic Approach for Improving Minimum Cost of Economic Load Dispatch Problems." Mathematical Problems in Engineering 2014 (2014): 1–11. http://dx.doi.org/10.1155/2014/906028.

Full text

Abstract:

Economic load dispatch problem is a popular optimization problem in electrical power system field, which has been so far tackled by various mathematical and metaheuristic approaches including Lagrangian relaxation, branch and bound method, genetic algorithm, tabu search, particle swarm optimization, harmony search, and Taguchi method. On top of these techniques, this study proposes a novel memetic algorithm scheme combining metaheuristic algorithm and gradient-based technique to find better solutions for an economic load dispatch problem with valve-point loading. Because metaheuristic algorithms have the strength in global search and gradient-based techniques have the strength in local search, the combination approach obtains better results than those of any single approach. A bench-mark example of 40 generating-unit economic load dispatch problem demonstrates that the memetic approach can further improve the existing best solutions from the literature.

APA, Harvard, Vancouver, ISO, and other styles

28

BERRETTA, REGINA, PAULO M. FRANÇA, and VINÍCIUS A. ARMENTANO. "METAHEURISTIC APPROACHES FOR THE MULTILEVEL RESOURCE-CONSTRAINED LOT-SIZING PROBLEM WITH SETUP AND LEAD TIMES." Asia-Pacific Journal of Operational Research 22, no. 02 (June 2005): 261–86. http://dx.doi.org/10.1142/s0217595905000510.

Full text

Abstract:

We propose the use of metaheuristics for the resource-capacitated multilevel lot-sizing problem with general product structures, setup costs, setup times, and lead times. Initially, we develop a heuristic which moves production in time in order to obtain feasible solutions with good quality. Strategies for the short-term memory and long-term memory of tabu search are then included to guide the search of the subordinate heuristic for new, feasible, and better solutions. Simulated annealing components are embedded into tabu search in order to improve its performance. For small problems, the solutions provided by tabu search and the hybrid metaheuristic are compared to optimal solutions and for larger problems, the quality of the solutions is evaluated against a lower bound generated by Lagrangean relaxation.

APA, Harvard, Vancouver, ISO, and other styles

29

Bianco, Lucio, and Massimiliano Caramia. "Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound." 4OR 9, no. 4 (April 20, 2011): 371–89. http://dx.doi.org/10.1007/s10288-011-0168-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Trespalacios, Francisco, and Ignacio E. Grossmann. "Lagrangean relaxation of the hull-reformulation of linear generalized disjunctive programs and its use in disjunctive branch and bound." European Journal of Operational Research 253, no. 2 (September 2016): 314–27. http://dx.doi.org/10.1016/j.ejor.2016.02.048.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Barbot, Nelly, Olivier Boëffard, Jonathan Chevelu, and Arnaud Delhay. "Large Linguistic Corpus Reduction with SCP Algorithms." Computational Linguistics 41, no. 3 (September 2015): 355–83. http://dx.doi.org/10.1162/coli_a_00225.

Full text

Abstract:

Linguistic corpus design is a critical concern for building rich annotated corpora useful in different domains of applications. For example, speech technologies such as ASR (Automatic Speech Recognition) or TTS (Text-to-Speech) need a huge amount of speech data to train data-driven models or to produce synthetic speech. Collecting data is always related to costs (recording speech, verifying annotations, etc.), and as a rule of thumb, the more data you gather, the more costly your application will be. Within this context, we present in this article solutions to reduce the amount of linguistic text content while maintaining a sufficient level of linguistic richness required by a model or an application. This problem can be formalized as a Set Covering Problem (SCP) and we evaluate two algorithmic heuristics applied to design large text corpora in English and French for covering phonological information or POS labels. The first considered algorithm is a standard greedy solution with an agglomerative/spitting strategy and we propose a second algorithm based on Lagrangian relaxation. The latter approach provides a lower bound to the cost of each covering solution. This lower bound can be used as a metric to evaluate the quality of a reduced corpus whatever the algorithm applied. Experiments show that a suboptimal algorithm like a greedy algorithm achieves good results; the cost of its solutions is not so far from the lower bound (about 4.35% for 3-phoneme coverings). Usually, constraints in SCP are binary; we proposed here a generalization where the constraints on each covering feature can be multi-valued.

APA, Harvard, Vancouver, ISO, and other styles

32

Zhang, Canrong, Tao Wu, Mingyao Qi, and Lixin Miao. "Simultaneous Allocation of Berths and Quay Cranes under Discrete Berth Situation." Asia-Pacific Journal of Operational Research 35, no. 03 (May 31, 2018): 1850011. http://dx.doi.org/10.1142/s0217595918500112.

Full text

Abstract:

This paper examines the simultaneous allocation of berths and quay cranes under discrete berth situation in container terminals. The berths of discrete type have been broadly applied in realistic production especially for the terminals whose berths are not aligned in a straight line. The typical features of such berths including wharf length constraints, water depth constraints, and berth-bound quay cranes have been considered in this paper. In contrast to the previous work which only deployed the number of quay cranes besides the assignment of berths, this paper assigns berths and quay cranes simultaneously. In addition, to better fit the realistic production, some practical features related to quay cranes including the interference between quay cranes, the berth-dependent productivity of quay cranes, and limited adjustments of the assigned quay cranes during operations have also been considered in this paper. An integer programming model is formulated for this problem, and a sub-gradient-based Lagrangian relaxation algorithm is proposed. A simple but efficient greedy insertion heuristics is developed to solve the decomposed primal problems to optimality. Based on actual data, numerical experiments are conducted to test the performance of the proposed algorithm.

APA, Harvard, Vancouver, ISO, and other styles

33

Zhou, Binghai, and Shi Zong. "Adaptive memory red deer algorithm for cross-dock truck scheduling with products time window." Engineering Computations 38, no. 8 (March 8, 2021): 3254–89. http://dx.doi.org/10.1108/ec-05-2020-0273.

Full text

Abstract:

Purpose The cross-docking strategy has a significant influence on supply chain and logistics efficiency. This paper aims to investigate the most suitable and efficient way to schedule the transfer of logistics activities and present a meta-heuristic method of the truck scheduling problem in cross-docking logistics. A truck scheduling problem with products time window is investigated with objectives of minimizing the total product transshipment time and earliness and tardiness cost of outbound trucks. Design/methodology/approach This research proposed a meta-heuristic method for the truck scheduling problem with products time window. To solve the problem, a lower bound of the problem is built through a novel two-stage Lagrangian relaxation problem and on account of the NP-hard nature of the truck scheduling problem, the novel red deer algorithm with the mechanism of the heuristic oscillating local search algorithm, as well as adaptive memory programming was proposed to overcome the inferior capability of the original red deer algorithm in the aspect of local search and run time. Findings Theory analysis and simulation experiments on an industrial case of a cross-docking center with a product’s time window are conducted in this paper. Satisfactory results show that the performance of the red deer algorithm is enhanced due to the mechanism of heuristic oscillating local search algorithm and adaptive memory programming and the proposed method efficiently solves the real-world size case of truck scheduling problems in cross-docking with product time window. Research limitations/implications The consideration of products time window has very realistic significance in different logistics applications such as cold-chain logistics and pharmaceutical supply chain. Furthermore, the novel adaptive memory red deer algorithm could be modified and applied to other complex optimization scheduling problems such as scheduling problems considering energy-efficiency or other logistics strategies. Originality/value For the first time in the truck scheduling problem with the cross-docking strategy, the product’s time window is considered. Furthermore, a mathematical model with objectives of minimizing the total product transshipment time and earliness and tardiness cost of outbound trucks is developed. To solve the proposed problem, a novel adaptive memory red deer algorithm with the mechanism of heuristic oscillating local search algorithm was proposed to overcome the inferior capability of genetic algorithm in the aspect of local search and run time.

APA, Harvard, Vancouver, ISO, and other styles

34

Balseiro, Santiago R., David B. Brown, and Chen Chen. "Dynamic Pricing of Relocating Resources in Large Networks." Management Science, October 20, 2020. http://dx.doi.org/10.1287/mnsc.2020.3735.

Full text

Abstract:

Motivated by applications in shared vehicle systems, we study dynamic pricing of resources that relocate over a network of locations. Customers with private willingness to pay sequentially request to relocate a resource from one location to another, and a revenue-maximizing service provider sets a price for each request. This problem can be formulated as an infinite-horizon stochastic dynamic program, but it is difficult to solve, as optimal pricing policies may depend on the locations of all resources in the network. We first focus on networks with a hub-and-spoke structure, and we develop a dynamic pricing policy and a performance bound based on a Lagrangian relaxation. This relaxation decomposes the problem over spokes and is thus far easier to solve than the original problem. We analyze the performance of the Lagrangian-based policy and focus on a supply-constrained large network regime in which the number of spokes (n) and the number of resources grow at the same rate. We show that the Lagrangian policy loses no more than O(ln n/n) in performance compared with an optimal policy, thus implying asymptotic optimality as n grows large. We also show that no static policy is asymptotically optimal in the large network regime. Finally, we extend the Lagrangian relaxation to provide upper bounds and policies to general networks with multiple interconnected hubs and spoke-to-spoke connections and to incorporate relocation times. We also examine the performance of the Lagrangian policy and the Lagrangian relaxation bound on some numerical examples, including examples based on data from RideAustin. This paper was accepted by David Simchi-Levi, revenue management and market analytics.

APA, Harvard, Vancouver, ISO, and other styles

35

Kawatra, Rakesh. "A Lagrangean Heuristic For The Degree Constrained Minimal Spanning Tree Problem." Review of Business Information Systems (RBIS) 14, no. 3 (July 1, 2010). http://dx.doi.org/10.19030/rbis.v14i3.493.

Full text

Abstract:

In this paper we present a new heuristic procedure to solve the degree constrained minimal spanning tree problem. This procedure uses Lagrangian relaxation of the integer programming formulation of the problem to get a lower bound for the optimal objective function value. A subgradient optimization method is used to find multipliers that give good lower bounds. A branch exchange procedure is used after each iteration of the subgradient optimization to generate a feasible solution from an infeasible Lagrangean solution. Computational results are given for problems with up to 300 nodes. The heuristic procedure presented here gives optimal solutions in most instances. For problem sets that were not solved optimally, the gap between the lower bound and the feasible solution was less than 10-2 percent.

APA, Harvard, Vancouver, ISO, and other styles

36

Singh, Bismark, and Bernard Knueven. "Lagrangian relaxation based heuristics for a chance-constrained optimization model of a hybrid solar-battery storage system." Journal of Global Optimization, June 1, 2021. http://dx.doi.org/10.1007/s10898-021-01041-y.

Full text

Abstract:

AbstractWe develop a stochastic optimization model for scheduling a hybrid solar-battery storage system. Solar power in excess of the promise can be used to charge the battery, while power short of the promise is met by discharging the battery. We ensure reliable operations by using a joint chance constraint. Models with a few hundred scenarios are relatively tractable; for larger models, we demonstrate how a Lagrangian relaxation scheme provides improved results. To further accelerate the Lagrangian scheme, we embed the progressive hedging algorithm within the subgradient iterations of the Lagrangian relaxation. We investigate several enhancements of the progressive hedging algorithm, and find bundling of scenarios results in the best bounds. Finally, we provide a generalization for how our analysis extends to a microgrid with multiple batteries and photovoltaic generators.

APA, Harvard, Vancouver, ISO, and other styles

37

Fattahi, Parviz, and Mehdi Tanhatalab. "Stochastic inventory-routing problem with lateral transshipment for perishable product." Journal of Modelling in Management ahead-of-print, ahead-of-print (June 3, 2021). http://dx.doi.org/10.1108/jm2-09-2019-0230.

Full text

Abstract:

Purpose This study aims to design a supply chain network in an uncertain environment while exists two options for distribution of the perishable product and production lot-sizing is concerned. Design/methodology/approach Owing to the complexity of the mathematical model, a solution approach based on a Lagrangian relaxation (LR) heuristic is developed which provides good-quality upper and lower bounds. Findings The model output is discussed through various examples. The introduction of some enhancements and using some heuristics results in better outputs in the solution procedure. Practical implications This paper covers the modeling of some real-world problems in which demand is uncertain and managers face making some concurrent decisions related to supply chain management, transportation and logistics and inventory control issues. Furthermore, considering the perishability of product in modeling makes the problem more practically significant as these days there are many supply chains handling dairy and other fresh products. Originality/value Considering uncertainty, production, transshipment and perishable product in the inventory-routing problem makes a new variant that has not yet been studied. The proposed novel solution is based on the LR approach that is enhanced by some heuristics and some valid inequalities that make it different from the current version of the LR used by other studies.

APA, Harvard, Vancouver, ISO, and other styles

38

Decerle, Jérémy, Olivier Grunder, Amir Hajjam El Hassani, and Oussama Barakat. "A matheuristic-based approach for the multi-depot home health care assignment, routing and scheduling problem." RAIRO - Operations Research, June 1, 2020. http://dx.doi.org/10.1051/ro/2020057.

Full text

Abstract:

Home health care structures provide care for the elderly, people with disabilities as well as patients with chronic conditions. Since there has been an increase in demand, organizations providing home health care are eager to optimize their activities. In addition, the increase in patient numbers has led organizations to expand their geographical reach. As a result, home health care structures tend to be located in different offices to limit their travel time and, consequently, caregivers employed by these various structures must be assigned to one of the offices so they start and end their workday at their associated office. Unlike the existing literature where an upstream assignment of caregivers is performed to become a parameter of the model, the assignment of caregivers to offices is solved during the resolution of the problem in order to obtain the best possible combinations. Thus, we suggest a mixed-integer programming model of the multi -depot home health care assignment, routing, and scheduling problem without prior assignment of caregivers to the home health care offices. In addition, we propose an original matheuristic -based approach with different assignment strategies to assign visits and caregivers to the home health care offices in order to solve the problem. The experiments are conducted on a set of 56 heterogeneous instances of various sizes. Results are compared with best solutions obtained by a commercial solver, and with a lower bound obtained by Lagrangian relaxation. The results highlight the efficiency of the matheuristic -based approach since it provides a low deviation ratio with a faster computational time.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Lagrangian relaxation bounds'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles