Network interdiction to minimize the maximum probability of evasion with synergy between applied resources

In this paper, we model and solve the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Inspired primarily by operations to coordinate Iraqi and U.S. security forces seeking to interdict an evader attempting to avoid detection while transiting part of the nearly rectilinear street network in East Baghdad, this study motivates and examines either linear or concave (nonlinear) synergy relationships between the applied resources within our formulations. We also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. Our empirical results confirm the value of tactical patience regarding decisions on the covert utilization of resources for network interdiction. Furthermore, considering non-integral and integral resource allocations, we identify (theoretically and empirically) parametric characteristics of instances that exhibit the relative worth of employing partially covert operations. Under the relatively more practical scenario involving integral resource allocations, we demonstrate that the composite overt-covert strategy of deploying resources has a greater potential to improve over a purely overt resource deployment strategy, both with and without synergy, particularly when costs are positively correlated, resources are plentiful, and a sufficiently high ratio of covert to overt resources exists. Moreover, should an interdictor be able to ascertain an optimal evader path, the potential and magnitude of this relative improvement for the overt-covert resource allocation strategy is significantly greater.     

Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization

Disjunctive Programs can often be transcribed as reverse convex constrained problems with nondifferentiable constraints and unbounded feasible regions. We consider this general class of nonconvex programs, called Reverse Convex Programs (RCP), and show that under quite general conditions, the closure of the convex hull of the feasible region is polyhedral. This development is then pursued from a more constructive standpoint, in that, for certain special reverse convex sets, we specify a finite linear disjunction whose closed convex hull coincides with that of the special reverse convex set. When interpreted in the context of convexity/intersection cuts, this provides the capability of generating any (negative edge extension) facet cut. Although this characterization is more clarifying than computationally oriented, our development shows that if certain bounds are available, then convexity/intersection cuts can be strengthened relatively inexpensively.     

Enhanced intersection cutting-plane approach for linear complementarity problems

In this paper, we develop an enhanced intersection cutting-plane algorithm for solving a mixed integer 0–1 bilinear programming formulation of the linear complementarity problem (LCP). The matrixM associated with the LCP is not assumed to possess any special structure, except that the corresponding feasible region is assumed to be bounded. A procedure is described to generate cuts that are deeper versions of the Tuy intersection cuts, based on a relaxation of the usual polar set. The proposed algorithm then attempts to find an LCP solution in the process of generating either a single or a pair of such strengthened intersection cuts. The process of generating these cuts involves a vertexranking scheme that either finds an LCP solution, or else these cuts eliminate the entire feasible region leading to the conclusion that no LCP solution exists. Computational experience on various test problems is provided.This material is based upon work supported by the National Science Foundation under Grant No. DMII-9121419 to the first author and Grant No. DMII-9114489 to the third author. The authors gratefully acknowledge the constructive suggestions of a referee that helped focus the approach and its presentation.     

RLT-POS: Reformulation-Linearization Technique-based optimization software for solving polynomial programming problems

In this paper, we introduce a Reformulation-Linearization Technique-based open-source optimization software for solving polynomial programming problems (RLT-POS). We present algorithms and mechanisms that form the backbone of RLT-POS, including constraint filtering techniques, reduced RLT representations, and semidefinite cuts. When implemented individually, each model enhancement has been shown in previous papers to significantly improve the performance of the standard RLT procedure. However, the coordination between different model enhancement techniques becomes critical for an improved overall performance since special structures in the original formulation that work in favor of a particular technique might be lost after implementing some other model enhancement. More specifically, we discuss the coordination between (1) constraint elimination via filtering techniques and reduced RLT representations, and (2) semidefinite cuts for sparse problems. We present computational results using instances from the literature as well as randomly generated problems to demonstrate the improvement over a standard RLT implementation and to compare the performances of the software packages BARON, COUENNE, and SparsePOP with RLT-POS.     

Enumeration Approach for Linear Complementarity Problems Based on a Reformulation-Linearization Technique

In this paper, we consider the linear complementarity problem (LCP) and present a global optimization algorithm based on an application of the reformulation-linearization technique (RLT). The matrix M associated with the LCP is not assumed to possess any special structure. In this approach, the LCP is formulated first as a mixed-integer 0–1 bilinear programming problem. The RLT scheme is then used to derive a new equivalent mixed-integer linear programming formulation of the LCP. An implicit enumeration scheme is developed that uses Lagrangian relaxation, strongest surrogate and strengthened cutting planes, and a heuristic, designed to exploit the strength of the resulting linearization. Computational experience on various test problems is presented.     

A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations

This paper considers the class scheduling and timetabling problem faced at Kuwait University (KU). The principal focus is to design efficient class offering patterns while taking into consideration newly imposed gender policies. We formulate a mathematical programming model that assigns offered classes to time-slots and addresses gender issues by defining appropriate surrogate constraints along with objective penalty terms. The model aims to enhance existing manual scheduling and timetabling approaches that are often accompanied with arduous combinatorial tasks such as resolving class conflicts, dealing with parking and traffic congestion, and ensuring an efficient utilization of facility and human resources. This modeling approach emphasizes the generation of flexible class timetables for students, and the efficient utilization of available facility resources. Computational results based on a number of case studies related to Kuwait University reveal that this approach yields improved schedules in terms of offering patterns and class conflicts.     

A leader-follower model and analysis for a two-stage network of oligopolies

This paper is concerned with the existence, uniqueness and computation of leader-follower equilibrium solutions for an industry involved with two major stages of production. We assume that there exists one set of firms performing the first stage of production, which produces a semi-finished product. This semi-finished product is converted to a final good by a second set of firms performing the second stage of production. Furthermore, also competing in the final product market is a third set of firms, which are vertically integrated through the two stages of production and which are assumed to lead the second set of firms by explicitly considering the reaction or response of these latter firms to their own outputs. We model such an industry as a two-stage network of oligopolies, and define equilibrium solutions based on assumed market structures. Our analysis examines the existence and uniqueness of such equilibrium solutions, characterizes the nature of the production strategies of the various firms at an equilibrium, and prescribes algorithms to compute such solutions. This provides the machinery required to perform sensitivity analyses for studying the effects of various mergers or integrations on individual firm profits, and on the industry outputs and prices at equilibrium. The presentation is self-contained, and does not necessarily require any significant prior preparation in economic theory on the part of the reader.This paper is based on work done for the Minerals and Mining Resources Research Institute, under the sponsorship of the Bureau of Mines, Department of the Interior.     

A new reformulation-linearization technique for bilinear programming problems

This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This RLT process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.