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

Integer programming model and branch-and-cut algorithm for the stack inbound and pre-marshalling problem

COMPUTERS & OPERATIONS RESEARCH 2023年第1期155卷

作者： Wu, Lebao Jiang, Zuhua Wang, Fuhua Shanghai Jiao Tong Univ Dept Ind Engn & Management Shanghai 200240 Peoples R China

The steel plate yard of shipbuilding separates the inbound and pre-processing operations, increasing the number of moves. This paper considers the mixed inbound and pre-processing operation and studies the stack inbound and pre-marshalling problem where storage and relocation moves can alternate. This problem aims to find a minimum operation to store all inbound plates while eliminating all blocking plates. We propose a novel integer programming model combining two moves in one time period. This model reduces the number of periods, thereby decreasing the model size, but requires extra constraints to avoid infeasible patterns. An exact branch-and-cut algorithm is introduced to tackle the influence of these extra constraints. This paper provides a new modeling approach for stack-related problems, and the experiments show that the proposed method outperforms other ILP-based methods in the literature.

关键词： Stack inbound Pre-marshalling problem Integer programming model branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm framework for the integrated aircraft hangar maintenance scheduling and staffing problem

A branch-and-cut algorithm framework for the integrated airc...

引用

2019第二届信息科学与系统国际会议

作者： Yichen Qin Felix T.S.Chan S.H.Chung T.Qu School of Electrical and Information Engineering Jinan University (Zhuhai Campus) Department of Industrial and Systems Engineering The Hong Kong Polytechnic University

The problem of maintenance scheduling and staffing at an aircraft heavy maintenance service company is studied. The objective is to establish an integrated aircraft maintenance schedule and maintenance technicians' rosters to fulfil different maintenance requests while minimizing the overall tardiness cost and labor cost. Upon receiving the maintenance requests, the hangar planner has to determine if the maintenance company is capable to serve the aircraft within the planning period, then allocate the parking stands and staying time of each aircraft in the hangar for the subsequent maintenance operations. Due to the complexity of the combinatorial problem, the commercial solver using branch-andbound algorithm is incapable to tackle with the medium-sized instance within reasonable time. To enhance the computational efficiency, a framework of branch-and-cut algorithm is proposed in this paper, aiming to decompose the original model and tighten the lower bound of the original problem by the effective cuts. The concept of combinatorial benders' decomposition algorithm is adopted in the development of algorithm.

关键词： Aircraft hangar maintenance hangar layout planning workforce scheduling branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A Heuristic Method Based on the branch and cut algorithm to the Transmission System Expansion Planning Problem

A Heuristic Method Based on the Branch and Cut Algorithm to ...

引用

General Meeting of the IEEE-Power-and-Energy-Society (PES)

作者： Sousa, Aldir S. Asada, Eduardo N. Univ Sao Paulo Dept Elect Engn Sao Carlos Sch Engn BR-13566590 Sao Carlos SP Brazil

ISBN: (纸本)9781457710018

In this paper we introduce a new heuristic algorithm to the centralized long-term transmission system expansion planning problem. The proposed method introduces cuts (new constraints) to the mathematical model to force generating feasible solutions to the DC model. The application of the strategy resulted in good solutions for the DC model. The computational results demonstrate the efficiency of the proposed method when applied to IEEE-24 bus system, Brazilian Southern System and Colombian system.

关键词： Transmission System Expansion Planning Heuristic Methods branch-and-Bound algorithm branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A Heuristic Method Based on the branch and cut algorithm to the Transmission System Expansion Planning Problem

A Heuristic Method Based on the Branch and Cut Algorithm to ...

引用

IEEE Power and Energy Society General Meeting

作者： Aldir S. Sousa Eduardo N. Asada Department of Electrical Engineering Sao Carlos School of Engineering University of Sao Paulo

ISBN: (纸本)9781457710001

关键词： Transmission System Expansion Planning Heuristic Methods branch-and-Bound algorithm branch-and-cut algorithm heuristic methods branch and bound algorithms power system expansion planning expansion plan Transmission systems branch cut Heuristic algorithms branches

来源：评论

学校读者我要写书评

暂无评论

branch-and-cut algorithms for the covering salesman problem

引用

RAIRO-OPERATIONS RESEARCH 2023年第3期57卷 1149-1166页

作者： Maziero, Lucas Porto Usberti, Fabio Luiz Cavellucci, Celso Univ Estadual Campinas Inst Comp Av Albert Einstein 1251 BR-13083852 Campinas SP Brazil

The Covering Salesman Problem (CSP) is a generalization of the Traveling Salesman Problem in which the tour is not required to visit all vertices, as long as all vertices are covered by the tour. The objective of CSP is to find a minimum length Hamiltonian cycle over a subset of vertices that covers an undirected graph. In this paper, valid inequalities from the generalized traveling salesman problem are applied to the CSP in addition to new valid inequalities that explore distinct aspects of the problem. A branch-and-cut framework assembles exact and heuristic separation routines for integer and fractional CSP solutions. Computational experiments show that the proposed framework outperformed methodologies from literature with respect to optimality gaps. Moreover, optimal solutions were proven for several previously unsolved instances.

关键词： Covering salesman problem integer linear programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

branch-and-cut algorithms for the bilinear matrix inequality eigenvalue problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2001年第1期19卷 79-105页

作者： Fukuda, M Kojima, M Tokyo Inst Technol Dept Math & Comp Sci Meguro Ku Tokyo 1528552 Japan

The optimization problem with the Bilinear Matrix Inequality (BMI) is one of the problems which have greatly interested researchers of system and control theory in the last few years. This inequality permits to reduce in an elegant way various problems of robust control into its form. However, in contrast to the Linear Matrix Inequality (LMI), which can be solved by interior-point-methods, the BMI is a computationally difficult object in theory and in practice. This article improves the branch-and-bound algorithm of Goh, Safonov and Papavassilopoulos (Journal of Global Optimization, vol. 7, pp. 365-380, 1995) by applying a better convex relaxation of the BMI Eigenvalue Problem (BMIEP), and proposes new branch-and-Bound and branch-and-cut algorithms. Numerical experiments were conducted in a systematic way over randomly generated problems, and they show the robustness and the efficiency of the proposed algorithms.

关键词： bilinear matrix inequality semidefinite programming branch-and-cut algorithm convex relaxation cut polytope

来源：评论

学校读者我要写书评

暂无评论

Discrete cutting path problems: a general solution framework and industrial applications

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2025年第3期63卷 949-969页

作者： Khachai, Daniil Battaia, Olga Petunin, Alexander Khachay, Michael Kedge Business Sch 680 Cours Liberat Talence France Ural Fed Univ Ekaterinburg Russia NN Krasovskii Inst Math & Mech Ekaterinburg Russia RAS Ivannikov Inst Syst Programming Moscow Russia

The optimal tool routing for cutting machines, also known as cutting path optimisation is an important problem in production research. This problem is relevant in various manufacturing environments such as aeronautic, automotive, garment and semiconductor industries. In this paper, we introduce a general solution framework for the discrete cutting Path Problem which includes: (i) the universal approach to reduce numerous settings of this problem to the appropriate auxiliary instances of the well-known Precedence Constrained Generalized Traveling Salesman Problem;(ii) the proposition of efficient solution methods for finding (sub-) optimal solutions. We carry out extensive computational experiments in order to evaluate performance of the proposed framework and the obtained results demonstrate its efficiency for real-life industrial instances.

关键词： cutting path problem endpoint cutting problem precedence constrained generalised travelling salesman problem branch-and-cut algorithm adaptive large neighbourhood search industry innovation and infrastructure

来源：评论

学校读者我要写书评

暂无评论

The Hamiltonian p-median problem: Polyhedral results and branch-and-cut algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第2期316卷 473-487页

作者： Barbato, Michele Gouveia, Luis Univ Milan Dipartimento Informat Giovanni Degli Antoni Via Celoria 18 I-20133 Milan Italy Univ Lisbon Fac Ciencias Ctr Matemat Aplicacoes Fundamentais & Invest Opera C6 Piso 4 P-1749016 Lisbon Portugal

In this paper we study the Hamiltonian p-median problem, in which we are given an edge-weighted graph and we are asked to determine p vertex-disjoint cycles spanning all vertices of the graph and having minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of edge variables. Each one of the families forbids solutions to the 2-factor relaxation of the problem that have less than.. cycles. The inequalities in one of the families are associated with large cycles of the underlying graph and generalize known inequalities associated with Hamiltonian cycles. The other family involves inequalities for the case with p = (sic)n/3(sic), associated with edge cuts and multi-cuts whose shores have specific cardinalities. We identify inequalities from both families that define facets of the polytope associated with the problem. We design branch-and-cut algorithms based on these families of inequalities and on inequalities associated with 2-opt moves removing sub-optimal solutions. Computational experiments on benchmark instances show that the proposed algorithms exhibit a comparable performance with respect to existing exact methods from the literature. Moreover the algorithms solve to optimality new instances with up to 400 vertices.

关键词： Combinatorial optimization Hamiltonian p-median problem Valid inequality Polyhedral study branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-AND-cut FOR THE NON-DISJOINT m-RING-STAR PROBLEM

引用

RAIRO-OPERATIONS RESEARCH 2014年第2期48卷 167-188页

作者： Fouilhoux, Pierre Questel, Auralien Univ Paris 06 Lab LIP6 F-75005 Paris France

In this article we study the realistic network topology of Synchronous Digital Hierarchy (SDH) networks. We describe how providers fulfill customer connectivity requirements. We show that SDH Network design reduces to the Non-Disjoint m-Ring-Star Problem (NDRSP). We first show that there is no two-index integer formulation for this problem. We then present a natural 3-index formulation for the NDRSP together with some classes of valid inequalities that are used as cutting planes in a branch-and-cut approach. We propose a polyhedral study of a polytope associated with this formulation. Finally, we present our branch-and-cut algorithm and give some experimental results on both random and real instances.

关键词： Realistic SDH network non-disjoint m-ring-star problem polyhedral approach branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

Two-phase branch-and-cut for the mixed capacitated general routing problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第1期243卷 17-29页

作者： Irnich, Stefan Lagana, Demetrio Schlebusch, Claudia Vocaturo, Francesca Johannes Gutenberg Univ Mainz Gutenberg Sch Management & Econ Chair Logist Management D-55128 Mainz Germany Univ Calabria Dept Mech Energy & Management Engn I-87036 Arcavacata Di Rende CS Italy ProCom GmbH D-52070 Aachen Germany Univ Calabria Dept Econ Stat & Finance I-87036 Arcavacata Di Rende CS Italy

The Mixed Capacitated General Routing Problem (MCGRP) is defined over a mixed graph, for which some vertices must be visited and some links must be traversed at least once. The problem consists of determining a set of least-cost vehicle routes that satisfy this requirement and respect the vehicle capacity. Few papers have been devoted to the MCGRP, in spite of interesting real-world applications, prevalent in school bus routing, mail delivery, and waste collection. This paper presents a new mathematical model for the MCGRP based on two-index variables. The approach proposed for the solution is a two-phase branch-and-cut algorithm, which uses an aggregate formulation to develop an effective lower bounding procedure. This procedure also provides strong valid inequalities for the two-index model. Extensive computational experiments over benchmark instances are presented. (C) 2014 Elsevier B.V. All rights reserved.

关键词： General routing problem Mixed graph Integer programming branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：