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 orig...
详细信息
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.
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 linea...
详细信息
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.
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 ...
详细信息
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.
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 ordina...
详细信息
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.
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 sho...
详细信息
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.
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 v...
详细信息
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.
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....
详细信息
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.
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 minimize...
详细信息
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.
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 algori...
详细信息
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.
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} ...
详细信息
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.
暂无评论