We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Sev...
详细信息
We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2-edge-connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals-doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2-edge-connected Steiner network problem.
This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is b...
详细信息
This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors' previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness-tardiness problems, and most instances with 100 jobs of the former problem. (C) 2013 Elsevier B.V. All rights reserved.
We study techniques for solving the MAxSAT problem on instances in which the variable degree is bounded by 3. The problem is NP-hard. We show how resolution principle can be applied that converts an instance into an e...
详细信息
We study techniques for solving the MAxSAT problem on instances in which the variable degree is bounded by 3. The problem is NP-hard. We show how resolution principle can be applied that converts an instance into an equivalent instance in which the CNF formula becomes a linear CNF formula. We then show how more efficient branching strategies can be applied on linear CNF formulas. As applications, we present two algorithms: one of running time O*(1.194(k)) that solves the parameterized version of the problem, and the other of running time O*(1.237(n)) that solves the optimization version of the problem, both significantly improving previous best upper bounds. (C) 2016 Elsevier B.V. All rights reserved.
We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and an integer k with 1 <= k <= n, the problem asks to find a minimum-width annulus tha...
详细信息
We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and an integer k with 1 <= k <= n, the problem asks to find a minimum-width annulus that contains at least n - k input points. The k excluded points are considered as outliers of the input points. In this paper, we are interested in particular in annuli of three different shapes: circular, square, and rectangular annuli. For the three cases, we present first and improved algorithms to the problem. (C) 2019 Elsevier B.V. All rights reserved.
In this paper we study the multi-period vehicle routing problem with due dates. A supplier has to determine a distribution plan to visit a set of customers over a given planning horizon. Each customer is associated wi...
详细信息
In this paper we study the multi-period vehicle routing problem with due dates. A supplier has to determine a distribution plan to visit a set of customers over a given planning horizon. Each customer is associated with a release date and a due date, that is, the date at which the goods required by the customer become available at the supplier's depot, and the date by which the customer has to be visited, respectively. A fleet of capacitated vehicles is available at the depot to perform the distribution and the objective is to minimize the distribution costs and the costs related to delayed deliveries. New families of valid inequalities are presented that allow us to improve a branch-and-bound algorithm proposed in the literature. The new branch-and-bound algorithm reduces to 5.1% the optimality gap which is 12.1% for the known branch-and-bound on instances with one vehicle. A variable MIP neighborhood descent (VMND) algorithm is also presented, which speeds up the search for high quality solutions through a local search heuristic embedded in the branch-and-bound algorithm. Computational tests are performed to assess the quality of the VMND algorithm against the new branch-and-bound algorithm. The computational results show that the VMND algorithm improves 35 out of 80 solutions on instances with one vehicle, reducing the average optimality gap from 5.1% to 3.6%. It further matches the performance of the new branch-and-bound algorithm on another 35 instances. On instances with two and three vehicles the average optimality gap obtained by the VMND algorithm is 5.5% and 5.6%, respectively. (C) 2019 Elsevier Ltd. All rights reserved.
This paper addresses the problem of computing a minimum-width axis-aligned cubic shell enclosing a given set of n points in R-3. A cubic shell is a closed volume between two concentric and face-parallel cubes. Prior t...
详细信息
This paper addresses the problem of computing a minimum-width axis-aligned cubic shell enclosing a given set of n points in R-3. A cubic shell is a closed volume between two concentric and face-parallel cubes. Prior to this work, there was no known algorithm for this problem in the literature. We present the first nontrivial algorithm whose running time is O(n log(2) n) in the worst case. Our approach extends to higher dimension d > 3, resulting in an algorithm in O(n left perpendicular d/2 right perpendicular log(d-1) n) expected time. (C) 2019 Elsevier B.V. All rights reserved.
作者：
Sun, WeiYu, YangWang, JunweiLiaoning Univ
Sch Business Shenyang 110316 Liaoning Peoples R China Northeastern Univ
State Key Lab Synthet Automat Proc Ind Dept Intelligent Syst Engn Shenyang 110819 Liaoning Peoples R China Univ Hong Kong
Dept Ind & Mfg Syst Engn Pokfulam Rd Hong Kong Peoples R China
The heterogeneous green pickup and delivery problem (GPDP) aims to minimize carbon emissions of pickups and deliveries by a fleet of heterogeneous vehicles. We propose the first exact algorithm for solving the heterog...
详细信息
The heterogeneous green pickup and delivery problem (GPDP) aims to minimize carbon emissions of pickups and deliveries by a fleet of heterogeneous vehicles. We propose the first exact algorithm for solving the heterogeneous GPDP. This exact algorithm is based on a set partitioning model and the key characteristics of its optimal solution. We prove that the optimal solution is composed of the optimal trips of heterogeneous vehicles;thus, the solution space is significantly reduced by cutting the non-optimal trips. The proposed exact algorithm can rapidly find the optimal solution of the largest-scale instance from Li & Lim benchmarks and three types of vehicles. The exact algorithm is also validated by solving a practical case of heterogeneous GPDP in China. Based on the extensive experiments, we conclude an interesting managerial insight that heterogeneous vehicles can always effectively reduce carbon emissions except for two situations.
We investigate a real-world product distribution problem faced by a fast fashion retailer in Singapore. It is a generalization of the multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) proposed b...
详细信息
We investigate a real-world product distribution problem faced by a fast fashion retailer in Singapore. It is a generalization of the multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) proposed by Hernandez-Perez and Salazar-Gonzalez [15]. Each weekend the retailer forecasts the demand of each product for the next week. To ensure the inventory level equal to the forecast, the retailer schedules a fleet of vehicles to pick up or deliver products from/to each store at the beginning of each week. Shipping products from a store in surplus to another store in shortage is encouraged. For products that cannot be balanced among the stores, they are either picked up or delivered from/to the warehouse, which incurs a handling cost for each unit. The objective is to minimize the total travel distance as well as the total handling cost at the warehouse. To solve this problem, we propose a branch-and-price-and-cut algorithm based on a strong set-partitioning model, where an ad-hoc label-setting algorithm is designed to solve the pricing problem. The algorithm is tested on a set of instances generated according to a real-world database from the retailer and the m-PDTSP benchmark instances. Computational results show that our algorithm can optimally solve instances with 20 stores and over 100 products in one hour computational time. Moreover, it successfully solves several open m-PDTSP benchmark instances to optimality. (C) 2018 Elsevier Ltd. All rights reserved.
We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solut...
详细信息
We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range of penalties, on the identification of a core problem and on dynamic programming. The proposed approach turns out to be very effective in solving hard instances of PKP and compares favorably both to commercial solver CPLEX 12.5 applied to the ILP formulation of the problem and to the best available exact algorithm in the literature. Then we present a general inapproximability result and investigate several relevant special cases which permit fully polynomial time approximation schemes (FPTASs). (C) 2017 Elsevier B.V. All rights reserved.
The maximum edge-weight clique problem is to find a clique whose sum of edgeweight is the maximum for a given edge-weighted undirected graph. The problem is NP-hard and some branch-and-bound algorithms have been propo...
详细信息
The maximum edge-weight clique problem is to find a clique whose sum of edgeweight is the maximum for a given edge-weighted undirected graph. The problem is NP-hard and some branch-and-bound algorithms have been proposed. In this paper, we propose a new exact algorithm based on the branch-and-bound method. It assigns edge-weights to vertices and calculates upper bounds using vertex coloring. By some computational experiments, we confirmed our algorithm works fine. (C) 2020 Published by Elsevier B.V.
暂无评论