检索结果-内蒙古大学图书馆

volume-based branch-and-cut algorithm for large-scale fixed-charge multicommodity network design

ANNALS OF OPERATIONS RESEARCH 2024年 1-34页

作者： Shibasaki, Rui S. Baiou, Mourad Barahona, Francisco Mahey, Philippe de Souza, Mauricio C. UPJV MIS 33 Rue St Leu F-80000 Amiens France UCA LIMOS 1 Rue Chebarde F-63178 Aubiere France IBM Corp TJ Watson Res Ctr 1101 Kitchawan Rd Yorktown Hts NY 10598 USA Univ Fed Minas Gerais DEP Ave Antonio Carlos 6627 BR-31270901 Belo Horizonte Brazil Univ Fed Minas Gerais PPGEP Ave Antonio Carlos 6627 BR-31270901 Belo Horizonte Brazil

The fixed-charge multicommodity capacitated network design (FCMC) problem remains challenging, particularly in large-scale contexts. In this particular case, the ability to produce good-quality solutions in a reasonable amount of time depends on the availability of efficient algorithms. Therefore, this paper proposes a volume-based branch-and-cut algorithm, which applies a relax-and-cut procedure to solve linear programs in each node of the enumeration tree. Moreover, a Lagrangian feasibility pump heuristic using the volume algorithm as a solver for linear programs was implemented to accelerate the search for good feasible solutions in large-scale cases. The obtained results showed that the proposed branch-and-cut scheme is competitive with other state-of-the-art algorithms, and presents better performance when solving large-scale instances.

关键词： Lagrangian relaxation Relax-and-cut volume algorithm Multicommodity network design Branch-and-cut

来源：评论

学校读者我要写书评

暂无评论

A parallel implementation of an volume algorithm

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2015年第4期23卷 925-952页

作者： Mohacsi, L. Deak, I. Corvinus Univ Budapest Dept Comp Sci H-1093 Budapest Hungary Corvinus Univ Budapest Budapest Hungary

Recently an volume algorithm has been presented for convex bodies by Lovasz and Vempala, where is the number of dimensions of the convex body. Essentially the algorithm consists of several, interlocked simulational steps of slightly different natures. A computer implementation was later developed to gather some information about the numerical aspects of the algorithm, the number of dimensions in the examples was at most 10, and the errors of the results were somewhat dissatisfying. Now we present a parallel version of the improved algorithm, where variance reducing was added to make the algorithm faster, and the use of a GPU with 480 processors made experimentation easier. Computational results for convex bodies in dimensions ranging from 2 to 20 are presented as well.

关键词： Monte Carlo computation volume algorithm GPU Simulation Computational results

来源：评论

学校读者我要写书评

暂无评论

A Lagrangian Relaxation Heuristic for a Bi-Objective Multimodal Transportation Planning Problem

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2023年第1期24卷 382-399页

作者： Li, Zhaojin Chen, Haoxun Liu, Ya Jin, Kun Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China Univ Technol Troyes Lab Comp Sci & Digital Soc LIST3N Logist & Optimizat Ind Syst LOSI Team F-10004 Troyes France Air Force Med Univ Foreign Languages Dept Xian 710049 Peoples R China

We study a realistic Bi-objective Multimodal Transportation Planning Problem (BMTPP) faced by logistics companies when trying to obtain cost advantages and improve the customer satisfaction in a competitive market. The two objectives considered are: the minimization of total transportation cost and the maximization of service quality. Given a set of transportation orders described by an origin, a destination and a time window, solving BMTPP involves determining the delivery path for each order in a capacitated network as well as selecting the carrier with the best service quality for each edge of the path. The BMTPP is formulated as a novel bi-objective mixed integer linear programming model and an iterative $\epsilon$ -constraint method is applied to solve it. As the NP-hardness of the single-objective problems derived from BMTPP, a Lagrangian Relaxation (LR) heuristic which can not only provide a near-optimal solution but also a lower bound for each of the single-objective problems is developed. 100 randomly generated instances are tested and the computational results demonstrate the effectiveness of the heuristic in obtaining a tight lower bound and a high-quality near-optimal solution for the derived single-objective problem. Various performance indicators show the high-quality of the Pareto front of the bi-objective problem obtained by the heuristic. We also provide a case study for the proposed LR heuristic in a logistics network in China.

关键词： Multimodal transportation bi-objective optimization Lagrangian relaxation volume algorithm

来源：评论

学校读者我要写书评

暂无评论

Determination of Locational Marginal Redispatch Prices of a Mixed-Integer Congestion Management Problem 20

Determination of Locational Marginal Redispatch Prices of a ...

引用

20th International Conference on the European Energy Market (EEM)

作者： Blank, Andreas Einsiedler, Jana Moser, Albert Rhein Westfal TH Aachen Inst High Voltage Equipment & Grids Digitalizat & Aachen Germany

ISBN: (纸本)9798350381757;9798350381740

Locational marginal prices (LMP) are the basis for many studies on energy economic questions. LMPs are determined from the dual solution of the primary optimization problem. If the optimization problem is formulated linearly, dual variables can be read from the closed-form solution using commercially available solvers such as CPLEX or GUROBI. Mixed integer problems (MILP) are no longer possible, and the dual solution's decomposition and iterative determination are required. This paper presents an extended Lagrangian method for congestion management simulation, which can determine locational marginal redispatch prices (LMRP) by considering mixed-integer constraints of thermal power plants considering startup and shutdown costs.

关键词： congestion management Lagrangian relaxation locational marginal pricing redispatch volume algorithm

来源：评论

学校读者我要写书评

暂无评论

Lagrangian bounds for large-scale multicommodity network design: a comparison between volume and Bundle methods

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2021年第1期28卷 296-326页

作者： Shibasaki, Rui S. Baiou, Mourad Barahona, Francisco Mahey, Philippe de Souza, Mauricio C. Univ Fed Minas Gerais PPGEP Ave Antonio Carlos 6627 BR-31270901 Belo Horizonte MG Brazil Univ Clermont Auvergne LIMOS 1 Rue Chebarde F-63178 Aubiere France IBM Corp Thomas J Watson Res Ctr 1101 Kitchawan Rd Yorktown Hts NY USA Univ Fed Minas Gerais DEP Ave Antonio Carlos 6627 BR-31270901 Belo Horizonte MG Brazil

The Bundle Method and the volume algorithm are among the most efficient techniques to obtain accurate Lagrangian dual bounds for hard combinatorial optimization problems. We propose here to compare their performance on very large scale Fixed-Charge Multicommodity Capacitated Network Design problems. The motivation is not only the quality of the approximation of these bounds as a function of the computational time but also the ability to produce feasible primal solutions and thus to reduce the gap for very large instances for which optimal solutions are out of reach. Feasible solutions are obtained through the use of Lagrangian information in constructive and improving heuristic schemes. We show in particular that, if the Bundle implementation has provided great quality bounds in fewer iterations, the volume algorithm is able to reduce the gaps of the largest instances, taking profit of the low computational cost per iteration compared to the Bundle Method.

关键词： Bundle method volume algorithm fixed-charge multicommodity network design problem

来源：评论

学校读者我要写书评

暂无评论

Lagrangian Relaxation of Large-scale Congestion Management using Extended Subgradient Methods 18

Lagrangian Relaxation of Large-scale Congestion Management u...

引用

18th International Conference on the European Energy Market (EEM)

作者： Blank, Andreas Schmitt, Carlo Mehlem, Jonas Moser, Albert Rhein Westfal TH Aachen Inst High Voltage Equipment & Grids Digitalizat & Aachen Germany

ISBN: (数字)9781665408967

ISBN: (纸本)9781665408967

Modeling a high amount of decentralized flexibility options within the congestion management simulation of transmission grids leads to a significant increase in the complexity of the resulting optimization problem. For this purpose, this paper presents a decomposition approach of a congestion management model using the Lagrangian relaxation method in combination with the volume algorithm to find a reliable primal solution. The decomposed model is applied to a benchmark case, and the results are validated by comparison to the closed solution. Therefore, a comparison of the primal objective function value and locational marginal prices for redispatch derived from shadow prices of system coupling constraints occurs. It can be observed that the shadow prices are matched with very high precision, thus validating the approach.

关键词： congestion management Lagrangian relaxation locational marginal pricing redispatch volume algorithm

来源：评论

学校读者我要写书评

暂无评论

Lagrangian Decomposition Methods for Large-Scale Fixed-Charge Capacitated Multicommodity Network Design Problem

Lagrangian Decomposition Methods for Large-Scale Fixed-Charg...

引用

作者： Sa Shibasaki, Rui Clermont Auvergne Universidade federal de Minas Gerais

学位级别：博士

Typiquement présent dans les domaines de la logistique et des télécommunications, le problème de synthèse de réseau multi-flot à charge fixe reste difficile, en particulier dans des contextes à grande échelle. Dans ce cas, la capacité à produire des solutions de bonne qualité dans un temps de calcul raisonnable repose sur la disponibilité d'algorithmes efficaces. En ce sens, cette thèse propose des approches lagrangiennes capables de fournir des bornes relativement proches de l'optimal pour des instances de grande taille. L'efficacité des méthodes dépend de l'algorithme appliqué pour résoudre les duals lagrangiens, nous choisissons donc entre deux des solveurs les plus efficaces de la littérature: l'algorithme de volume et la méthode Bundle, fournissant une comparaison entre eux. Les résultats ont montré que l'algorithme de volume est plus efficace dans le contexte considéré, étant celui choisi pour le développement du projet de *** première heuristique lagrangienne a été conçue pour produire des solutions réalisables de bonne qualité pour le problème, obtenant de bien meilleurs résultats que Cplex pour les plus grandes instances. Concernant les limites inférieures, un algorithme Relax-and-Cut a été implémenté intégrant une analyse de sensibilité et une mise à l'échelle des contraintes, ce qui a amélioré les résultats. Les améliorations des bornes inférieures ont atteint 11\%, mais en moyenne, elles sont restées inférieures à 1\%. L'algorithme Relax-and-Cut a ensuite été inclus dans un schéma Branch-and-Cut, pour résoudre des programmes linéaires dans chaque nœud de l'arbre de recherche. De plus, une heuristique Feasibility Pump lagrangienne a été implémentée pour accélérer la recherche de bonnes solutions réalisables. Les résultats obtenus ont montré que le schéma proposé est compétitif avec les meilleurs algorithmes de la littérature et fournit les meilleurs résultats dans des contextes à grande échelle. De plus, une version heuristique de l'algorithme B

关键词： Synthèse de réseau multi-flot Relaxation lagrangienne algorithme de volume Bundle Relax-and-Cut Branch-and-Cut Multicommodity Network Design Lagrangian Relaxation volume algorithm Bundle Method Relax-and-Cut Branch-and-Cut

来源：评论

学校读者我要写书评

暂无评论

Computational results of an O*(n⁴) volume algorithm

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2012年第1期216卷 152-161页

作者： Lovasz, L. Deak, I. Corvinus Univ Budapest Dept Comp Sci H-1093 Budapest 9 Hungary Eotvos Lorand Univ Dept Comp Sci H-1117 Budapest Hungary

Recently an O*(n(4)) volume algorithm has been presented for convex bodies by Lovasz and Vempala, where n is the number of dimensions of the convex body. Essentially the algorithm is a series of Monte Carlo integrations. In this paper we describe a computer implementation of the volume algorithm, where we improved the computational aspects of the original algorithm by adding variance decreasing modifications: a stratified sampling strategy, double point integration and orthonormalised estimators. Formulas and methodology were developed so that the errors in each phase of the algorithm can be controlled. Some computational results for convex bodies in dimensions ranging from 2 to 10 are presented as well. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Applied probability Simulation Monte Carlo computation Markov processes volume algorithm Computational results

来源：评论

学校读者我要写书评

暂无评论

Cluster Lagrangean decomposition in multistage stochastic optimization

引用

COMPUTERS & OPERATIONS RESEARCH 2016年 67卷 48-62页

作者： Escuclero, Laureano F. Garin, Maria Araceli Unzueta, Aitziber Univ Rey Juan Carlos Dept Estadist & Invest Operat Mostoles Madrid Spain Univ Basque Country UPV EHU Dept Econ Aplicada 3 E-48080 Bilbao Bizkaia Spain Univ Basque Country UPV EHU Dept Matemat Aplicada E-48080 Bilbao Bizkaia Spain

We present a Lagrangean Decomposition approach for obtaining strong lower bounds on minimizing medium to large scale multistage stochastic mixed 0-1 problems. The problem is represented by a mixture of the splitting representation up to a given stage, so-named break stage, and the compact representation for the other stages along the time horizon. The dualization of the nonanticipativity constraints for the variables up to the break stage results in a model that can be decomposed into a set of independent scenario cluster submodels. The nonanticipativity constraints for the 0-1 and continuous variables in the cluster submodels are implicitly satisfied. Four scenario cluster schemes are compared for Lagrangean multipliers updating such as the Subgradient Method, the volume algorithm, the Lagrangean Progressive Hedging algorithm and the Dynamic Constrained Cutting Plane scheme. We have observed in randomly generated instances that the smaller the number of clusters, the stronger the lower bound provided for the original problem (even, frequently, it is the solution value). (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Multistage stochastic integer optimization Cluster Lagrangean problem Subgradient method volume algorithm Lagrangean progressive hedging algorithm Dynamic constrained cutting plane scheme

来源：评论

学校读者我要写书评

暂无评论

Scenario Cluster Decomposition of the Lagrangian dual in two-stage stochastic mixed 0-1 optimization

引用

COMPUTERS & OPERATIONS RESEARCH 2013年第1期40卷 362-377页

作者： Escudero, Laureano F. Araceli Garin, M. Perez, Gloria Unzueta, Aitziber Univ Basque Country Dpto Econ Aplicada 3 E-48080 Bilbao Spain Univ Rey Juan Carlos Dpto Estadist & Invest Operat Mostoles Spain Univ Basque Country Dpto Matemat Aplicada & Estadist E-48080 Bilbao Spain Univ Basque Country IO E-48080 Bilbao Spain

In this paper we introduce four scenario Cluster based Lagrangian Decomposition procedures for obtaining strong lower bounds to the (optimal) solution value of two-stage stochastic mixed 0-1 problems. At each iteration of the Lagrangian based procedures, the traditional aim consists of obtaining the solution value of the corresponding Lagrangian dual via solving scenario submodels once the nonanticipativity constraints have been dualized. Instead of considering a splitting variable representation over the set of scenarios, we propose to decompose the model into a set of scenario clusters. We compare the computational performance of the four Lagrange multiplier updating procedures, namely the Subgradient Method, the volume algorithm, the Progressive Hedging algorithm and the Dynamic Constrained Cutting Plane scheme for different numbers of scenario clusters and different dimensions of the original problem. Our computational experience shows that the Cluster based Lagrangian Decomposition bound and its computational effort depend on the number of scenario clusters to consider. In any case, our results show that the Cluster based Lagrangian Decomposition procedures outperform the traditional Lagrangian Decomposition scheme for single scenarios both in the quality of the bounds and computational effort. All the procedures have been implemented in a C++ experimental code. A broad computational experience is reported on a test of randomly generated instances by using the MIP solvers COIN-OR (2010, [18]) and CPLEX (2009, [17]) for the auxiliary mixed 0-1 cluster submodels, this last solver within the open source engine COIN-OR. We also give computational evidence of the model tightening effect that the preprocessing techniques, cut generation and appending and parallel computing tools have in stochastic integer optimization. Finally, we have observed that the plain use of both solvers does not provide the optimal solution of the instances included in the testbed with which

关键词： Two-stage stochastic integer programming Nonanticipativity constraints Cluster Lagrangian Decomposition Scenario cluster model Subgradient Method volume algorithm Progressive Fledging algorithm Dynamic Constrained Cutting Plane Scheme

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：