We consider the 0/1 Collapsing Knapsack Problem (CKP) and a generalization involving more than a capacity constraint (M-CKP). We propose a novel ILP formulation and a problem reduction procedure together with an exact...
详细信息
We consider the 0/1 Collapsing Knapsack Problem (CKP) and a generalization involving more than a capacity constraint (M-CKP). We propose a novel ILP formulation and a problem reduction procedure together with an exact approach. The proposed approach compares favorably to the methods available in the literature and manages to solve to optimality very large size instances particularly for CKP and 2-CKP. (C) 2016 Elsevier B.V. All rights reserved.
Suppose a graph G is given with two vertex-disjoint sets of vertices Z(1) and Z(2). Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z(1) and Z...
详细信息
Suppose a graph G is given with two vertex-disjoint sets of vertices Z(1) and Z(2). Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z(1) and Z(2), respectively? This problem is known as the 2-DISJOINT CONNECTED SUBGRAPHS problem. It is already NP-complete for the class of n-vertex graphs G = (V, E) in which Z(1) and Z(2) each contain a connected set that dominates all vertices in V\(Z(1)boolean OR Z(2)). We present an O* (1.2051(n)) time algorithm that solves it for this graph class. As a consequence, we can also solve this problem in O*(1.2051(n)) time for the classes of n-vertex P(6)-free graphs and split graphs. This is an improvement upon a recent O*(1.5790(n)) time algorithm for these two classes. Our approach translates the problem to a generalized version of hypergraph 2-coloring and combines inclusion/exclusion with measure and conquer. (C) 2011 Elsevier B.V. All rights reserved.
The complexity of the Bandpass problem is re-investigated. Specifically, we show that the problem with any fixed bandpass number Ba parts per thousand yen2 is NP-hard. Next, a row stacking algorithm is proposed for th...
详细信息
The complexity of the Bandpass problem is re-investigated. Specifically, we show that the problem with any fixed bandpass number Ba parts per thousand yen2 is NP-hard. Next, a row stacking algorithm is proposed for the problem with three columns, which produces a solution that is at most 1 less than the optimum. For the special case B=2, the row stacking algorithm guarantees an optimal solution. On approximation, for the general problem, we present an O(B (2))-algorithm, which reduces to a 2-approximation algorithm for the special case B=2.
The longest induced path problem consists in finding a maximum subset of vertices of a graph such that it induces a simple path. We propose a new exact enumerative algorithm that solves problems with up to 138 vertice...
详细信息
The longest induced path problem consists in finding a maximum subset of vertices of a graph such that it induces a simple path. We propose a new exact enumerative algorithm that solves problems with up to 138 vertices and 493 edges and a heuristic for larger problems. Detailed computational experiments compare the results obtained by the new algorithms with other approaches in the literature and investigate the characteristics of the optimal solutions.
This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The s...
详细信息
This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The simultaneous optimization of routing and handling costs is difficult, and the resulting loading patterns are hard to implement in practice. However, this option makes economical sense in contexts where the routing cost dominates the handling cost. We have proposed some simplified policies applicable to such contexts. The first is a two-phase heuristic in which the tour having minimum routing cost is initially determined by optimally solving an SVPDP, and the optimal handling policy is then determined for that tour. In addition, branch-and-cut algorithms based on integer linear programming formulations are proposed, in which routing and handling decisions are simultaneously optimized, but the handling decisions are restricted to three simplified policies. The formulations are strengthened by means of problem specific valid inequalities. The proposed methods have been extensively tested on instances involving up to 25 customers and hundreds of items. Our results show the impact of the handling aspect on the customer sequencing and indicate that the simplified handling policies favorably compare with the optimal one.
Compared to the non-cooperative mode, the cooperative mode is a powerful way to reduce operational cost in pickup and delivery service. In order to protect business sensitive information, sometimes participants are un...
详细信息
Compared to the non-cooperative mode, the cooperative mode is a powerful way to reduce operational cost in pickup and delivery service. In order to protect business sensitive information, sometimes participants are unwilling to open the customer's detailed information. Thus, we utilize the publishable trip scheduled results to compute the saved trips brought by cooperation. A mathematical model minimizing trips of cooperation is proposed. To obtain the exact solution, we define the cooperative trip set. We prove that only when cooperative trip set exists it is possible to save trips by cooperation. For a two-trip cooperative trip set, we exactly obtain the saved trips by enumerating all feasible cooperative cases. For a K-trip cooperative trip set, we propose an exact method to obtain the saved trips by decomposing it to at most K-1 two-trip cooperative trip sets. Computational complexity of the based-on-decomposition exact algorithm is O(N), where N is the total number of trips. Using the based-on-decomposition algorithm, we calculate the exact Shapley value to distribute profit. To empirically verify the exact method, we perform the extensive experiment cases of the real cooperative pickup and delivery service, i.e., "picking up and delivering customers to airport service" (PDCA). (C) 2017 Elsevier Ltd. All rights reserved.
Together with a newly developed method for avoiding collisions between links themselves, the BFA (Backtrack-Free path planning algorithm) has been implemented for calculating the paths of manipulators that are operate...
详细信息
Together with a newly developed method for avoiding collisions between links themselves, the BFA (Backtrack-Free path planning algorithm) has been implemented for calculating the paths of manipulators that are operated in three-dimensional workspaces. An approach to extending the BFA to an algorithm for calculating the paths of multiple manipulators cooperating to accomplish complicated tasks, in which multiple manipulators are considered as a single composite one with many links, is also discussed. The algorithm is backtrack-free and resolution-complete. Its computational volume is proportional to the total number of links and does not change drastically with the environments in which the manipulators are operated. Simulation results have demonstrated that the BFA allows efficient generation of paths for both single and multiple manipulators. (C) 2011 Wiley Periodicals, Inc. Electron Comm Jpn, 94(12): 1-11,2011;Published online in Wiley Online Library (***). DOI 10.1002/ecj.10392
In Euclidean plane geometry, Apollonius' problem is to construct a circle in a plane that is tangent to three given circles. We will use a solution to this ancient problem to solve several versions of the followin...
详细信息
In Euclidean plane geometry, Apollonius' problem is to construct a circle in a plane that is tangent to three given circles. We will use a solution to this ancient problem to solve several versions of the following geometric optimization problem. Given is a set of customers located in the plane, each having a demand for a product and a budget. A customer is satisfied if her total, travel and purchase, costs do not exceed the budget. The task is to determine location of production facilities in the plane and one price for the product such that the revenue generated from the satisfied customers is maximized.
The spare allocation problem in redundant RAM is to replace faulty rows/columns of memory cells with spare rows/columns. To solve the problem, comparison-based search tree structures were used in traditional exact alg...
详细信息
The spare allocation problem in redundant RAM is to replace faulty rows/columns of memory cells with spare rows/columns. To solve the problem, comparison-based search tree structures were used in traditional exact algorithms. These algorithms are not efficient for large problems because significant amounts of data have to be retained and copied in order to generate new partial solutions. Many data may need to be compared for the removal of each redundant partial solution. To overcome these drawbacks, an efficient algorithm is proposed in this paper. The algorithm transforms a spare allocation problem into Boolean functions, and the renowned BDD is used to manipulate them. Experimental results indicate that the proposed algorithm is very efficient in terms of speed and memory requirements. It may also be useful for problems which can be modeled as constraint bipartite vertex cover problems.
In this paper, we first give the definition of randomized time-varying knapsack problems () and its mathematic model, and analyze the character about the various forms of . Next, we propose three algorithms for : (1) ...
详细信息
In this paper, we first give the definition of randomized time-varying knapsack problems () and its mathematic model, and analyze the character about the various forms of . Next, we propose three algorithms for : (1) an exact algorithm with pseudo-polynomial time based on dynamic programming;(2) a 2-approximation algorithm for based on greedy algorithm;(3) a heuristic algorithm by using elitists model based on genetic algorithms. Finally, we advance an evaluation criterion for the algorithm which is used for solving dynamic combinational optimization problems, and analyze the virtue and shortage of three algorithms above by using the criterion. For the given three instances of , the simulation computation results coincide with the theory analysis.
暂无评论