Preemptive and nonpreemptive multi-objective programming: Relationship and counterexamples

In this paper, we formally establish connections between two standard approaches proposed for resolving multi-objective programs, namely, the nonpreemptive and the preemptive methods. We demonstrate in the linear case that, if the preemptive problem has an optimal solution, then there exists a set of weights for the nonpreemptive problem, such that any optimal solution to the nonpreemptive problem is optimal to the preemptive problem. Conversely, and more importantly, any optimal solution to the preemptive problem is optimal to the nonpreemptive problem. A similar result is established for arbitrary multi-objective functions being optimized over a finite discrete set. Thus, the preemptive problem is subsumed within the nonpreemptive problem in these cases. Although we actually construct a set of equivalent weights, we do not advocate our technique as a computational device for solving the preemptive problem. However, a previous attempt (Ref. 1), which does prescribe a set of equivalent weights to solve a preemptive problem as a linear program, is shown to be erroneous. Moreover, our constructive proof exhibits the features of the problem which govern the determination of such equivalent weights.     

A fractional programming approach for retail category price optimization

We present a new mixed-integer programming (MIP) approach to study certain retail category pricing problems that arise in practice. The motivation for this research arises from the need to design innovative analytic retail optimization techniques at Oracle Corporation to not only predict the empirical effect of price changes on the overall sales and revenue of a category, but also to prescribe optimal dynamic pricing recommendations across a category or demand group. A multinomial logit nonlinear optimization model is developed, which is recast as a discrete, nonlinear fractional program (DNFP). The DNFP model employs a bi-level, predictive modeling framework to manage the empirical effects of price elasticity and competition on sales and revenue, and to maximize the gross-margin of the demand group, while satisfying certain practical side-constraints. This model is then transformed by using the Reformulation–Linearization Technique in tandem with a sequential bound-tightening scheme to recover an MIP formulation having a relatively tight underlying linear programming relaxation, which can be effectively solved by any commercial optimization software package. We present sample computational results using randomly generated instances of DNFP having different constraint settings and price range restrictions that are representative of common business requirements, and analyze the empirical effects of certain key modeling parameters. Our results indicate that the proposed retail price optimization methodology can be effectively deployed within practical retail category management applications for solving DNFP instances that typically occur in practice.     

Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality

In this paper, we propose two sets of theoretically filtered bound-factor constraints for constructing reformulation-linearization technique (RLT)-based linear programming (LP) relaxations for solving polynomial programming problems. We establish related theoretical results for convergence to a global optimum for these reduced sized relaxations, and provide insights into their relative sizes and tightness. Extensive computational results are provided to demonstrate the relative effectiveness of the proposed theoretical filtering strategies in comparison to the standard RLT and a prior heuristic filtering technique using problems from the literature as well as randomly generated test cases.     

A column generation approach for determining optimal fleet mix,schedules, and transshipment facility locations for a vessel transportation problem

This paper presents a column generation approach for a storage replenishment transportation-scheduling problem. The problem is concerned with determining an optimal combination of multiple-vessel schedules to transport a product from multiple sources to different destinations based on demand and storage information at the destinations, along with cost-effective optimal strategic locations for temporary transshipment storage facilities. Such problems are faced by oil/trucking companies that own a fleet of vessels (oil tankers or trucks) and have the option of chartering additional vessels to transport a product (crude oil or gasoline) to customers (storage facilities or gas stations) based on agreed upon contracts. An integer-programing model that determines a minimum-cost operation of vessels based on implicitly representing feasible shipping schedules is developed in this paper. Due to the moderate number of constraints but an overwhelming number of columns in the model, a column generation approach is devised to solve the continuous relaxation of the model, which is then coordinated with a sequential fixing heuristic in order to solve the discrete problem. Computational results are presented for a range of test problems to demonstrate the efficacy of the proposed approach.     

A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture

The airline’s ability to offer flight schedules that provide service to passengers at desired times in competitive markets, while matching demand with an aircraft fleet of suitable size and composition, can significantly impact its profits. In this spirit, optional flight legs can be considered to construct a profitable schedule by optimally selecting among such alternatives in concert with assigning the available aircraft fleet to all the scheduled legs. Examining itinerary-based demands as well as multiple fare-classes can effectively capture network effects and realistic demand patterns. In addition, allowing flexibility on the departure times of scheduled flight legs can increase connection opportunities for passengers, hence yielding robust schedules while saving fleet assignment costs within the framework of an integrated model. Airlines can also capture an adequate market share by balancing flight schedules throughout the day, and recapture considerations can contribute to more realistic accepted demand realizations. We therefore propose in this paper a model that integrates the schedule design and fleet assignment processes while considering flexible flight times, schedule balance, and recapture issues, along with optional legs, path/itinerary-based demands, and multiple fare-classes. A polyhedral analysis is conducted to generate several classes of valid inequalities, which are used along with suitable separation routines to tighten the model representation. Solution approaches are designed by applying Benders decomposition method to the resulting tightened model, and computational results are presented using real data obtained from United Airlines to demonstrate the efficacy of the proposed procedures.     

The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches

We propose a generalized version of the Prize Collecting Steiner Tree Problem (PCSTP), which offers a fundamental unifying model for several well-known -hard tree optimization problems. The PCSTP also arises naturally in a variety of network design applications including cable television and local access networks. We reformulate the PCSTP as a minimum spanning tree problem with additional packing and knapsack constraints and we explore various nondifferentiable optimization algorithms for solving its Lagrangian dual. We report computational results for nine variants of deflected subgradient strategies, the volume algorithm (VA), and the variable target value method used in conjunction with the VA and with a generalized Polyak–Kelley cutting plane technique. The performance of these approaches is also compared with an exact stabilized constraint generation procedure.     

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.     

Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts

In this paper, we propose to enhance Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations for polynomial programming problems by developing cutting plane strategies using concepts derived from semidefinite programming. Given an RLT relaxation, we impose positive semidefiniteness on suitable dyadic variable-product matrices, and correspondingly derive implied semidefinite cuts. In the case of polynomial programs, there are several possible variants for selecting such particular variable-product matrices on which positive semidefiniteness restrictions can be imposed in order to derive implied valid inequalities. This leads to a new class of cutting planes that we call v-semidefinite cuts. We explore various strategies for generating such cuts, and exhibit their relative effectiveness towards tightening the RLT relaxations and solving the underlying polynomial programming problems in conjunction with an RLT-based branch-and-cut scheme, using a test-bed of problems from the literature as well as randomly generated instances. Our results demonstrate that these cutting planes achieve a significant tightening of the lower bound in contrast with using RLT as a stand-alone approach, thereby enabling a more robust algorithm with an appreciable reduction in the overall computational effort, even in comparison with the commercial software BARON and the polynomial programming problem solver GloptiPoly.     

Effective Relaxations and Partitioning Schemes for Solving Water Distribution Network Design Problems to Global Optimality

In this paper, we address the development of a global optimization procedure for the problem of designing a water distribution network, including the case of expanding an already existing system, that satisfies specified flow demands at stated pressure head requirements. The proposed approach significantly improves upon a previous method of Sherali et al. (1998) by way of adopting tighter polyhedral relaxations, and more effective partitioning strategies in concert with a maximal spanning tree-based branching variable selection procedure. Computational experience on three standard test problems from the literature is provided to evaluate the proposed procedure. For all these problems, proven global optimal solutions within a tolerance of 10^–4% and/or within 1$ of optimality are obtained. In particular, the two larger instances of the Hanoi and the New York test networks are solved to global optimality for the very first time in the literature. A new real network design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test cases, and related computational results are presented.