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

A branch and cut algorithm for Two-Echelon Inventory Routing Problem with End-of-Tour Replenishment Policy

Open Journal of Applied Sciences 2024年第11期14卷 3100-3126页

作者： Bi Kouaï Bertin Kayé Doffou Jerome Diako Zacrada Françoise Odile Trey UFR Mathmatiques et Informatique Universit Flix Houphout-Boigny (UFHB) Abidjan Cte dIvoire Laboratoire de Mcanique et Informatique (LAMI) Abidjan Cte dIvoire Ecole Suprieure des Technologies de lInformation et de la Communication (ESATIC) Abidjan Cte dIvoire Laboratoire des Sciences et Technologies de lInformation et de la Communication (LASTIC) Abidjan Cte dIvoire

This study presents a two-echelon inventory routing problem (2E-IRP) with an end-of-tour replenishment (ETR) policy whose distribution network consists of a supplier, several distribution centers (DCs) and several retailers on a multi-period planning horizon. A formulation of the problem based on vehicle indices is proposed in the form of a mixed integer linear program (MILP). The mathematical model of the problem is solved using a branch and cut (B&C) algorithm. The results of the tests are compared to the results of a branch and price (B&P) algorithm from the literature on 2E-IRP with a classical distribution policy. The results of the tests show that the B&C algorithm solves 197 out of 200 instances (98.5%). The comparison of the B&C and B&P results shows that 185 best solutions are obtained with the B&C algorithm on 197 instances (93.9%). Overall, the B&C algorithm achieves cost reductions ranging from 0.26% to 41.44% compared to the classic 2E-IRP results solved with the B&P algorithm, with an overall average reduction of 18.08%.

关键词： Multi-Depots 2E-IRP branch and cut algorithm End-of-Tour Replenishment Policy Vendor Managed Inventory

来源：评论

学校读者我要写书评

暂无评论

Production scheduling under uncertainty of an open-pit mine using Lagrangian relaxation and branch-and-cut algorithm

引用

INTERNATIONAL JOURNAL OF MINING RECLAMATION AND ENVIRONMENT 2020年第5期34卷 343-361页

作者： Chatterjee, Snehamoy Dimitrakopoulos, Roussos Michigan Technol Univ Geol & Min Engn & Sci Houghton MI 49931 USA McGill Univ Dept Min & Mat Engn COSMO Stochast Mine Planning Lab Montreal PQ Canada

The life-of-mine optimization of open pit mine production scheduling under geological uncertainty is a computationally intensive process. Production scheduling determines the optimal extraction sequence by maximizing net present value (NPV). In this paper, an algorithm is proposed to schedule an open pit mine under geological uncertainty, where instead of solving the whole problem at once, the production schedule is generated by sequentially solving sub-problems. The sub-gradient method is used to generate the upper bound solution of a Lagrangian relaxed sub-problem. If the upper bound relaxed solution is infeasible, a mixed integer programming is applied to the latter solution. The algorithm is validated by solving six problems and is compared to the linear relaxation of the original production scheduling problem. The results show that the proposed algorithm generates a solution that is very close to optimal, with less than a 3% optimality gap. An application at a copper mine, where geological uncertainty is quantified with geostatistical simulations of the related orebody, shows that all constraints are satisfied and an 11% higher NPV is generated when compared to the corresponding deterministic equivalent of the proposed approach, while a 26% higher NPV is generated compared to a common conventional industry approach.

关键词： Open pit mine optimisation production scheduling uncertain supply Lagrangian relaxation sub-gradient method branch and cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Designing a resilient supply chain network: A multi-objective data-driven distributionally robust optimization method

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 173卷

作者： Chen, Shengjie Chen, Yanju Hebei Univ Coll Math & Informat Sci Risk Management & Financial Engn Lab Baoding Peoples R China

Uncertainty of supply chain disruption poses a significant challenge to decision-making in many real-life problems. In this paper, anew multi-objective data-driven distributionally robust optimization (MDDRO) model for the resilient supply chain network (RSCN) design problem under disruption scenario is developed, which includes minimizing the total cost, carbon emissions, and delivery time. In the context of supply chain disruption, it is important self-evidently that products can be supplied normally and the practical demand can be met. In handling the partial probability distribution information of the considered uncertain demand, this paper uses a data-driven Wasserstein-Moment ambiguity set (WMAS), which incorporate the Wasserstein metric and Moment information, and a robust counterpart to transform the developed model into a tractable approximation form. The finite-sample performance guarantee of the optimal solution of MDDRO model with Wasserstein-Moment ambiguous chance constraint is given. An accelerated branch and cut algorithm (BCA) constructed to solve the MDDRO model. Finally, through the investigation of a real-life case and sensitivity analysis of key parameters, some managerial insights are put forward.

关键词： Resilient supply chain network Distributionally robust optimization Wasserstein metric Moment information branch and cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Deterministic optimization of the thermal Unit Commitment problem: A branch and cut search

引用

COMPUTERS & CHEMICAL ENGINEERING 2014年 67卷 53-68页

作者： Marcovecchio, Marian G. Novais, Augusto Q. Grossmann, Ignacio E. Univ Nacl Litoral Argentina UNL Consejo Nacl Invest Cient & Tecn INGAR CONICET Santa Fe Argentina LNEG Lisbon Portugal Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA

This paper proposes a novel deterministic optimization approach for the Unit Commitment (UC) problem, involving thermal generating units. A mathematical programming model is first presented, which includes all the basic constraints and a set of binary variables for the on/off status of each generator at each time period, leading to a convex mixed-integer quadratic programming (MIQP) formulation. Then, an effective solution methodology based on valid integer cutting planes is proposed, and implemented through a branch and cut search for finding the global optimal solution. The application of the proposed approach is illustrated with several examples of different dimensions. Comparisons with other mathematical formulations are also presented. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Energy optimization Unit Commitment problem Deterministic optimization branch and cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Effects of binary variables in mixed integer linear programming based unit commitment in large-scale electricity markets

引用

ELECTRIC POWER SYSTEMS RESEARCH 2018年 160卷 429-438页

作者： Alemany, Juan Kasprzyk, Leszek Magnago, Fernando Rio Cuarto Natl Univ Power Syst Anal Grp Rio Cuarto Argentina Poznan Univ Tech Inst Elect & Elect Ind Poznan Poland Nexant Inc Chandler AZ USA

Mixed integer linear programming is one of the main approaches used to solve unit commitment problems. Due to the computational complexity of unit commitment problems, several researches remark the benefits of using less binary variables or relaxing them for the branch-and-cut algorithm. However, integrality constraints relaxation seems to be case dependent because there are many instances where applying it may not improve the computational burden. In addition, there is a lack of extensive numerical experiments evaluating the effects of the relaxation of binary variables in mixed integer linear programming based unit commitment. Therefore, the primary purpose of this work is to analyze the effects of binary variables and compare different relaxations, supported by extensive computational experiments. To accomplish this objective, two power systems are used for the numerical tests: the IEEE118 test system and a very large scale real system. The results suggest that a direct link between the relaxation of binary variables and computational burden cannot be easily assured in the general case. Therefore, relaxing binary variables should not be used as a general rule-of-practice to improve computational burden, at least, until each particular model is tested under different load scenarios and formulations to quantify the final effects of binary variables on the specific UC implementation. The secondary aim of this work is to give some preliminary insight into the reasons that could be supporting the binary relaxation in some UC instances. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Binary variables relaxation branch and cut algorithm Day-ahead electricity market clearing Mixed integer linear programming Unit commitment

来源：评论

学校读者我要写书评

暂无评论

Resource constrained project scheduling with uncertain activity durations

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2017年 112卷 537-550页

作者： Chakrabortty, Ripon K. Sarker, Ruhul A. Essam, Daryl L. Univ New South Wales Sch Engn & Informat Technol Canberra ACT 2600 Australia

In this paper, we consider Resource Constrained Project Scheduling Problems (RCPSPs) with known deterministic renewable resource requirements but uncertain activity durations. In this case, the activity durations are represented by random variables with different probability distribution functions. To deal with this problem, we propose an approach based on the robust optimization concept, which produces reasonably good solutions under any likely input data scenario. Depending on different uncertainty characteristics, we have developed six different heuristics to incorporate the uncertain duration as a deterministic constraint in a robust optimization model. The resulting optimization model is then solved by using a Coin-branch & cut (CBC) solver. To judge the performance of the algorithm, we solved 30, 60, 90 and 120-activity benchmark problems from the project scheduling problem library (PSPLIB). Our proposed approach guarantees the feasibility of solutions and produces high-quality solutions, particularly for larger activity instances, compared to other existing approaches. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： RCPSP SRCPSP branch and cut algorithm Robust optimization Heuristics

来源：评论

学校读者我要写书评

暂无评论

Robust multi-product newsvendor model with uncertain demand and substitution

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第1期293卷 190-202页

作者： Zhang, Jie Xie, Weijun Sarin, Subhash C. Virginia Tech Dept Ind & Syst Engn Blacksburg VA 24061 USA

This work studies a Robust Multi-product Newsvendor Model with Substitution (R-MNMS), where the demand and the substitution rates are stochastic and are subject to cardinality-constrained uncertainty sets. The goal of this work is to determine the optimal order quantities of multiple products to maximize the worst-case total profit. To achieve this, we first show that for given order quantities, computing the worst-case total profit, in general, is NP-hard. Therefore, we derive the closed-form optimal solutions for the following three special cases: (1) if there are only two products, (2) if there is no substitution among different products, and (3) if the budget of demand uncertainty is equal to the number of products. For a general R-MNMS, we formulate it as a mixed-integer linear program with an exponential number of constraints and develop a branch and cut algorithm to solve it. For large-scale problem instances, we further propose a conservative approximation of R-MNMS and prove that under some certain conditions, this conservative approximation yields an exact optimal solution to R-MNMS. The numerical study demonstrates the effectiveness of the proposed approaches and the robustness of our model. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Stochastic programming Robust Cardinality-constrained uncertainty set Mixed-integer program branch and cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Formulating and solving the minimum dominating cycle problem

引用

Electronic Notes in Discrete Mathematics 2013年 41卷 423-430页

作者： Lucena, Abilio Salles da Cunha, Alexandre Simonetti, Luidi Departamento de Administração / PESC-COPPE Universidade Federal do Rio de Janeiro Rio de Janeiro Brazil Departamento de Ciência da Computação Universidade Federal de Minas Gerais Belo Horizonte Brazil Instituto de Computação Universidade Federal Fluminense Niteroi Brazil

This paper introduces a formulation for the Minimum Dominating Cycle Problem. Additionally, a branch and cut algorithm, based on that formulation, is also investigated. So far, the algorithm contains no primal heuristics. However, it managed to solve to proven optimality, in acceptable CPU times, all test instances with up to 120 vertices. © 2013 Elsevier B.V.

关键词： branch and cut algorithm Formulations Minimum dominating cycle problem Valid inequalities

来源：评论

学校读者我要写书评

暂无评论

Transfer synchronization model with elastic headway and valid inequalities

Transfer synchronization model with elastic headway and vali...

引用

International Conference on Intelligent Rail Transportation (ICIRT)

作者： Xu, Wenkai Zhao, Peng Ning, Liqiao Beijing Jiaotong Univ Sch Traff & Transportat Beijing Peoples R China

ISBN: (纸本)9781538675281

Given that the timetable with even headway is inferior in matching the passenger demand, we use the departure times in even headway situation as the benchmarks, and allow the departure times to change within a limited range to increases the flexibility in timetabling. Then a transfer synchronization model with elastic headway is constructed. By analyzing the specific structure of the model, four classes of valid inequalities are designed to improve the computational efficiency when implementing the branch and cut algorithm in CPLEX. Finally, an experimental case study is conducted and results show that timetabling with elastic headway can effectively improve transfer efficiency, and valid inequalities can strengthen the linear relaxation model and shrink the solution space as well as the number of branch nodes, and then the algorithm can seek the optimal solution faster.

关键词： urban rail transit elastic headway transfer synchronization branch and cut algorithm valid inequalities

来源：评论

学校读者我要写书评

暂无评论

EXACT SOLUTION METHODOLOGIES FOR THE P-CENTER PROBLEM UNDER SINGLE AND MULTIPLE ALLOCATION STRATEGIES

EXACT SOLUTION METHODOLOGIES FOR THE P-CENTER PROBLEM UNDER ...

引用

作者： Hatice Calik Bilkent University

学位级别：博士

The p-center problem is a relatively well known facility location problem that involves locating p identical facilities on a network to minimize the maximum distance between demand nodes and their closest facilities. The focus of the problem is on the minimization of the worst case service time. This sort of objective is more meaningful than total cost objectives for problems with a time sensitive service structure. A majority of applications arises in emergency service locations such as determining optimal locations of ambulances, fire stations and police stations where the human life is at stake. There is also an increased interest in p-center location and related location covering problems in the contexts of terror fighting, natural disasters and human-caused disasters. The p-center problem is NP-hard even if the network is planar with unit vertex weights, unit edge lengths and with the maximum vertex degree of 3. If the locations of the facilities are restricted to the vertices of the network, the problem is called the vertex restricted p-center problem; if the facilities can be placed anywhere on the network, it is called the absolute p-center problem. The p-center problem with capacity restrictions on the facilities is referred to as the capacitated p-center problem and in this problem, the demand nodes can be assigned to facilities with single or multiple allocation strategies. In this thesis, the capacitated p-center problem under the multiple allocation strategy is studied for the first time in the literature. The main focus of this thesis is a modelling and algorithmic perspective in the exact solution of absolute, vertex restricted and capacitated p-center prob- lems. The existing literature is enhanced by the development of mathematical formulations that can solve typical dimensions through the use of off the-shelf commercial solvers. By using the structural properties of the proposed formula- tions, exact algorithms are developed. In order to increase t

关键词： p-center problem absolute p-center problem capacitated p-center problem multiple allocation branch and cut algorithm Benders Decomposition network design

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：