A novel approach to subgraph selection with multiple weights on arcs

In this paper, an extension of the minimum cost flow problem is considered in which multiple incommensurate weights are associated with each arc. In the minimum cost flow problem, flow is sent over the arcs of a graph from source nodes to sink nodes. The goal is to select a subgraph with minimum associated costs for routing the flow. The problem is tractable when a single weight is given on each arc. However, in many real-world applications, several weights are needed to describe the features of arcs, including transit cost, arrival time, delay, profit, security, reliability, deterioration, and safety. In this case, finding an optimal solution becomes difficult. We propose a heuristic algorithm for this purpose. First, we compute the relative efficiency of the arcs by using data envelopment analysis techniques. We then determine a subgraph with efficient arcs using a linear programming model, where the objective function is based on the relative efficiency of the arcs. The flow obtained satisfies the arc capacity constraints and the integrality property. Our proposed algorithm has polynomial runtime and is evaluated in rigorous experiments.

     

Perfect Circular Arc Coloring

The circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n² m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem.Partially supported by Project 02139 of Education Ministry of China.Supported in part by the Research Grants Council of Hong Kong (Project No. HKU7054/03P) and a seed funding for basic research of HKU.     

PLANNING FOR TRUCK FLEET SIZE IN THE PRESENCE OF A COMMON-CARRIER OPTION

This paper considers a class of network optimization problems in which certain directed arcs must be covered by a set of cycles. Our study was motivated by a distribution planning problem of a commercial firm that had to make deliveries over several origin-destination pairs (directed arcs) and that could service any demand arc by using a vehicle in its own fleet or by paying a common carrier. The problem is to determine an optimal fleet size and the resulting vehicle routes while satisfying maximum route-time restrictions. We formulate the problem, describe some approximate solution strategies, and discuss important implementation issues.     

协同运输的路线整合问题研究

本文研究协同运输的路线整合问题(CTRIP):允许所有的O-D流(运输任务)在规定的路线长度内任意采取直通运输、单点中转、两点中转的整合运输路线,整合运输的中枢路段在支付固定成本后可产生运费折扣,如何选择O-D流的整合路线使得总成本最小? CTRIP广泛应用于航空、物流、快递等领域的整合运输实践。论文构造了CTRIP的混合整数规划模型和Benders分解算法,实验显示,算法表现出非常好的计算绩效。最后,我们利用一个具体实例对CTRIP与已有研究展开了比较,结论显示CTRIP更能保证中枢路段的规模优势 。     

Complexity analysis for maximum flow problems with arc reversals

We provide a comprehensive study on network flow problems with arc reversal capabilities. The problem is to identify the arcs to be reversed in order to achieve a maximum flow from source(s) to sink(s). The problem finds its applications in emergency transportation management, where the lanes of a road network could be reversed to enable flow in the opposite direction. We study several network flow problems with the arc reversal capability and discuss their complexity. More specifically, we discuss the polynomial time algorithms for the maximum dynamic flow problem with arc reversal capability having a single source and a single sink, and for the maximum (static) flow problem. The presented algorithms are based on graph transformations and reductions to polynomially solvable flow problems. In addition, we show that the quickest transshipment problem with arc reversal capability and the problem of minimizing the total cost resulting from arc switching costs are NP\mathcal{NP} -hard.     

Reducibility of stochastic networks

This paper deals with the problem of reducing a stochastic network to one equivalent activity. The problem was motivated by the question of determining or approximating the probability distribution function of the duration of the longest or shortest path in a stochastic network. We define a particular reduction and use it to characterize the reducibility of such a network. The network can be reduced to one equivalent activity if the network does not have a special graph which we call the ‘interdictive graph’, or IG for short. If an IG is embedded in the network, the network is irreducible. In this case, its reduction becomes possible by duplicating some of the arcs in the irreducible network. The concept of duplicating an arc is introduced, then it is used to identify the arcs which can be duplicated. The reduction procedure is stated and illustrative examples are provided. An upper bound on the number of duplications is established.     

Using branch-and-price approach to solve the directed network design problem with relays

We present node-arc and arc-path formulations, and develop a branch-and-price approach for the directed network design problem with relays (DNDR). The DNDR problem can be used to model many network design problems in transportation, service, and telecommunication system, where relay points are necessary. The DNDR problem consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a directed path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. With the node-arc formulation, we can directly solve small DNDR instances using mixed integer programming solver. With the arc-path formulation, we design a branch-and-price approach, which is a variant of branch-and-bound with bounds provided by solving linear programs using column generation at each node of the branch-and-bound tree. We design two methods to efficiently price out columns and present computational results on a set of 290 generated instances. Results demonstrate that our proposed branch-and-price approach is a computationally efficient procedure for solving the DNDR problem.     

Exact and heuristic algorithms for solving the generalized minimum filter placement problem

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved. We formulate a mixed-integer programming model for the problem and derive valid inequalities for this model by identifying polynomially-solvable subgraphs of the communication network. We also present three heuristics for solving the filter placement problem and evaluate their performance against the optimal solution provided by the mixed-integer programming model. The authors gratefully acknowledge the comments of two anonymous referees, whose input led to an improved version of this paper. Dr. Smith gratefully acknowledges the support of the Office of Naval Research under Grant #N00014-03-1-0510 and the Defense Advanced Research Projects Agency under Grant #N66001-01-1-8925.     

A production model for deteriorating items with stochastic preventive maintenance time and rework process with FIFO rule

Due to unreliable production facility and stochastic preventive maintenance, deriving an optimal production inventory decision in practice is very complicated. In this paper, we develop a production model for deteriorating items with stochastic preventive maintenance time and rework using the first in first out (FIFO) rule. From our literature search, no study has been done on the above problem. The problem is solved using a simple search procedure; this makes it more practical for use by industries. Two case examples using uniform and exponential distribution preventive maintenance time are applied. Examples and sensitivity analysis are conducted for each case. The results show that rework and preventive maintenance time have significant affected the total cost and the optimal production time. This provides helpful managerial insights to help management in making smart decisions.     

A production model for deteriorating items with stochastic preventive maintenance time and rework process with FIFO rule

Due to unreliable production facility and stochastic preventive maintenance, deriving an optimal production inventory decision in practice is very complicated. In this paper, we develop a production model for deteriorating items with stochastic preventive maintenance time and rework using the first in first out (FIFO) rule. From our literature search, no study has been done on the above problem. The problem is solved using a simple search procedure; this makes it more practical for use by industries. Two case examples using uniform and exponential distribution preventive maintenance time are applied. Examples and sensitivity analysis are conducted for each case. The results show that rework and preventive maintenance time have significant affected the total cost and the optimal production time. This provides helpful managerial insights to help management in making smart decisions.     

On greedy and strategic evaders in sequential interdiction settings with incomplete information

We consider a class of sequential network interdiction problem settings where the interdictor has incomplete initial information about the network while the evader has complete knowledge of the network including its structure and arc costs. In each decision epoch, the interdictor can block (for the duration of the epoch) at most k arcs known to him/her. By observing the evader’s actions, the interdictor learns about the network structure and costs and thus, can adjust his/her actions in subsequent decision epochs. It is known from the literature that if the evader is greedy (i.e., the shortest available path is used in each decision epochs), then under some assumptions the greedy interdiction policies that block k-most vital arcs in each epoch are efficient and have a finite regret. In this paper, we consider the evader’s perspective and explore deterministic “strategic” evasion policies under the assumption that the interdictor is greedy. We first study the theoretical computational complexity of the evader’s problem. Then we derive basic constructive properties of optimal evasion policies for two decision epochs when the interdictor has no initial information about the network structure. These properties are then exploited for the design of a heuristic algorithm for a strategic evader in a general setting with an arbitrary time horizon and any initial information available to the interdictor. Our computational experiments demonstrate that the proposed heuristic outperforms the greedy evasion policy on several classes of synthetic network instances under either perfect or noisy information feedback. Finally, some interesting insights from our theoretical and computational results conclude the paper.     

Possible winner problems on partial tournaments: a parameterized study

We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D and a subset X of vertices, we are asked to add some arcs to D such that all vertices in X are included in the uncovered set. We focus on two parameterizations: parameterized by |X| and parameterized by the number of arcs to be added. In addition, we study a parameterized variant of the problem which is to determine whether all vertices of X can be included in the uncovered set by reversing at most k arcs. Finally, we study some parameterizations of a possible winner problem on partial tournaments, where we are given a partial tournament D and a distinguished vertex p, and asked whether D has a maximal transitive subtournament with p being the 0-indegree vertex. These parameterized problems are related to the Banks set. We achieve \(\mathcal {XP}\) results, \(\mathcal {W}\)-hardness results as well as \(\mathcal {FPT}\) results along with a kernelization lower bound for the problems studied in this paper.     

The mixed evacuation problem

A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then the goal of this problem is to find a minimum time limit such that we can send the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.     

Customer order scheduling to minimize total weighted completion time

In this paper we study the scheduling problem in which each customer order consists of several jobs of different types, which are to be processed on m facilities. Each facility is dedicated to the processing of only one type of jobs. All jobs of an order have to be delivered to the customer at the same time. The objective is to schedule all the orders to minimize the total weighted order completion time. While the problem has been shown to be unary NP-hard, we develop a heuristics to tackle the problem and analyze its worst-case performance.     

Iterative Converging Algorithms for Computing Bounds on Durations of Activities in Pert and Pert-Like Models

Since its invention in 1958, Program Evaluation and Review Technique (PERT) has been widely used during the planning, design, and implementation of projects. Pert models the activities of a project as a single source-single sink directed acyclic graph where nodes represent events (end or beginning of activities) and arcs activities. The maximum amount by which an activity can be delayed without delaying the overall project is called the slack. Critical tasks have zero slack whereas all noncritical tasks have positive slacks. Pert is a valuable tool in the management of large projects since it allows to compute the slack of each activity of the project. Such information may be crucial in avoiding cost overruns that would be caused by delays to critical activities and/or excessive delays to noncritical activities. What Pert fails to provide is how one should go about distributing remaining slack on noncritical activities while taking into consideration properties of the activities as well as precedence relationships among them, so as to have reasonable upper bounds on duration of all activities, critical or noncritical. In this paper we propose several algorithms for the distribution of slack on non-critical activities. We show that if one desires to distribute the remaining slack proportionally to the initially assigned activity durations then the problem is in P, and propose an algorithm of linear time complexity. However if one desires to use distribution functions other than the initial durations of activities, then the problem of slack distribution becomes NP-complete. Finding the maximal bounds corresponding to zero-slack solution at the sink requires iterative application of exponential algorithm. For that case we introduce an approximation algorithm of linear time complexity on each iteration. The algorithm iteratively increases bounds on durations of activities and converges to the zero-slack solution on all paths from the source node to the sink node in the Pert-like graph. The algorithms described in this paper were successfully applied to solving timing bounds problems in VLSI design.     

Minimizing number of tardy jobs on a single machine subject to periodic maintenance

This paper considers a single-machine scheduling problem with periodic maintenance. In this study, a schedule consists of several maintenance periods and each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the number of tardy jobs subject to periodic maintenance and nonresumable jobs. Based on the Moore's algorithm, an effective heuristic is developed to provide a near-optimal schedule for the problem. A branch-and-bound algorithm is also proposed to find the optimal schedule. Some important theorems associated with the problem are implemented in the algorithm. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

The maximum flow problem with disjunctive constraints

We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at least one arc has to carry flow in a feasible solution. It is convenient to represent the negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the arcs of the underlying graph, and whose edges encode the constraints. Analogously we represent the positive disjunctive constraints by a so-called forcing graph. For conflict graphs we prove that the maximum flow problem is strongly $\mathcal{NP}$ -hard, even if the conflict graph consists only of unconnected edges. This result still holds if the network consists only of disjoint paths of length three. For forcing graphs we also provide a sharp line between polynomially solvable and strongly $\mathcal{NP}$ -hard instances for the case where the flow values are required to be integral. Moreover, our hardness results imply that no polynomial time approximation algorithm can exist for both problems. In contrast to this we show that the maximum flow problem with a forcing graph can be solved efficiently if fractional flow values are allowed.     

Arcs in $$\mathbb Z^2_{2p}$$

An arc in \(\mathbb Z^2_n\) is defined to be a set of points no three of which are collinear. We describe some properties of arcs and determine the maximum size of arcs for some small n.     

Computational risk management techniques for fixed charge network flow problems with uncertain arc failures

We consider a formulation for the fixed charge network flow (FCNF) problem subject to multiple uncertain arc failures, which aims to provide a robust optimal flow assignment in the sense of restricting potential losses using Conditional Value-at-Risk (CVaR). We show that a heuristic algorithm referred to as Adaptive Dynamic Cost Updating Procedure (ADCUP) previously developed for the deterministic FCNF problem can be extended to the considered problem under uncertainty and produce high-quality heuristic solutions for large problem instances. The reported computational experiments demonstrate that the described procedure can successfully tackle both the uncertainty considerations and the large size of the networks. High-quality heuristic solutions for problem instances with up to approximately 200,000 arcs have been identified in a reasonable time.     

Maximizing misinformation restriction within time and budget constraints

Online social networks have become popular media worldwide. However, they also allow rapid dissemination of misinformation causing negative impacts to users. With a source of misinformation, the longer the misinformation spreads, the greater the number of affected users will be. Therefore, it is necessary to prevent the spread of misinformation in a specific time period. In this paper, we propose maximizing misinformation restriction (\(\mathsf {MMR}\)) problem with the purpose of finding a set of nodes whose removal from a social network maximizes the influence reduction from the source of misinformation within time and budget constraints. We demonstrate that the \(\mathsf {MMR}\) problem is NP-hard even in the case where the network is a rooted tree at a single misinformation node and show that the calculating objective function is #P-hard. We also prove that objective function is monotone and submodular. Based on that, we propose an \(1{-}1/\sqrt{e}\)-approximation algorithm. We further design efficient heuristic algorithms, named \(\mathsf {PR}\)-\(\mathsf {DAG}\) to show \(\mathsf {MMR}\) in very large-scale networks.