Network flow interdiction on planar graphs

The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers.     

Heuristics for Multi-Stage Interdiction of Stochastic Networks

We describe and compare heuristic solution methods for a multi-stage stochastic network interdiction problem. The problem is to maximize the probability of sufficient disruption of the flow of information or goods in a network whose characteristics are not certain. In this formulation, interdiction subject to a budget constraint is followed by operation of the network, which is then followed by a second interdiction subject to a second budget constraint. Computational results demonstrate and compare the effectiveness of heuristic algorithms. This problem is interesting in that computing an objective function value requires tremendous effort. We exhibit classes of instances in our computational experiments where local search based on a transformation neighborhood is dominated by a constructive neighborhood.     

Computational experience with a difficult mixedinteger multicommodity flow problem

The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable. We describe computational experience with a cutting plane algorithm for this problem.This research was partially supported by a Presidential Young Investigator Award and the Center for Telecommunications Research, Columbia University.Corresponding author.     

Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem

The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient solution. In this work we propose a new approach that combines two existing procedures: the master problem of a simplicial decomposition algorithm is solved through the analytic center cutting plane method. Four variants are considered for solving the master problem. The third and fourth ones, which heuristically compute an appropriate initial point, provided the best results. The computational experience reported in the solution of real large-scale diagonal and difficult asymmetric problems—including a subset of the transportation networks of Madrid and Barcelona—show the effectiveness of the approach.     

A cutting plane procedure for the travelling salesman problem on road networks

A cutting plane algorithm for the exact solution of the symmetric travelling salesman problem (TSP) is proposed. The real tours on a usually incomplete road network, which are in general non-Hamiltonian, are characterized directly by an integer linear programming model. The algorithm generates special cutting planes for this model. Computational results for real road networks with up to 292 visiting places are reported, as well as for classical problems of the literature with up to 120 cities. Some of the latter problems have been solved for the first time with a pure cutting plane approach.     

The crane scheduling problem: models and solution approaches

In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small-sized instances, we develop a time-space network flow formulation with non-crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium-sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near-optimal solutions. For large-sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches.     

An arc-exchange decomposition method for multistage dynamic networks with random arc capacities

Multistage dynamic networks with random arc capacities (MDNRAC) have been successfully used for modeling various resource allocation problems in the transportation area. However, solving these problems is generally computationally intensive, and there is still a need to develop more efficient solution approaches. In this paper, we propose a new heuristic approach that solves the MDNRAC problem by decomposing the network at each stage into a series of subproblems with tree structures. Each subproblem can be solved efficiently. The main advantage is that this approach provides an efficient computational device to handle the large-scale problem instances with fairly good solution quality. We show that the objective value obtained from this decomposition approach is an upper bound for that of the MDNRAC problem. Numerical results demonstrate that our proposed approach works very well.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

The combined cutting stock and lot-sizing problem in industrial processes

Despite its great applicability in several industries, the combined cutting stock and lot-sizing problem has not been sufficiently studied because of its great complexity. This paper analyses the trade-off that arises when we solve the cutting stock problem by taking into account the production planning for various periods. An optimal solution for the combined problem probably contains non-optimal solutions for the cutting stock and lot-sizing problems considered separately. The goal here is to minimize the trim loss, the storage and setup costs. With a view to this, we formulate a mathematical model of the combined cutting stock and lot-sizing problem and propose a solution method based on an analogy with the network shortest path problem. Some computational results comparing the combined problem solutions with those obtained by the method generally used in industry—first solve the lot-sizing problem and then solve the cutting stock problem—are presented. These results demonstrate that by combining the problems it is possible to obtain benefits of up to 28% profit. Finally, for small instances we analyze the quality of the solutions obtained by the network shortest path approach compared to the optimal solutions obtained by the commercial package AMPL.     

An interior-point Benders based branch-and-cut algorithm for mixed integer programs

We present an interior-point branch-and-cut algorithm for structured integer programs based on Benders decomposition and the analytic center cutting plane method (ACCPM). We show that the ACCPM based Benders cuts are both pareto-optimal and valid for any node of the branch-and-bound tree. The valid cuts are added to a pool of cuts that is used to warm-start the solution of the nodes after branching. The algorithm is tested on two classes of problems: the capacitated facility location problem and the multicommodity capacitated fixed charge network design problem. For the capacitated facility location problem, the proposed approach was on average 2.5 times faster than Benders-branch-and-cut and 11 times faster than classical Benders decomposition. For the multicommodity capacitated fixed charge network design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the majority of the tested instances.     

Logistics distribution network design with two commodity categories

In this paper, we study the design of a logistics distribution network consisting of a supplier, a set of potential warehouses, and a set of retailers. There are commodities from two product categories, that is, category A and category B, flowing across the network. The demand for commodities in product category A is stable. The demand for commodities in product category B is highly uncertain. We show that the network design problem to distribute the commodities in both product categories can be formulated as the uncapacitated facility location problem with monotone submodular costs and tackled using a cutting plane algorithm. We propose a strongly polynomial time algorithm for the nonlinear discrete optimization problem, which must be solved in each iteration of the cutting plane algorithm. We also provide the computational results, and summarize the insights based on the proposed model and the solution algorithm.     

Two-level evolutionary approach to the survivable mesh-based transport network topological design

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be NP\mathcal{NP} -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.     

A Semidefinite Programming Based Polyhedral Cut and Price Approach for the Maxcut Problem

We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the algorithm. Cutting planes based on the polyhedral theory of the maxcut problem are then added to the primal problem in order to improve the SDP relaxation; this is the cutting phase of the algorithm. We provide computational results, and compare these results with a standard SDP cutting plane scheme. Research supported in part by NSF grant numbers CCR–9901822 and DMS–0317323. Work done as part of the first authors Ph.D. dissertation at RPI.     

A new path-based cutting plane approach for the discrete time-cost tradeoff problem

Determining discrete time-cost tradeoffs in project networks allows for the control of the processing time of an activity via the amount of non-renewable resources allocated to it. Larger resource allocations with associated higher costs reduce activities’ durations. Given a set of execution modes (time-cost pairs) for each activity, the discrete time-cost tradeoff problem (DTCTP) involves selecting a mode for each activity so that either: (i) the project completion time is minimized, given a budget, or (ii) the total project cost is minimized, given a deadline, or (iii) the complete and efficient project cost curve is constructed over all feasible project durations. The DTCTP is a problem with great applicability prospects but at the same time a strongly N P{\mathcal N}\,P-hard optimization problem; solving it exactly has been a real challenge. Known optimal solution methodologies are limited to networks with no more than 50 activities and only lower bounds can be computed for larger, realistically sized, project instances. In this paper, we study a path-based approach to the DTCTP, in which a new path-based formulation in activity-on-node project networks is presented. This formulation is subsequently solved using an exact cutting plane algorithm enhanced with speed-up techniques. Extensive computational results reported for almost 5,000 benchmark test problems demonstrate the effectiveness of the proposed algorithm in solving to optimality for the first time some of the hardest and largest instances in the literature. The promising results suggest that the algorithms may be embedded into project management software and, hence, become a useful tool for practitioners in the future.     

Convex hull representation of the deterministic bipartite network interdiction problem

We consider a version of the stochastic network interdiction problem modeled by Morton et al. (IIE Trans 39:3–14, 2007) in which an interdictor attempts to minimize a potential smuggler’s chance of evasion via discrete deployment of sensors on arcs in a bipartite network. The smuggler reacts to sensor deployments by solving a maximum-reliability path problem on the resulting network. In this paper, we develop the (minimal) convex hull representation for the polytope linking the interdictor’s decision variables with the smuggler’s for the case in which the smuggler’s origin and destination are known and interdictions are cardinality-constrained. In the process, we propose an exponential class of easily-separable inequalities that generalize all of those developed so far for the bipartite version of this problem. We show how these cuts may be employed in a cutting-plane fashion when solving the more difficult problem in which the smuggler’s origin and destination are stochastic, and argue that some instances of the stochastic model have facets corresponding to the solution of NP-hard problems. Our computational results show that the cutting planes developed in this paper may strengthen the linear programming relaxation of the stochastic model by as much as 25 %.     

Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks

In this paper, we consider the duty scheduling of sensor activities in wireless sensor networks to maximize the lifetime. We address full target coverage problems contemplating sensors used for sensing data and transmit it to the base station through multi-hop communication as well as sensors used only for communication purposes. Subsets of sensors (also called covers) are generated. Those covers are able to satisfy the coverage requirements as well as the connection to the base station. Thus, maximum lifetime can be obtained by identifying the optimal covers and allocate them an operation time. The problem is solved through a column generation approach decomposed in a master problem used to allocate the optimal time interval during which covers are used and in a pricing subproblem used to identify the covers leading to maximum lifetime. Additionally, Branch-and-Cut based on Benders’ decomposition and constraint programming approaches are used to solve the pricing subproblem. The approach is tested on randomly generated instances. The computational results demonstrate the efficiency of the proposed approach to solve the maximum network lifetime problem in wireless sensor networks with up to 500 sensors.     

A general approach for optimizing regular criteria in the job-shop scheduling problem

Even though a very large number of solution methods has been developed for the job-shop scheduling problem, a majority has been designed for the makespan criterion. In this paper, we propose a general approach for optimizing any regular criterion in the job-shop scheduling problem. The approach is a local search method that uses a disjunctive graph model and neighborhoods generated by swapping critical arcs. The connectivity property of the neighborhood structure is proved and a novel efficient method for evaluating moves is presented. Besides its generality, another prominent advantage of the proposed approach is its simple implementation that only requires to tune the range of one parameter. Extensive computational experiments carried out on various criteria (makespan, total weighted flow time, total weighted tardiness, weighted sum of tardy jobs, maximum tardiness) show the efficiency of the proposed approach. Best results were obtained for some problem instances taken from the literature.     

Jamming communication networks under complete uncertainty

This paper describes a problem of interdicting/jamming wireless communication networks in uncertain environments. Jamming communication networks is an important problem with many applications, but has received relatively little attention in the literature. Most of the work on network interdiction is focused on preventing jamming and analyzing network vulnerabilities. Here, we consider the case where there is no information about the network to be jammed. Thus, the problem is reduced to jamming all points in the area of interest. The optimal solution will determine the locations of the minimum number of jamming devices required to suppress the network. We consider a subproblem which places jamming devices on the nodes of a uniform grid over the area of interest. The objective here is to determine the maximum grid step size. We derive upper and lower bounds for this problem and provide a convergence result. Further, we prove that due to the cumulative effect of the jamming devices, the proposed method produces better solutions than the classical technique of covering the region with uniform circles.     

An integrated cutting stock and sequencing problem

In this paper an integrated problem formulated as an integer linear programming problem is presented to find an optimal solution to the cutting stock problem under particular pattern sequencing constraints. The solution uses a Lagrangian approach. The dual problem is solved using a modified subgradient method. A heuristic for the integrated problem is also presented. The computational results obtained from a set of unidimensional instances that use these procedures are reported.     

Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs

Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computational study of a disjunctive cutting plane method for stochastic mixed 0-1 programs that uses lift-and-project cuts based on the extensive form of the two-stage SMIP problem. An extension of the method based on where the data uncertainty appears in the problem is made, and it is shown how a valid inequality derived for one scenario can be made valid for other scenarios, potentially reducing solution time. Computational results amply demonstrate the effectiveness of disjunctive cuts in solving several large-scale problem instances from the literature. The results are compared to the computational results of disjunctive cuts based on the subproblem space of the formulation and it is shown that the two methods are equivalently effective on the test instances.