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

The coordinated production and transportation scheduling problem with a time-sensitive product: a branch-and-cut algorithm

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2017年第2期55卷 536-557页

作者： Karaoglan, Ismail Kesen, Saadettin Erhan Selcuk Univ Dept Ind Engn Fac Engn Konya Turkey

In many supply chain scenarios in which short lifespan products are considered, production and transportation decisions must be made in a coordinated manner with no inventory stage. Hence, a solution to this problem conveys information about production starting times of each product lot at facility and delivery times of the lots to various customer-sites located in different geographic regions. In this paper, we study a variant of the problem that single product with limited shelf life is produced at single facility. Once produced, production lot is directly distributed to the customers with non-ignorable transportation time by single vehicle having limited capacity before the lifespan. Objective is to determine the minimum time required to produce and deliver all customer demands. To this end, we develop a branch-and-cut (B&C) algorithm using several valid inequalities adopted from the existing literature to improve lower bounds and applying a local search based on simulated annealing approach to improve upper bounds. On test problems available in the literature, we evaluate the performance of the B&C algorithm. Results show the promising performance of the B&C algorithm.

关键词： supply chain coordination vehicle routing problem scheduling branch-and-cut algorithm time-sensitive product

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2020年第2期75卷 493-513页

作者： Kobayashi, Ken Takano, Yuich Fujitsu Labs LTD. Artificial Intelligence LabNakahara-ku 4-1-1 Kamikodanaka Kawasaki Kanagawa 2118588 Japan Univ Tsukuba Fac Engn Informat Syst 1-1-1 Tennodai Tsukuba Shi Ibaraki 3058577 Japan

We consider a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite (psd) constraint is relaxed, and the resultant mixed-integer linear optimization problem is solved repeatedly, imposing at each iteration a valid inequality for the psd constraint. We prove the convergence properties of the algorithm. Moreover, to speed up the computation, we devise a branch-and-cut algorithm, in which valid inequalities are dynamically added during a branch-and-bound procedure. We test the computational performance of our cutting-plane and branch-and-cut algorithms for three types of MISDO problem: random instances, computing restricted isometry constants, and robust truss topology design. Our experimental results demonstrate that, for many problem instances, our branch-and-cut algorithm delivered superior performance compared with general-purpose MISDO solvers in terms of computational efficiency and stability.

关键词： Mixed-integer optimization Semidefinite optimization cutting-plane algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm

引用

MATHEMATICAL PROGRAMMING 2010年第2期121卷 269-305页

作者： Dumitrescu, Irina Ropke, Stefan Cordeau, Jean-Francois Laporte, Gilbert HEC Montreal Canada Res Chair Distribut Management Montreal PQ H3T 2A7 Canada Univ Sydney Sch Math & Stat Sydney NSW 2052 Australia HEC Montreal Canada Res Chair Logist & Transportat Montreal PQ H3T 2A7 Canada

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. In this paper, the TSPPD is modeled as an integer linear program and its polyhedral structure is analyzed. In particular, the dimension of the TSPPD polytope is determined and several valid inequalities, some of which are facet defining, are introduced. Separation procedures and a branch-and-cut algorithm are developed. Computational results show that the algorithm is capable of solving to optimality instances involving up to 35 pickup and delivery requests, thus more than doubling the previous record of 15.

关键词： Traveling salesman problem Pickup and delivery Precedence relationships Polyhedral results Valid inequalities Separation procedures branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Polyhedral results and a branch-and-cut algorithm for the k-cardinality tree problem

引用

MATHEMATICAL PROGRAMMING 2013年第1-2期142卷 511-538页

作者： Simonetti, Luidi da Cunha, Alexandre Salles Lucena, Abilio Univ Fed Fluminense Inst Comp Rio De Janeiro Brazil Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil Univ Fed Rio de Janeiro Dept Adm Programa Engn Sistemas & Comp Rio De Janeiro Brazil

Given an undirected graph G with vertex and edge weights, the k-cardinality tree problem asks for a minimum weight tree of G containing exactly k edges. In this paper we consider a directed graph reformulation of the problem and carry out a polyhedral investigation of the polytope defined by the convex hull of its feasible integral solutions. Three new families of valid inequalities are identified and two of them are proven to be facet implying for that polytope. Additionally, a branch-and-cut algorithm that separates the new inequalities is implemented and computationally tested. The results obtained indicate that our algorithm outperforms its counterparts from the literature. Such a performance could be attributed, to a large extent, to the use of the new inequalities and also to some pre-processing tests introduced in this study.

关键词： branch-and-cut algorithm Polyhedral study k-Cardinality tree problem

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes

引用

ANNALS OF OPERATIONS RESEARCH 2019年第2期275卷 321-338页

作者： Henke, Tino Speranza, M. Grazia Waescher, Gerhard Otto Von Guericke Univ Dept Management Sci D-39106 Magdeburg Germany Univ Brescia Dept Quantitat Methods I-25122 Brescia Italy Beijing Jiaotong Univ Sch Mech Elect & Control Engn Beijing 100044 Peoples R China

Multi-compartment vehicle routing problems arise in a variety of problem settings in which different product types have to be transported separated from each other. In this paper, a problem variant which occurs in the context of glass waste recycling is considered. In this problem, a set of locations exists, each of which offering a number of containers for the collection of different types of glass waste (e.g. colorless, green, brown glass). In order to pick up the contents from the containers, a fleet of homogeneous disposal vehicles is available. Individually for each disposal vehicle, the capacity can be discretely separated into a limited number of compartments to which different glass waste types are assigned. The objective of the problem is to minimize the total distance to be travelled by the disposal vehicles. For solving this problem to optimality, a branch-and-cut algorithm has been developed and implemented. Extensive numerical experiments have been conducted in order to evaluate the algorithm and to gain insights into the problem structure. The corresponding results show that the algorithm is able to solve instances with up to 50 locations to optimality and that it reduces the computing time by 87% compared to instances from the literature. Additional experiments give managerial insights into the use of different variants of compartments with flexible sizes.

关键词： Vehicle routing Multiple compartments branch-and-cut algorithm Waste collection

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems

引用

OPTIMIZATION 2018年第2期67卷 359-375页

作者： Deng, Zhibin Fang, Shu-Cherng Lu, Cheng Guo, Xiaoling Univ Chinese Acad Sci Sch Econ & Management Beijing Peoples R China Chinese Acad Sci Key Lab Big Data Min & Knowledge Management Beijing Peoples R China North Carolina State Univ Dept Ind & Syst Engn Raleigh NC USA North China Elect Power Univ Sch Econ & Management Beijing Peoples R China China Univ Min & Technol Dept Math Beijing Peoples R China

In this paper, we propose a branch-and-cut algorithm for solving a nonconvex quadratically constrained quadratic programming (QCQP) problem with a nonempty bounded feasible domain. The problem is first transformed into a linear conic programming problem, and then approximated by semidefinite programming problems over different intervals. In order to improve the lower bounds, polar cuts, generated from corresponding cut-generation problems, are embedded in a branch-and-cut algorithm to yield a globally epsilon(r)-epsilon(z)-optimal solution (with respect to feasibility and optimality, respectively) in a finite number of iterations. To enhance the computational speed, an adaptive branch-and-cut rule is adopted. Numerical experiments indicate that the number of explored nodes required for solving QCQP problems can be significantly reduced by employing the proposed polar cuts.

关键词： branch-and-cut algorithm nonconvex quadratically constrained quadratic programming polar cut semidefinite relaxation

来源：评论

学校读者我要写书评

暂无评论

The pickup and delivery problem: Faces and branch-and-cut algorithm

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1997年第12期33卷 1-13页

作者： Ruland, KS Rodin, EY WASHINGTON UNIV DEPT SYST SCI & MATHST LOUISMO 63130

This paper formulates the pickup and delivery problem, also known as the dial-a-ride problem, as an integer program. Its polyhedral structure is explored and four classes of valid inequalities developed. The results o... 详细信息

关键词： integer programming branch-and-cut algorithm pickup and delivery problem

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for the undirected selective traveling salesman problem

引用

NETWORKS 1998年第4期32卷 263-273页

作者： Gendreau, M Laporte, G Semet, F Univ Montreal Ctr Rech Transports Montreal PQ H3C 3J7 Canada

The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a tour of maximal profit including all compulsory vertices and whose cost does not exceed a preset constant. We developed several classes of valid inequalities for the symmetric STSP and used them in a branch-and-cut algorithm. Depending on problem parameters, the proposed algorithm can solve instances involving up to 300 vertices. (C) 1998 John Wiley & Sons, Inc.

关键词： selective traveling salesman problem orienteering branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation

引用

NUMERICAL algorithmS 2021年第2期88卷 993-1024页

作者： Luo, Hezhi Chen, Sikai Wu, Huixian Zhejiang Sci Tech Univ Coll Sci Dept Math Hangzhou 310018 Zhejiang Peoples R China Zhejiang Univ Technol Coll Sci Dept Appl Math Hangzhou 310032 Zhejiang Peoples R China Hangzhou Dianzi Univ Coll Sci Dept Math Hangzhou 310018 Zhejiang Peoples R China

We consider a non-convex quadratic program (QP) with linear and convex quadratic constraints that arises from a broad range of applications and is known to be NP-hard. In this paper, we first prove that the alternative direction method converges to a local solution of the underlying QP problem. We then propose a new branch-and-cut algorithm that finds a globally optimal solution to the underlying QP problem within a pre-specified epsilon-tolerance by integrating the alternative direction method with semidefinite relaxation and disjunctive cut techniques. We establish the global convergence of the algorithm and estimate its complexity. Preliminary numerical results demonstrate that the proposed algorithm can effectively find a globally optimal solution to medium-scale QP instances in which the number of negative eigenvalues of the Hessian matrix in the objective function is less than or equals 20.

关键词： Quadratic programming branch-and-cut algorithm Alternative direction method Semidefinite relaxation Computational complexity

来源：评论

学校读者我要写书评

暂无评论

The Generalized Minimum Spanning Tree Problem:: Polyhedral analysis and branch-and-cut algorithm

引用

NETWORKS 2004年第2期43卷 71-86页

作者： Feremans, C Labbé, M Laporte, G Free Univ Brussels Serv Optimisat Inst Stat & Rech Operationnelle B-1050 Brussels Belgium Univ Limburg Fac Econ NL-6200 MD Maastricht Netherlands Univ Limburg Dept Business Adm NL-6200 MD Maastricht Netherlands

This article presents a branch-and-cut algorithm for the Generalized Minimum Spanning Tree Problem (GMSTP). Given an undirected graph whose vertex set is partitioned into clusters, the GMSTP consists of determining a minimum-cost tree including exactly one vertex per cluster. Applications of the GMSTP are encountered in telecommunications. An integer linear programming formulation is presented and new classes of valid inequalities are developed, several of which are proved to be facet-defining. A branch-and-cut algorithm and a tabu search heuristic are developed. Extensive computational experiments show that instances involving up to 160 or 200 vertices can be solved to optimality, depending on whether edge costs are Euclidean or random. (C) 2004 Wiley Periodicals, Inc.

关键词： generalized minimum spanning tree network design telecommunications polyhedral analysis branch-and-cut algorithm tabu search heuristic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：