SUMMARY OF RESEARCH CONTRIBUTIONS
Google Scholar Profile:
http://scholar.google.com/citations?user=0VsVEfQAAAAJ
The list of 353 refereed journal publications given below (in print or accepted to appear) make the following contributions to the Operations Research/Mathematical Programming literature (H-index = 85 and total citations = 45,236 including books, as of January, 2025 – see above link for update):
(A) Nonconvex (Including Integer) Programming: Published a research monograph on Disjunctive Programming (with C. M. Shetty) containing existing, and a significant amount of original, material on the subject. This book deals with optimization problems involving logical constraints, and subsumes a wide variety of nonconvex problems arising in a host of applications, including zero-one integer programming problems. An updated discussion appears in an encyclopedia article [01i]. Also, see the book on the Reformulation-Linearization Technique (RLT) listed in Section IV, which unifies the field of discrete and continuous nonconvex optimization, and presents theory and applications on constructing tight relaxations and convex hull representations. This methodology has enabled the solution of many open, challenging problems for the very first time, and in general, has enhanced the solution capability of many hard classes of nonconvex problems. Historical and encyclopedic treatises on the RLT development appear in [07e, 08r, 11k, 13j].
Contributions stemming from this work evolve around the generation of deep non-dominated cuts [80d, 83e], and the characterization of facets of the convex hull of feasible solutions for special disjunctive sets [85a, 86a]. These cuts have been imbedded in algorithms for various classes of problems including facial disjunctive programs [82a], and the bilinear programming problem for which the first implementable finitely convergent algorithm was developed based on a novel exploration of the faces of the underlying polyhedron [80b]. (Further research on bilinear problems is cited below.) Some novel schemes for converting inherently infinitely convergent algorithms to exact, finitely convergent methods have been devised for several classes of nonconvex optimization problems [00h]. Other, extreme point and generalized lattice point programming problems have also been analyzed as special cases of disjunctive programs [85g, 85i, 86g]. Computational results have established the superiority of the algorithms developed for these problems over other competing procedures. Also, a general convergence theory has been developed that provides insights into factors that contribute toward finite convergence, along with striking counter examples to show non-convergence of some existing algorithms that fail to recognize one or more such factors, hence resolving some open issues about the convergence of these algorithms [85b]. Another nonconvex program analyzed is the Reverse Convex Programming Problem for which polyhedral characterizations of the closure convex hull of feasible points have been developed under nondifferentiability, along with a characterization of facetial convexity cuts [87c]. Insightful canonical duality-based relationships between global optimization and nonconvex mechanics are discussed in [09l ], and related optimality conditions for nonconvex programs with connections to Lagrangian duality [09f] and canonical dual solutions for fixed-charge quadratic programs [10h] have been developed.
In the area of integer programming, tighter than existing linearizations have been developed for Mixed Integer Bilinear Programming Problems and Zero-One Quadratic Programs [86d, 90a, 93f], including polyhedral analyses and insights into quadratic versus linear order linearizations for the latter class of problems [07g]. This has led to the development of a novel Reformulation-Linearization Technique (RLT) for generating a hierarchy of relaxations for pure and mixed-integer, linear and polynomial, zero-one and general integer programming problems, spanning the spectrum from the linear programming to the convex hull representations [90c, 94a, 94f, 96d, 98i, 01h, 02f, 05g, 09c]. Many results, examples, and conjectures related to the computationally important first-level relaxation are presented in [00b]. Specializations for exploiting frequently occurring structures such as GUB, VUB, partitioning and covering constraints, as well as conditional logic-based tightening procedures for generating strong reformulations have been investigated [95c, 98a]. An extension of RLT to generate a hierarchy of relaxations leading to the convex hull representation for mixed-discrete, semi-infinite, and convex programming problems is developed in [09c]. The RLT also facilitates the characterization and derivation of facet inequalities. Such facetial characterizations have been obtained for the GUB constrained knapsack problem [95c] and the Boolean quadric polytope [95b]. Related theoretical developments along with computational techniques designed to take advantage of such structures are presented in detail in the context of solving mixed-integer bilinear programming problems in [93f]. A novel extension of Benders’ methodology for solving stochastic integer programs having mixed-integer recourse decisions has been developed for the first time, relying on RLT constructs for generating cuts that characterize the value function, leading to a finitely convergent procedure [02e]. A combination of Benders’ type decomposition with branch-and-cut strategies, along with the related convergence theory, has also been developed for two-stage stochastic mixed-integer programs [06b, 06c]. Insightful connections between RLT and disjunctive convexification methods for mixed-integer stochastic programming [09k], and specialized effective algorithms for two-stage stochastic programs arising in the contexts of airline fleet assignment [08a], and hierarchical multiple risk management [09a] have been explored. An interesting problem in robotics that involves the determination of the first collision (if any) between polyhedral bodies moving along piecewise linear trajectories with rotations has been analyzed [01g], where a convex hull representation using RLT is shown to yield a significant improvement over previous integer programming approaches. For column generation approaches based on set partitioning formulations, a novel complementary column generation feature for deriving tight upper bounds and a lower bounding mechanism are proposed in [09i]. Other advances in model formulations via the use of hierarchical constraints to combat symmetry, with applications to factory noise-dosage reduction, telecommunications networks, and cooling facility design problems are presented in [01b]. A new approach for defeating symmetry by using objective perturbations based on a preemptive priority approach is introduced in [11c]. An ideal convex hull representation has also been developed for modeling separable lower semi-continuous functions [01c]. Additionally, ideal representations for lexicographic orderings arising in binary expansions of integer variables have been studied [12a]. A detailed polyhedral study, including the derivation of several classes of facets, has been conducted for a new class of Generalized Vertex Packing problems that arise in aircraft collision risk analysis [05a, 06a]. New classes of Surrogate-Knapsack and Chvatal-Gomory cuts [97e], convexification cuts based on partial convex hull representations [05j], Chvatal-Gomory Tier cuts [05h], second-order knapsack cover cuts [08c], higher-order cover cuts based on knapsack constraints and additional sets of bounding inequalities [08d], higher-order RLT or disjunctive cuts [12h], and reduced-RLT cuts based on a dynamic Lagrangian dual construct [12j] have been developed. In computational tests, these cuts show promise of supporting the arsenal of existing cuts that are implemented in commercial software. Another general class of cutting planes, called Foundation-Penalty (FP) Cuts, has been proposed, predicated on a foundation function and the derivation of associated penalties to induce a cut [03c]. A particularly interesting special case of Balanced Foundation Penalty Cuts has also been studied [07k]. Many other classes of cuts such as disjunctive, convexity, and mixed-integer rounding cuts can be interpreted in the light of FP cuts. For fixed-charge problems having an embedded nested constraint structure, several classes of facetial and strong valid inequalities have been derived [05i].
The Reformulation-Linearization Technique (RLT) has also been specialized to solve bilinear programming problems, for which it has been shown to construct closure convex hull representations in special cases, and strong relaxations in general. Computational experience exhibits a significant advantage over competing methods [92e]. A bilinear formulation of the linear complementarity problem (LCP) has been exploited to design a novel enhanced polar cutting plane procedure that can solve a general LCP via the generation of a single or a pair of cutting planes [96g]. An alternative mixed-integer bilinear programming viewpoint of this same formulation has been used to design an effective algorithm for this problem based on the generation of tight linear programming relaxations through an application of RLT [98e]. Various approaches have been developed for Mathematical Programs with Equilibrium Constraints (MPECs), including methods using complementarity-based partitioning and disjunctive cuts [06n] and complementarity-induced active set [07b] techniques. A discussion note on algorithms for linear complementarity problems appears in [12k]. The experience of using RLT to solve continuous bilinear programs has been extended to solve nonlinear polynomial programming problems [92a, 97h, 02f] including problems having rational exponents [98b]. For the class of polynomial problems, the theoretical dominance of the proposed RLT process over that applied to Shor's sequential quadrification scheme has been demonstrated [97c]. In particular, for indefinite quadratic programs, a special Reformulation-Convexification variant has been developed that retains a degree of nonlinearity in the convex programming relaxations [95e]. Promising results have been obtained, including the solution of a test problem not previously solved to optimality. A significant enhancement in the strength of RLT relaxations, as well as in its computational effectiveness, has been obtained and demonstrated through the development of a new class of (polynomially derived) semidefinite cuts [02d] and v-semidefinite cuts [12c], the generation of a new class of bound-grid-factor RLT valid inequalities [11e], the design of compact but tight RLT relaxations for polynomial programming problems using a reduced basis strategy [12b], and a theoretically valid filtering of RLT bound-factor constrains that ensures convergence to global optimality for polynomial programming problems [13g]. The RLT methodology has been extended to solve a wider class of factorable programming problems by interspersing an additional step that generates nonconvex polynomial approximations to the underlying original factorable problem [01a]. Encouraging results, including the solution of test problems not previously solved to optimality are presented. Specialized, effective, and theoretically convergent, RLT-based global optimization methods have been developed for both hard and fuzzy clustering problems and have been demonstrated to yield significantly superior results to both existing popular methods as well as commercial solvers [05e, 05f]. Convex envelope characterizations over special polytopes have also been developed for bilinear functions [90d] and for various other production and design mixed-integer programming problems [96f]. Other convex envelope characterizations for multilinear functions over the unit hypercube and over special discrete sets have also been developed [97j]. Models and algorithms for applying the RLT technology to risk management problems have been proposed [95a, 04c]. An integer fractional programming model and algorithm has been developed for low probability-high consequence considerations in a multi-objective approach to risk management [97d]. Novel models and convergence analyses for determining optimal strategies for reducing system failure probabilities and mitigating consequences in the context of event and decision tree optimization problems have been proposed [08b, 11a]. A nested event tree optimization approach with applications to combating terrorism has also been developed [10b]. Two-stage stochastic models and effective solution strategies have been designed for risk threshold and hierarchical multiple risk scenarios [09a]. Furthermore, using the RLT methodology, a first ever global optimization scheme has been developed for solving water distribution network design problems [90h, 93g, 96b, 97f, 98h, 01d]. New improved solutions to standard test problems have been discovered by determining optimal solutions in this fashion, including the solution to optimality of two cases that had been heretofore unsolved for two-three decades. An analysis for determining a threshold break rate for aiding in pipeline replacement decisions has also been conducted [02h]. A new class of algorithms, referred to as pseudo-global optimization methods, which combines response surface methodology with the RLT technology for solving complex problems that might even involve black-box functions, has been developed and applied to the solution of a containership design problem [03e]. The results exhibit a capability of generating significantly improved designs in comparison with a standard commercial package. Also, an inverse reliability approach for designing under uncertainty with application to an automobile piston design problem is discussed in [07d]. Surveys of these RLT methodologies for continuous nonconvex optimization appear in [05k, 08r]. A public domain RLT-based Polynomial Optimization Software (POS) has also been developed for solving polynomial optimization problems using a variety of valid inequalities and semidefinite cuts along with reduced basis techniques and compact representations [16a].
Algorithmic strategies and procedures have been developed for nonlinear mixed-integer programming problems and large-scale mixed-integer linear programming problems, including decomposition strategies [81d], strategies for selecting nodes and branching variables in enumerative procedures [86e], and strategies for designing Lagrangian relaxations, recovering primal solutions, and for operating conjugate or deflected subgradient optimization procedures [88b, 89a, 96e, 00a, 01f, 04a, 06j, 06m, 08e]. The RLT procedure has also been specialized for set partitioning problems for which tight relaxations have been derived. These relaxations are shown to subsume existing constraint generation and strengthening schemes for this class of problems [96a]. Enhanced reformulations for the Asymmetric Traveling Salesman Problem employing (lifted) Miller-Tucker-Zemlin subtour elimination constraints, with and without precedence structures, have been derived using RLT constructs [02b]. An alternative new polynomial length formulation of this problem is described in [05c]. Further tightened polynomial length formulations using RLT-based lifting and path and flow-based constraints have been developed [06e], and several alternative models for the multiple asymmetric traveling salesmen problem with and without precedence constraints [14j], as well as for the high-multiplicity traveling salesman problem [11j, 18b] and the fixed-destination multi-depot traveling salesman problem with load balancing [22], have been analyzed. An effective technique for generating subtour-elimination constraints from integer solutions for the single and multiple asymmetric traveling salesman problems has also been proposed [18a]. A special application to the airline gate assignment problem has been studied [94e] where the RLT has been used to study the special partitioning and packing substructures in order to generate tight relaxations. Likewise, special model formulations, classes of valid inequalities, and algorithms have been developed for the local access transport area telecommunication network design problem [00f], and an intra-ring synchronous optical network design problem [00i, 00k]. Some novel persistency results have also been developed for unconstrained and constrained, linear and polynomial pseudo-Boolean programming problems. These results indicate conditions under which variables that take on binary values in RLT relaxations will persist to take on these same values at optimality [98c]. Insights into how RLT achieves a tighter representation than the elementary lift-and-project closure have also been provided [15d]. Several algorithms have been developed for the quadratic assignment problem, including a polynomial-time heuristic, which have discovered some of the best known solutions to (large) standard test problems in the literature [78b, 80c, 82e, 86h]. Network interdiction problems to maximize the minimum flow of an evader, or to minimize the maximum probability of evasion, under novel considerations of superadditive synergy among the resources utilized by the interdictor have also been studied [12d]. Extensions of such interdiction problems to consider a combination of covert and overt strategies for optimal effect [12e], and a game theoretic approach that considers time dynamic alterations of strategies by the interdictor and the evader [10i] have also been analyzed. In the context of wireless ad hoc sensor, mesh, and cellular networks, novel optimization-based design methodologies have been developed for: allocating energy and placing relay nodes [05n]; enhancing the network lifetime [05o]; multiple description video multicast [06q]; rate allocation [08n]; multicast routing [07o]; routing of concurrent video sessions [06r]; joint routing and server selection for video streaming [07m]; multi-path routing for multiple-description video [06s]; optimal data routing for ultra wide band-based sensor networks [06t]; optimal base station selection for anycast routing [06u]; optimizing data rates in ultra wide band-based ad hoc networks [08q]; cross-layer multimedia-centric routing [08l ]; path selection and rate allocation for video applications [09n]; multi-path routing for video communications [07n]; maximizing the capacity of multi-user MIMO (Multiple-Input-Multiple-Output) networks considering interference [08p]; spectrum sharing for multi-hop networks [08m]; multimedia routing for multiple description videos in wireless mesh networks [08o]; routing, power allocation, and bandwidth allocation in wireless mesh networks [08k]; scheduling sessions to improve signal-to-noise ratios [10k]; maximizing capacity of cognitive networks [11m]; multicast communications in cognitive radio networks [11n]; optimal power allocation in cooperative relay networks [12o]; optimal base station placement in commercial buildings for wireless communications [12n]; energy renewal approach for extending the life of sensor networks with wireless energy transfer [12p]; joint flow routing and relay node assignment within cooperative multi-hop networks [12q]; throughput maximization with network-wide energy constraints [13k]; network infrastructure optimization for future smart buildings [15e]; session grouping and relay node selection for cooperative communications [14k]; wireless energy charging in sensor networks [15f]; rechargeable sensor networks using magnetic resonant coupling [14l]; joint congestion control and routing using a second-order distributed approach [16h]; wireless charging and data collection in sensor networks [15g]; scheduling for MIMO allocation in multi-hop networks [16g], energy-constrained multi-hop multicast approaches for operating directional antennas [15h], and a derivation of the throughput region for primary and secondary users in a node-level cooperative environment [16i]. Models and algorithms have also been developed for the solution of various probabilistic set covering problems [91b]; generalized partial covering problems [06h]; the symmetric and asymmetric eigenvalue complementarity problem [07f, 09h, 14f]; the computation of all eigenvalues for eigenvalue complementarity problems [14g]; the solution of inverse eigenvalue complementarity problems [14d]; the second-order cone eigenvalue complementarity problem [16d]; the quadratic eigenvalue complementarity problem [16c]; the second-order cone quadratic eigenvalue complementarity problem [17c]; the determination of parameter stability margins in control systems using polynomial programming techniques [06o]; optimal synthesis of capacitated networks for multi-commodity flow considerations [07h]; the prize-collecting Steiner tree problem [08f, 10c, 10j, 13a]; some discrete combinatorial production planning problems faced by the Burroughs Corporation/Standard Register [89b]; a linear fractional and mixed-integer programming approach for retail price optimization [10d]; a linear fractional programming problem on networks [12i]; a hardware-software co-design scheduling problem for reconfigurable systems [12m]; a flexible manufacturing system operational problem [90e]; set-up time reduction in production lines [08h]; cost of quality optimization using polynomial programming models [15a]; an optimal product disassembly and part retrieval problem [06g]; a stochastic scheduling problem concerning a network of flexible manufacturing facilities [16e]; a hospital resident scheduling problem [02g]; a hospital staff scheduling problem with stochastic operating times [16f]; a radar pulsing problem and the interleaving of multi-target tracking [04b]; an extension of this concept for developing continuous-time models for interleaving two-phase jobs on a single machine [05d]; the scheduling of doubles tennis training tournaments [10f]; a subassembly parts assignment problem [11i]; developing optimal fleet mix and schedules for routing oil tankers for the Kuwait Petroleum Corporation [99d, 05l, 05m]; determining an optimal fleet mix along with strategic transshipment facility locations and vessel schedules in transportation-inventory operations [13i, 18d]; a joint vehicle loading and routing problem [09d]; a resource allocation model for managing critical network-based infrastructure systems [16b]; a problem dealing with constructing academic schedules at the U.S. Military Academy at West Point [99e]; class-faculty assignment problems [06l, 07j, 15b]; an exam timetabling problem [10g]; a high school timetabling problem [15c]; a column generation approach for assigning workload to teaching assistants [18c]; employee scheduling problems under hierarchical structures [07i, 07 l , 08j]; two-stage stochastic workforce planning problem [09j]; determining optimal rosters for workforce subject to cyclic requirements [12l ]; a coal blending and distribution problem for the Taiwan Electric Utility Company [00j]; a branch-and-price approach for a stochastic generalized assignment problem [14e]; a column generation approach for the graph equipartition problem [20a]; a perturbation technique for generating maximal non-dominated Benders cuts [13e]; the concept of minimizing the conditional value-at-risk for stochastic scheduling problems [14h]; a scenario-based lower bounding approach for stochastic scheduling problems [12g]; a primary pharmaceutical manufacturing scheduling problem [14c]; a bulk tank allocation and distribution problem for the natural gas industry [14b]; and a coastal sea-space sector design problem for U.S. Coast Guard patrolling operations [12f]. For the Naval Surface Warfare Center, a novel discrete optimization model that possesses a very tight linear programming relaxation has been developed to solve their battle-group anti-air passive homing device scheduling problem in real-time [95d, 09m]. Related concepts have been extended to derive effective algorithms for parallel machine scheduling problems having time-window and machine unavailability constraints [94d, 09m]. A state-of-the-art survey of Integer Programming until the end of the twentieth century appears in [00e].
Under the umbrella of the National Center for Excellence in Aviation Operations Research established by the FAA (with founding members: Virginia Tech, MIT, UC Berkeley, and the Univ. of Maryland), several operational and policy models have been developed. These include an Airspace Sector Occupancy Model for determining the entry and exit points and occupancy durations of aircraft traversing through nonconvex three-dimensional sectors, and an Aircraft Encounter Model for detecting and assessing the severity of aircraft collision risks [00d]. Analyses of various future traffic scenarios under Free-Flight and Cruise-Climb conditions have been conducted for the FAA. A novel Airspace Planning Model that examines diversions and delays of flights under special-use airspaces prompted by space launches or under severe weather conditions, subject to various sector workload, collision safety, and airline carrier equity considerations has been developed, analyzed, and tested [02c]. This has been significantly enhanced in a revised Airspace Planning and Collaborative Decision Making (APCDM) model, by considering stochastic navigation errors in a probabilistic collision risk analysis, new collaboration equity and sector workload constructs, and several classes of valid inequalities to tighten the model representation [03d, 06d]. Novel extensions to consider the bartering of slots by airlines with the FAA acting as a mediator under the Ground Delay Program paradigm, along with various equity concepts, have been proposed within the context of the APCDM model [11b]. New models for representing weather data along with aircraft trajectory generation mechanisms to circumvent severe weather with a specified threshold probability are proposed in [08g]. A related reverse time-restricted shortest path problem is analyzed in [09g]. Novel models and algorithms for partitioning the airspace into convex sectors under a dynamic airspace configuration paradigm for balancing air traffic controller workload have been proposed [13d]. A study has also been conducted for the ground control of aircraft under time-dependent taxiway routing conditions [02i], and for a combined arrival-departure aircraft sequencing problem [14a]. A methodological framework for determining aggregate daily operation airline schedules over the year has been developed [11l]. For the airline industry, in conjunction with United Airlines, a discrete optimization methodology has been developed for revising fleet assignments using more realistic itinerary-based demand considerations where uncertainty mitigates as the time of departure approaches [05b], as well as for a two-stage stochastic optimization approach for the fleet assignment problem under probabilistic demand patterns [08a]. Integrated airline operational models (enhanced via valid inequalities) and algorithms that simultaneously consider schedule planning and fleet assignment [10a]; aircraft fleeting and routing [11f, 11h]; schedule design and fleet assignment with flight retiming, schedule balance, and demand recapture considerations [13f]; and schedule planning, fleet assignment, and aircraft routing [13b] have been analyzed and demonstrated to yield significantly increased profits. A hybrid optimization-simulation algorithm for the weekly aircraft routing and retiming problem has also been developed [17b]. A novel polynomial length lifted formulation for the aircraft maintenance routing problem has been designed [13c], and has been further used in an integrated model and approach for simultaneously solving the fleet assignment, aircraft routing, and crew pairing problems [17a]. Likewise, a novel compact formulation for the airline crew pairing problem has been proposed [19a]. A tutorial on the airline fleet assignment problem appears in [06k]. A phenomenon called dual noise has been identified that explains the observed stalling when using column generation techniques for solving large-scale airline crew scheduling problems, which has been curtailed using a new deflected subgradient optimization technique [08e].
(B) Linear, Nonlinear, Network, and Transportation Mathematical Programming Problems with Applications: Some nonadjacent extreme point algorithms [83c], and advanced bases procedures [84f], have been proposed to enhance the effectiveness of the simplex method. A convergence analysis for the affine-scaling variant of Karmarkar's algorithm has been accomplished. This analysis demonstrates the connections between this variant and logarithmic barrier function methods, generalized gradient methods employing space dilation techniques, and Khachian's ellipsoid algorithm [87b]. It is shown that a slight perturbation of the variant admits convergence in an assumption-free environment [88f]. An exterior point approach for linear programming based on polytope sliding and deformation has also been developed [97i]. This algorithm, while exact, is probably most useful for determining quick near optimal solutions with minimal storage requirements. This has also led to the development of a competitive closest point routine [93c]. With the same motivation, various classes of exterior penalty function approaches for solving linear programming problems have been explored [01j]. An insightful constructive proof of the important Representation Theorem has also been developed [87g]. A characterization of degeneracy in linear assignment network problems has been analyzed [82d], and a versatile scheme for ranking its vertices has been developed [81c]. An RLT approach to effecting optimal corrections to inconsistent systems of linear constraints appears in [08i, 09e]. Graph theoretic approaches to curricula scheduling [77a] (see also [99e]) have also been studied. A detailed investigation of several novel solution procedures for the challenging pipe network design problem has been conducted [90h, 93g, 96b, 97f, 98h, 01d, 02h]. Several test problems in the literature that have been open for 20-30 years have been solved to global optimality for the first time. A theoretical characterization of the relationships between preemptive and non-preemptive solutions to linear, nonlinear and discrete multiple objective programs has been developed [82f, 83a, 88e]. An interactive convergent cutting plane algorithm has also been designed for multi-objective programming problems. For the Association of American Railroads (AAR), network models with "complicating" side-constraints have been developed for their empty freight car management program involving railroads participating in a pooling agreement [85f]. A specialized decomposition procedure developed for these problems is presently being used by the AAR. Strategic fleet sizing models and algorithms have also been developed and implemented for the AAR [97a] and for the TTX Company [00l], and a decision support system for the tactical empty railcar distribution problem has been developed and implemented at the TTX Company [98g]. Several game theoretic approaches for apportioning railcar capital expenses among automobile shippers and among rail carriers participating in a pooling agreement have been developed [11g]. Geometrically convergent primal-dual subgradient [86f] and conjugate subgradient algorithms [89a] have been designed for decomposable and/or nondifferentiable convex programming problems, by coordinating a suitable penalty function along with a Lagrangian dual function. These procedures have been specialized and implemented for the AAR real-world problems. This analysis has also led to a new conjugate gradient scheme which is more closely related to Quasi-Newton updates [90f]. Such conjugate gradient procedures along with second-order information based directions have been used to enhance Response Surface Methodology approaches that have traditionally relied on first-order schemes that are unmindful of previously generated information [98d]. A new variable target value conjugate subgradient algorithm has been developed for convex nondifferentiable problems, which makes no a priori assumptions on the availability of bounds [00a]. In addition, other effective memoryless and limited memory space dilation and reduction based subgradient deflection strategies have been proposed and tested [01f]. Certain generalized schemes for obtaining primal solutions when using pure or deflected subgradient methods for optimizing Lagrangian duals of large-scale, specially structured linear programs have also been developed [96e]. These methods use only the information that is generated in the process of applying such schemes, while imposing no additional computational burden. A coordination of the volume algorithm, generalized Polyak-Kelly cutting plane schemes, and various subgradient deflection schemes have been studied to develop theoretically convergent and computationally effective methods for optimizing Lagrangian duals of linear programs and solving more general nondifferentiable optimization problems [04a, 06j, 07a, 06m, 08e]. In particular, the results exhibit a high speed-up factor (33 times faster) than a commercial software (CPLEX) to compute the same quality solutions for linear programs.
Contributions have also been made in the areas of constructive derivation techniques for dynamic programming [81a]; step-size choices in subgradient optimization [81b]; the crew scheduling problem [84c]; the oil-tanker routing problem faced by the Kuwait Petroleum Corporation [99d, 05l, 05m, 13i, 18d]; nonlinear and linear network with side-constraints forest harvest scheduling problems [85h, 90g]; linear programming approaches for designing a herbaceous biomass delivery system [97g]; relationships between Dorn's duality and Lagrangian duality [93a]; and in showing connections between the partitioned shortest path algorithm, Moore's algorithm, and dynamic programming [91a]. Various complexity results, models and algorithms have also been developed for the time-dependent shortest pair of variable-degree disjoint paths problem [98f]. Improved discrete optimization models that use a new opportunity cost concept, as well as polynomial-time algorithms for special cases, have been developed for the traffic incident response problem [99b]. For the Federal Highway Administration, various modules that comprise TRANSIMS, a $20M transportation planning system originally developed at the Los Alamos National Laboratory, have been enhanced. In particular, efficient techniques have been devised for solving a new class of time-dynamic, label-constrained shortest path problems [03b]; approach-dependent, time-dependent, label-constrained shortest path problems [06f]; and reverse time-restricted shortest path problems [09g], with related complexity analyses. A novel optimal pruning strategy has also been developed for classification trees under side-constraints [09b] (this has been patented). Various network interdiction problems to maximize the minimum flow of an evader, or to minimize the maximum probability of evasion, under novel considerations of superadditive synergy among the resources utilized by the interdictor, with extensions to combined covert-and-overt strategies and time dynamic strategic variations have also been studied [12d, 12e, 10i] (see also Part A above). Insightful analytical results and models and algorithms have been devised for staging and routing considerations in the context of evacuation planning [13h], along with an aggregate-level demand management planning approach [14i]. Using TRANSIMS as a motivating application, contributions have also been made to the computation of dynamic user equilibrium solutions [06p]. Emission control studies have also been conducted using TRANSIMS [06v]. Under a DOT/VDOT grant, a novel linear programming model solvable via a column generation scheme has been developed for constructing origin-destination trip tables based on given inexact traffic counts. An equilibrium solution is sought that matches link volumes and is driven by a specified target trip table to an extent controllable by input parameters. Favorable results in comparison with competing nonlinear approaches are reported with respect to both effort and accuracy [94c]. A significant extension of this methodology to handle the ubiquitous case of missing link volumes, which requires the derivation of a suitable fixed-point solution, is described in [03f]. In addition to this static model, a dynamic origin-destination trip table estimation model has been developed and suitable optimization techniques have been designed to solve this problem for special corridor or intersection as well as general networks [97b, 01e]. It is shown that not only can this approach be operated in real-time, but that it also yields more accurate solutions than available through traditional statistical procedures. Also funded by VDOT, a discrete optimization approach has been developed for optimally locating Automatic Vehicle Identification (AVI) readers for effectively measuring travel times on key roadways [06i]. Under a U.S. DOI grant, models and algorithms have been designed for coal mining, blending, and distribution [93b], along with strategic and tactical considerations for conforming to the 1990 Clean Air Act [93e] (see also [00j]).
(For further contributions to nonconvex nonlinear programming problems, including polynomial programs, quadratic problems, bilinear programs, linear complementarity problems, etc., see Part (A) above. Also, several other transportation applications are discussed in Parts (A) and (C).)
(C) Location Theory: The work in this area principally involves nonconvex, capacitated location-allocation problems on planes and networks. For the notorious quadratic assignment problem, several novel model reformulations and decomposition, partial enumeration over projected regions, and cutting plane approaches have been developed [78b, 80c, 82e, 86h]. When operated inexactly, these methods have been demonstrated to yield powerful heuristic techniques that have discovered the best known solutions reported heretofore for many test cases from the literature. The first specialized algorithm for solving capacitated multi-facility rectilinear distance location allocation problems on a plane has been developed [80a]. Efficient methods for the rectilinear distance location problem [78a], and the multi-facility Euclidean distance location problem using a conjugate subgradient approach [99c] have also been developed. In particular, it has been an open question since 1972 whether the dual to the Euclidean multi-facility location problem can be used to readily yield primal optimal solutions. Through Lagrangian duality constructs, this has been resolved in the affirmative [99a]. Various other equivalent differentiable formulations to this nondifferentiable problem are presented and analyzed in [99a]. Location-allocation models have been constructed and analyzed for citing shelter locations and prescribing evacuation strategies under hurricane or flood conditions [91e]. Capacitated and uncapacitated location-allocation problems over convex polygons [86b], and over networks having a continuum of demand [86c, 88d], have also been analyzed. In particular, the algorithms proposed for the capacitated problems on networks are developed for the first time in the literature, and the addition of capacity restrictions have been shown to render otherwise polynomially solvable problems as NP-Hard [88a]. In addition, an algorithm which has been computationally shown to be superior over alternative methods has been designed for the capacitated discrete-site location-allocation problem on a plane or network [84e] as well as for the discrete equal-capacity p-median problem [00c]. These algorithms have been extended to the dynamic multi-period situation in which the facility location decisions need to be made sequentially, one per period [85e, 91c]. Also, a much more complex class of unbalanced, capacitated location-allocation problems on networks has been analyzed [91d]. These problems are also shown to be NP-Hard, and some effective algorithms have been developed based on optimality characterizations. In a novel application under a NASA project, models and algorithms have been developed for locating runway exits and designing their geometry in order to minimize aircraft runway occupancy times. The continuum problem is reduced to an equivalent finite dimensional mathematical program, for which a polynomial-time dynamic programming algorithm is designed [92b, 93d]. A new class of problems involving the determination of an optimal path in a plane or in a network for a facility moving in a region while interacting with fixed facilities has been modeled and analyzed using calculus of variations and mathematical programming techniques [89c, 92c, 92g]. For the squared-Euclidean location-allocation problem [92d], a new bounding technique has been devised via the construction of strong polyhedral relaxations using the RLT procedure. Computational experience exhibits a very significant improvement over traditional bounds. A similar advancement in the state-of-the-art has been obtained for solving rectilinear-distance location-allocation problems [94b]. The important variant of such location-allocation problems based on Euclidean or lp distance measures poses a significant challenge because of its nonconvexity as well as nondifferentiability. Global optimization algorithms have been developed for the first time for such capacitated problems using the RLT technique [02a]. Some novel applications of location theory models and associated discrete and nonlinear programming algorithms have been used to study the problem of optimally locating transmitters in micro-cellular radio communication design [96c]; optimally locating Automatic Vehicle Identification readers on transportation networks [06i]; and locating and sizing facilities under probabilistic demands [11d]. A highly challenging problem in location theory, which generalizes the notorious quadratic assignment problem (see 78b, 80c, 82e, and 86h for contributions on the latter class of problems), is the rectangular facility layout design problem. Novel modeling approaches have been designed for representing the nonlinear area constraints and the nonconvex disjunctive relationships, and new classes of valid inequalities have been developed that significantly enhance the accuracy and efficiency in solving these problems [03a]. Three previously unsolved challenging test cases from the literature have been solved to global optimality for the first time. Another novel sequence pair representation has been used to solve two additional larger-sized open layout problems in the literature for the first time [07c].
(D) Mathematical Economics and Game Theory: A series of papers have been published dealing with new characterizations and methodologies for computing fixed-point equilibrium solutions for oligopolistic models of various types of industries, with and without a competitive fringe. These papers address Nash-Cournot [82b, 87a], and Stackelberg-Nash-Cournot leader-follower equilibria [83b, 84d], their static and dynamic convergence properties [88c], and non-cooperative as well as cooperative behavior including merger considerations [86i]. The analysis involves parametric nonlinear programming sensitivity analysis and convex as well as nonconvex programming subproblems. This research has also analyzed more complex network oligopolistic models of industries with multiple production stages [85j]. Both follower-follower and leader-follower models have been analyzed, and incentives to merge with implications on market supply and prices and on anti-trust policy-making decisions have been investigated [88g, 92f]. The theory has been applied to a study of the copper industry [81e, 82g]. A game theoretic approach to analyzing the inducement of regional technological cooperation between developed and developing nations has been proposed for the first time in the literature [00g]. A comprehensive methodology for analyzing the scope for foreign investments in projects related to the development of the China Tumen Area has been proposed and applied [03g]. A highly effective nondifferentiable approach to portfolio optimization by minimizing the conditional value-at-risk has been devised [10e]. A linear fractional and mixed-integer programming approach to retail price optimization under a discrete price ladder has been developed [10d]. Game theoretic approaches have also been investigated for apportioning capital allocations among automobile shippers and railroad carriers [11g] participating in a pooling agreement, and for a time-dynamic network interdiction problem involving an interdictor and an evader [10i].
(E) Energy Modeling and Analysis: This research effort deals with capacity expansion planning and marginal cost pricing problems for electric utilities. A highly efficient nonlinear programming algorithm for the single period model has been developed [85d], and this has been used to design procedures for the multi-period problem. An extensive study of the dual to the linear discretized version of this problem has produced several insightful results, including closed-form dual solutions which admit rich economic interpretations and which are useful from the viewpoint of marginal cost and time-of-day pricing decisions [82c, 83d, 84a, 85k, 87f]. This research has been extended to incorporate renewable and non-dispatchable energy sources in capacity expansion plans [84b, 85c, 90b]. A procedure competitive with the existing state-of-the-art package EGEAS has been developed and applied to the Tijuana-Mexicali subsystem of the Mexican utility, for which EGEAS has been shown to be inadequate [87e]. Novel modeling constructs that promote the effective solution of the unit commitment problem for scheduling thermal generation units have been developed [00m].