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

Arc-flow formulation and branch-and-price-and-cut algorithm for the bin-packing problem with fragile objects

COMPUTERS & OPERATIONS RESEARCH 2025年 173卷

作者： Wang, Sunkanghong Yao, Shaowen Zhang, Hao Liu, Qiang Wei, Lijun Guangdong Univ Technol Guangdong Prov Key Lab Comp Integrated Mfg Syst State Key Lab Precis Elect Mfg Technol & Equipment Guangzhou 510006 Peoples R China

This study introduces an arc-flow formulation and the first branch-and-price-and-cut (BPC) algorithm designed to solve the bin-packing problem with fragile objects (BPPFO). This variant of the bin-packing problem originates in the field of telecommunications, particularly in the allocation of cellular calls to frequency channels. The arc-flow formulation is inspired by previous studies and modifies the graph construction method to accommodate fragility constraints. We proved the correctness of this formulation and demonstrated its superiority in instances with small maximum fragility through extensive experiments. The proposed BPC algorithm leverages advanced cutting and packing techniques and incorporates innovative elements such as problem reduction, additional cutting planes, and a label-setting-based exact pricing algorithm. The experimental results demonstrate that the proposed BPC algorithm is highly competitive with the state-of-the-art algorithm for solving the BPPFO and can successfully solve several previously unsolved instances.

关键词： Packing Fragile objects exact algorithm Branch-and-price-and-cut Arc-flow

来源：评论

学校读者我要写书评

暂无评论

Dynamic Optimization of Tunnel Construction Scheduling in a Reverse Construction Scenario

引用

SYSTEMS 2025年第3期13卷 168-168页

作者： Wei, Jianying Liu, Yuming Lu, Xiaochun Zhao, Rong Wang, Gan Beijing Jiaotong Univ Sch Econ & Management Beijing 100044 Peoples R China China Acad Bldg Res Beijing 100013 Peoples R China

Tunnel construction, a critical aspect of railway engineering, is a repetitive process with distinct linear characteristics. While the Linear Scheduling Method (LSM) is widely used for scheduling optimization in linear projects, it struggles to accommodate dynamic construction sequences, reverse construction, and flexible team allocation. Minimizing the project duration is a primary objective in tunnel construction scheduling optimization. To optimize tunnel construction, we propose a duration-shortening method using additional working surfaces, adaptable to multi-segment and multi-team scenarios. A dynamic optimization model is developed for tunnel construction scheduling, integrating LSM, soft logic, Work Breakdown Structure (WBS), and Resource Breakdown Structure (RBS) within a dynamic scheduling framework. This model analyzes logical relationships, work continuity, temporal and spatial constraints, and resource variation, focusing on reverse construction. The Mixed-Integer Programming (MIP) approach is used to build the mathematical model, solved with both exact algorithms and Genetic algorithms (GA), and implemented in Python 3.12.7. Both algorithms perform well, with the GA excelling at handling complex constraints. Case studies confirm the method's effectiveness in optimizing durations, devising flexible schedules, and improving efficiency and practicality. This research provides both theoretical insights and practical guidance for tunnel construction scheduling optimization in railway engineering.

关键词： tunnel construction schedule dynamic optimization linear scheduling method soft logic work breakdown structure resource breakdown structure exact algorithm genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for the multiple depot vehicle scheduling problem with heterogeneous vehicles, split loads and toll-by-weight scheme

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2022年 168卷

作者： Li, Jiliu Qin, Hu Shen, Huaxiao Tong, Xialiang Xu, Zhou Sun Yat sen Univ Sch Business Guangzhou 510275 Peoples R China Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Peoples R China Huawei Noahs Ark Lab Hong Kong Peoples R China Hong Kong Polytech Univ Fac Business Hong Kong Peoples R China

We study a general version of the multiple depot vehicle scheduling problem, which is motivated by the practice of line-haul transportation in Chinese express delivery firms. In this problem, there are a set of trips to be served by a fleet of vehicles. Each trip has a certain amount of packages to be transported from an origin to a destination. Each vehicle can serve a sequence of trips, but it has to depart from and return to its base depot. We aim at assigning trips to vehicles such that all trips are fully served and the total transportation cost is minimized. This problem is general because several practical features have been considered, including heterogeneous vehicles, service time windows, split loads, and the toll-by-weight scheme. These features greatly broaden the applicability of this problem, but at the price of complicating it. We first formulate this problem into a nonlinear route based model, and then equivalently transform it into a linear route-cover based model. To solve the model, we propose two exact algorithms, namely, a branch-and-price and a branch-and-benders decomposition. Both algorithms are built upon a branch-and-bound framework. Particularly, we design a column generation procedure equipped with an efficient label setting method to solve subproblems involved in the two algorithms. Computational experiments are conducted on a set of random instances, and the results have substantiated the effectiveness and efficiency of our model and algorithms.

关键词： Vehicle scheduling problem Multiple depot Heterogeneous vehicles Split loads Toll-by-weight exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for finding minimum transversals in rank-3 hypergraphs

引用

JOURNAL OF algorithmS-COGNITION INFORMATICS AND LOGIC 2004年第2期51卷 107-121页

作者： Wahlström, M Linkoping Univ Dept Comp & Informat Sci TCSLab Linkoping Sweden

We present two algorithms for the problem of finding a minimum transversal in a hypergraph of rank 3, also known as the 3-Hitting Set problem. This problem is a natural extension of the vertex cover problem for ordinary graphs. The first algorithm runs in time O(1.6538(n)) for a hypergraph with n vertices, and needs polynomial space. The second algorithm uses exponential space and runs in time O(1.6316(n)). (C) 2004 Elsevier Inc. All rights reserved.

关键词： minimum transversal hypergraph 3-hitting set exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for the Hamiltonian cycle problem in planar graphs

引用

OPERATIONS RESEARCH LETTERS 2006年第3期34卷 269-274页

作者： Deineko, VG Klinz, B Woeginger, GJ Graz Univ Technol Inst Math B A-8010 Graz Austria Univ Warwick Sch Business Coventry CV4 7AL W Midlands England Tech Univ Eindhoven Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity O(c(root n)), where c is some fixed constant that does not depend on the instance. Furthermore, we show that under the exponential time hypothesis, the time complexity cannot be improved to O(c(o(root n))). (c) 2005 Elsevier B.V. All rights reserved.

关键词： Hamiltonian cycle exact algorithm planar separator theorem combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems

引用

THEORETICAL COMPUTER SCIENCE 2017年第PartA期657卷 86-97页

作者： Xiao, Mingyu Kou, Shaowei Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China

A dissociation set in a graph G = (V, E) is a vertex subset D such that the subgraph G[D] induced on D has vertex degree at most 1. A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. A vertex set D is a dissociation set if and only if V \ D is a 3-path vertex cover. There are many applications for dissociation sets and 3-path vertex covers. However, it is NP-hard to compute a dissociation set of maximum size or a 3-path vertex cover of minimum size in graphs. Several exact algorithms have been proposed for these two problems and they can be solved in O*(1.4658(n)) time in n-vertex graphs. In this paper, we reveal some interesting structural properties of the two problems, which allow us to solve them in O*(1.4656(n)) time and polynomial space or O*(1.3659(n)) time and exponential space. (C) 2016 Elsevier B.V. All rights reserved.

关键词： exact algorithm Graph algorithm Dissociation number 3-path vertex cover Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for the two-dimensional guillotine knapsack

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第1期39卷 48-53页

作者： Dolatabadi, Mohammad Lodi, Andrea Monaci, Michele Univ Bologna DEIS I-40136 Bologna Italy Univ Ferdowsi Fac Math & Stat Mashhad Iran Univ Padua DEI I-35131 Padua Italy

The two-dimensional knapsack problem requires to pack a maximum profit subset of "small" rectangular items into a unique "large" rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem. In this paper we present a recursive exact procedure that, given a set of items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are computationally evaluated on well-known benchmark instances from the literature. The C++ source code of the recursive procedure is available upon request from the authors. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Two-dimensional knapsack Guillotine packing exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for the Bottleneck Steiner Tree Problem

引用

algorithmICA 2011年第4期61卷 924-948页

作者： Bae, Sang Won Choi, Sunghee Lee, Chunseok Tanigawa, Shin-ichi Kyonggi Univ Dept Comp Sci Suwon South Korea Korea Adv Inst Sci & Technol Div Comp Sci Taejon 305701 South Korea Kyoto Univ Math Sci Res Inst Kyoto Japan

Given n points, called terminals, in the plane a"e(2) and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from a"e(2) and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on a"e(2), usually, the Euclidean or the L (1) metric. This problem is known to be NP-hard. In this paper, we study this problem in the L (p) metric for any 1a parts per thousand currency signpa parts per thousand currency signa, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)a <...nlog (2) n time for the L (1) and the L (a) metrics, and the first exact algorithm for the L (p) metric for any fixed rational p with 1 < p < a whose time complexity is f(k)a <...(n (k) +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L (2) metric.

关键词： Steiner point Bottleneck Steiner tree exact algorithm Fixed-parameter tractability Computational geometry Optimization

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for maximum independent set

引用

INFORMATION AND COMPUTATION 2017年第Part1期255卷 126-146页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Sichuan Peoples R China Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto Japan

We show that the maximum independent set problem on an n-vertex graph can be solved in 1.1996(n)n(0)(1) time and polynomial space, which even is faster than Robson's 1.2109(n)n(0)(1) -time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of 1.1893(n)n(0)(1) and 1.1970(n)n(0)(1), respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analysis on the structure of bounded-degree graphs. (C) 20 17 Elsevier Inc. All rights reserved.

关键词： exact algorithm Independent set Graph Polynomial-space Branch-and-reduce Measure-and-conquer Amortized analysis

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for weak Roman domination

引用

DISCRETE APPLIED MATHEMATICS 2018年 248卷 79-92页

作者： Chapelle, Mathieu Cochefert, Manfred Couturier, Jean-Francois Kratsch, Dieter Letourneur, Romain Liedloff, Mathieu Perez, Anthony IFTS CReSTIC Pole Haute Technol F-08000 Charleville Mezieres France Univ Lorraine Lab Informat Theor & Appl F-57045 Metz 01 France Univ Orleans INSA Ctr Val Loire LIFO EA 4022 FR-45067 Orleans France

We consider the WEAK ROMAN DOMINATION problem. Given an undirected graph G = (V, E), the aim is to find a weak Roman domination function (wrd-function for short) of minimum cost, i.e. a function f : V -> {0, 1, 2} such that every vertex v is an element of V is defended (i.e. there exists a neighbor u of v, possibly u = v, such that f (u) >= 1) and for every vertex v is an element of V with f (v) = 0 there exists a neighbor u of v such that f (u) >= 1 and the function f(u -> v) defined by f(u -> v)(v) = 1, f(u -> v)(u) = f (u) - 1 and f(u -> v)(x) = f(x) otherwise does not contain any undefended vertex. The cost of a wrd-function f is defined by cost(f) = Sigma(v is an element of V)f(v). The trivial enumeration algorithm runs in time O*(3(n)) and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in O*(2(n)) time needing exponential space, and then describe an O*(2.2279(n)) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the RED-BLUE DOMINATING SET problem. Moreover we show that the problem can be solved in linear-time on interval graphs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： exact algorithm Graph algorithm Roman domination Interval graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：