Search

Distributed joint congestion control and routing optimization has received a significant amount of attention recently. To date, however, most of the existing schemes follow a key idea called the back-pressure algorithm. Despite having many salient features, the first-order subgradient nature of the back-pressure based schemes results in slow convergence and poor delay performance. To overcome these limitations, in this paper, we make a first attempt at developing a second-order joint congestion control and routing optimization framework that offers utility-optimality, queue-stability, fast convergence, and low delay. Our contributions in this paper are three-fold: i) we propose a new second-order joint congestion control and routing framework based on a primal-dual interior-point approach; ii) we establish utility-optimality and queue-stability of the proposed second-order method; and iii) we show how to implement the proposed second-order method in a distributed fashion.

Recently, a new MIMO degree-of-freedom (DoF) model was proposed to allocate DoF resources for spatial multiplexing (SM) and interference cancellation (IC) in a multi-hop network. Although this DoF model promises many benefits, it hinges upon a global node ordering to keep track of IC responsibilities among all the nodes. An open question about this model is whether its global ordering property can be achieved among the nodes in the network through distributed operations. In this paper, we explore this question by studying DoF scheduling in a multi-hop MIMO network, with the objective of maximizing the minimum throughput among a set of sessions. We propose an efficient DoF scheduling algorithm to solve it and show that our algorithm only requires local operations. We prove that the resulting DoF scheduling solution is globally feasible and show that there exists a corresponding feasible global node ordering for IC, albeit such global ordering is implicit. Simulation results show that the solution values obtained by our algorithm are relatively close to the upper bound values computed by CPLEX solver, thereby indicating that our algorithm is highly competitive.

The Quadratic Eigenvalue Complementarity Problem (QEiCP) is an extension of the Eigenvalue Complementarity Problem (EiCP) that has been introduced recently. Similar to the EiCP, the QEiCP always has a solution under reasonable hypotheses on the matrices included in its definition. This has been established in a previous paper by reducing a QEiCP of dimension n to a special 2n-order EiCP. In this paper we propose an enumerative algorithm for solving the QEiCP by exploiting this equivalence with an EiCP. The algorithm seeks a global minimum of a special Nonlinear Programming Problem (NLP) with a known global optimal value. The algorithm is shown to perform very well in practice but in some cases terminates with only an approximate optimal solution to NLP. Hence, we propose a hybrid method that combines the enumerative method with a fast and local semi-smooth method to overcome the latter drawback. This algorithm is also shown to be useful for computing a positive eigenvalue for an EiCP under similar assumptions. Computational experience is reported to demonstrate the efficacy and efficiency of the hybrid enumerative method for solving the QEiCP.

This paper investigates a high school timetabling problem in a case study related to Kuwait's public educational system, which is concerned with assigning teachers to classes and time-slots. Because a direct solution to an initially formulated comprehensive mixed-integer programming model for generating weekly teacher schedules was found to be untenable for practical-sized realistic test instances, we propose in this paper two decomposition approaches to the underlying problem. A two-stage modeling solution approach is presented first, where the initial stage determines weekly time-slots for the classes, based on which, the second stage then assigns teachers to classes. Instead of generating weekly schedules within the model itself, we propose another mixed-integer programming formulation that selects valid combinations of weekly schedules from the set of all feasible schedules, and we design a column generation solution framework to exploit its inherent special structure. Computational results are presented for the proposed solution approaches using several real as well as simulated realistic test problems pertaining to high schools in Kuwait.

The eigenvalue complementarity problem EiCP differs from the traditional eigenvalue problem in that the primal and dual variables belong to a closed and convex cone K and its dual, respectively, and satisfy a complementarity condition. In this paper we investigate the solution of the second-order cone EiCP SOCEiCP where K is the Lorentz cone. We first show that the SOCEiCP reduces to a special Variational Inequality Problem on a compact set defined by K and a normalization constraint. This guarantees that SOCEiCP has at least one solution, and a new enumerative algorithm is introduced for finding a solution to this problem. The method is based on finding a global minimum of an appropriate nonlinear programming NLP formulation of the SOCEiCP using a special branching scheme along with a local nonlinear optimizer that computes stationary points on subsets of the feasible region of NLP associated with the nodes generated by the algorithm. A semi-smooth Newton's method is combined with this enumerative algorithm to enhance its numerical performance. Our computational experience illustrates the efficacy of the proposed techniques in practice.

Wireless energy transfer based on magnetic resonant coupling is a promising technology to replenish energy to a wireless sensor network (WSN). However, charging sensor nodes one at a time poses a serious scalability problem. Recent advances in magnetic resonant coupling show that multiple nodes can be charged at the same time. In this paper, we exploit this multi-node wireless energy transfer technology and investigate whether it is a scalable technology to address energy issues in a WSN. We consider a wireless charging vehicle (WCV) periodically traveling inside a WSN and charging sensor nodes wirelessly. Based on charging range of the WCV, we propose a cellular structure that partitions the two-dimensional plane into adjacent hexagonal cells. We pursue a formal optimization framework by jointly optimizing traveling path, flow routing, and charging time. By employing discretization and a novel Reformulation-Linearization Technique (RLT), we develop a provably near-optimal solution for any desired level of accuracy. Through numerical results, we demonstrate that our solution can indeed address the charging scalability problem in a WSN.

Network-coded cooperative communications (NC-CC) is a new paradigm for communications in wireless networks that employs network coding (NC) to improve the performance of CC. A key problem to harness the potential of NC-CC is how to put sessions into different groups, and assign a relay node for each group. In this paper, we study this joint grouping and relay node selection problem for NC-CC. We provide a formal proof of NP-hardness for this problem. Due to NP-hardness, we propose a distributed and online algorithm and show that it offers near-optimal solution to this problem. The key idea in this algorithm is to have each neighboring relay node of a new session calculate the best local group that it can offer and advertise this information; and then to have the source node of the new session select the best local group to join among all offers. We show that our distributed algorithm has polynomial time complexity. Using extensive numerical results, we show that our distributed algorithm adapts well to online network dynamics.

This article addresses an integrated lot-sizing and scheduling problem that arises in the primary manufacturing phase of a pharmaceutical supply chain. Multiple pharmaceutical ingredients and their intermediate products are to be scheduled on parallel and capacitated bays for production in batches. Sequence-dependent setup times and costs are incurred when cleaning a bay during changeovers between different product families. The problem also contains a high multiplicity asymmetric traveling salesman-type of substructure because of sequence-dependent setups and special restrictions. Mixed-integer programming formulations are proposed for this problem and several valid inequalities are developed to tighten the model. A column generation method along with a decomposition scheme and an advanced-start solution are designed to efficiently derive good solutions to this highly complex problem. A computational investigation is performed, based on instances that closely follow a real-life application, and it demonstrates the efficacy of the proposed solution approach.

This paper addresses the static aircraft sequencing problem over a mixed-mode single runway (or closely interacting parallel runways), which commonly constitutes a critical bottleneck at airports. In contrast with disjunctive formulations, our modeling approach takes advantage of the underlying structure of an asymmetric traveling salesman problem with time-windows. This enables the development of efficient preprocessing and probing procedures, and motivates the derivation of several classes of valid inequalities along with partial convex hull representations to enhance problem solvability via tighter reformulations. The lifted model is further embedded within the framework of two proposed heuristics that are compared against the traditional first-come first-served (FCFS) heuristic with landing priority: an optimized FCFS policy (OFCFS) and a threshold-based suboptimized heuristic (TSH) with an a priori fixing of the relative order of aircraft that are sufficiently time-separated. Computational results using real data based on Doha International Airport (DOH) as well as simulated instances are reported to demonstrate the efficacy of the proposed exact and heuristic solution methods. In particular, for the DOH instances, heuristics OFCFS and TSH achieved an attractive runway utilization (4.3% and 5.0% makespan reduction, respectively, over the base FCFS policy with landing priority), while exhibiting limited aircraft position deviations (0.45 and 0.49 deviations on average, respectively, from the base FCFS positions with landing priority, with similar results being obtained for the simulated instances). The superiority of the proposed optimization models over previous disjunctive formulations is also demonstrated for challenging problem instances, resulting in over 50% CPU savings for the larger instances in our test-bed.

This paper examines relationships between the two methods for constructing polyhedral outer-approximations of mixed 0-1 linear programs known in the literature as the level-1 Reformulation–Linearization-Technique (RLT) and the elementary closure of lift-and-project (L&P) cuts based on the level-1 L&P. The latter can be obtained, via a transformation of variables, as a relaxed version of the former through the removal of constraints. Whereas both approaches derive formulations in lifted spaces by scaling problem constraints with suitable multipliers, a key difference is that the multipliers used by the RLT are defined in terms of the binary variables of the given problem. As a consequence, these multipliers, in contrast to those used in the L&P, portend important advantages, including the ability to handle nonlinear expressions, to recognize redundant inequalities, and to exploit special structures. This paper compares the two methods, and uses RLT constructs to provide insights into the L&P approach. Some particular insights are illustrated on the quadratic assignment and MAX-2SAT problems, with level-2 RLT and level-2 L&P comparisons also given for the latter problem.

In this paper, a parametric algorithm is introduced for computing all eigenvalues for two Eigenvalue Complementarity Problems discussed in the literature. The algorithm searches a finite number of nested intervals $$[\bar{l}, \bar{u}]$$ [ l ¯ , u ¯ ] in such a way that, in each iteration, either an eigenvalue is computed in $$[\bar{l}, \bar{u}]$$ [ l ¯ , u ¯ ] or a certificate of nonexistence of an eigenvalue in $$[\bar{l}, \bar{u}]$$ [ l ¯ , u ¯ ] is provided. A hybrid method that combines an enumerative method [1] and a semi-smooth algorithm [2] is discussed for dealing with the Eigenvalue Complementarity Problem over an interval $$[\bar{l}, \bar{u}]$$ [ l ¯ , u ¯ ] . Computational experience is presented to illustrate the efficacy and efficiency of the proposed techniques.

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch-and-price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method—one that utilizes a dual-stabilization technique and another that incorporates an advanced-start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch-and-cut (B&C) method within CPLEX. Our results show that all B&P-based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the “true” optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10-fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014

In this paper, we discuss the solution of an Inverse Eigenvalue Complementarity Problem. Two nonlinear formulations are presented for this problem. A necessary and sufficient condition for a stationary point of the first of these formulations to be a solution of the problem is established. On the other hand, to assure global convergence to a solution of this problem when it exists, an enumerative algorithm is designed by exploiting the structure of the second formulation. The use of additional implied constraints for enhancing the efficiency of the algorithm is also discussed. Computational results are provided to highlight the performance of the algorithm.

Airline profits critically depend on the nature and efficiency of service they provide, and accrue from a complex planning process involving schedule design, fleet assignment, aircraft routing, and crew scheduling, which are interrelated to each other within the overall system. We propose in this paper a model that integrates certain aspects of the schedule design, fleet assignment, and aircraft-routing processes, while considering flight retiming and demand recapture issues, along with optional legs, itinerary-based demands, and multiple fare classes. Maintenance routing decisions, as well as through-flight opportunities, are additionally incorporated in our model, and we apply the reformulation-linearization technique to reduce its complexity while introducing hierarchical symmetry-breaking constraints, along with other classes of valid inequalities, to enhance its solvability. A Benders' decomposition-based method is designed to handle the resulting large-scale model formulation. Computational results using real data obtained from United Airlines are presented to demonstrate the potential profitability in applying the proposed approach.

Given a set of flights for a specific fleet type, the aircraft routing problem (ARP) determines the flying sequence for each individual aircraft while incorporating specific considerations of minimum turn time, maintenance checks, as well as restrictions on the total accumulated flying time, the total number of takeoffs, and the total number of days between two consecutive maintenances. This stage is significant to airline companies as it directly assigns operational routes and maintenance breaks for each aircraft in service. Most approaches related to the problem adopt set partitioning formulations that include exponentially many variables, which requires the design of specialized column generation or branch-and-price algorithms and codes. In this paper, we present a compact polynomial-sized representation for the ARP, which is then linearized and lifted using the reformulation-linearization technique. In addition, we propose two root-node strategies for further augmenting the model formulation. The resulting formulations remain polynomial in size, and we show that they can be solved very efficiently by commercial software without complicated algorithmic implementations. The numerical experiments demonstrate high-quality solutions and significant savings in computational time.

This paper introduces the use of conditional-value-at-risk (CVaR) as a criterion for stochastic scheduling problems. This criterion has the tendency of simultaneously reducing both the expectation and variance of a performance measure, while retaining linearity whenever the expectation can be represented by a linear expression. In this regard, it offers an added advantage over traditional nonlinear expectation-variance-based approaches. We begin by formulating a scenario-based mixed-integer program formulation for minimizing CVaR for general scheduling problems. We then demonstrate its application for the single machine total weighted tardiness problem, for which we present both a specialized l-shaped algorithm and a dynamic programming-based heuristic procedure. Our numerical experimental results reveal the benefits and effectiveness of using the CVaR criterion. Likewise, we also exhibit the use and effectiveness of minimizing CVaR in the context of the parallel machine total weighted tardiness problem. We believe that minimizing CVaR is an effective approach and holds great promise for achieving risk-averse solutions for stochastic scheduling problems that arise in diverse practical applications.

This paper presents a column generation approach for assigning faculty members to sections of offered classes (class-sections) in a case study related to Kuwait University. For a given class, the total number of class-sections to be offered is known; however, the distribution of these class-sections into available time-slots is determined via a mixed-integer programming model that takes into consideration faculty members’ aggregate preferences for specific offered classes and the time-slots of the corresponding sections, as well as other restrictions imposed by the Office of the Registrar. Subsequently, upon fixing the time-slot assignments of the class-sections, another mixed-integer programming model is formulated and solved to select weekly schedules for faculty members, while considering their preferences for specific classes and time-slots. In this latter model, each variable corresponds to a feasible schedule of a faculty member, and by exploiting its special structure, we demonstrate that its continuous relaxation can be solved very efficiently via a column generation method in order to heuristically derive a good quality feasible solution. Computational results are provided for a number of test instances, including 10 real cases pertaining to the Department of Mathematics at Kuwait University.

The cost of energy consumption is an important concern for network operators. In this paper, we study an energy-related problem that focuses on network-wide energy consumption. In the first part of this work, we study how to maximize throughput under a network-wide energy constraint. We formulate this problem as a mixed-integer nonlinear program (MINLP). This formulation differs from prior efforts as it considers a non-zero device power, which complicates the problem. We propose a novel piece-wise linear approximation to transform the nonlinear constraints into linear constraints. We prove that the solution developed under this approach is near-optimal with a guaranteed performance bound. In the second part, we generalize the problem in the first part via a multicriteria optimization framework, which simultaneously optimizes throughput and total network energy. We show how weakly Pareto-optimal solutions can characterize an optimal throughput-energy curve. We offer some interesting properties of the optimal throughput-energy curves, which are useful to both network operators and end-users. Our results fill in some important gaps in the current understanding on optimizing total network energy.

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.

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.

In this paper, we discuss the solution of linear and quadratic eigenvalue complementarity problems (EiCPs) using an enumerative algorithm of the type introduced by Judice et al. (Optim. Methods Softw. 24:549---586, 2009). Procedures for computing the interval that contains all the eigenvalues of the linear EiCP are first presented. A nonlinear programming (NLP) model for the quadratic EiCP is formulated next, and a necessary and sufficient condition for a stationary point of the NLP to be a solution of the quadratic EiCP is established. An extension of the enumerative algorithm for the quadratic EiCP is also developed, which solves this problem by computing a global minimum for the NLP formulation. Some computational experience is presented to highlight the efficiency and efficacy of the proposed enumerative algorithm for solving linear and quadratic EiCPs.

We use minimal cover and set covering inequalities to define the convex hulls of special sets of binary vectors that are lexicographically lower and upper bounded by given vectors. These convex hulls are used to obtain ideal representations for base-2 expansions of bounded integer variables, and also to afford a new perspective on, and extend convex hull results for, binary knapsack polytopes having weakly super-decreasing coefficients. Computational experience for the base-2 expansions exhibits, on average, a 60% reduction in effort.

Without successful large-scale regional evacuations, threats such as hurricanes and wild-fires can cause a large loss of life. In this context, automobiles are oftentimes an essential transportation mode for evacuations, but the ensuing traffic typically overwhelms the roadway capacity and causes congestion on a massive scale. Congestion leads to many problems including longer, costlier, and more stressful evacuations, lower compliance rates, and increased risk to the population. Supply-based strategies have traditionally been used in evacuation planning, but they have been proven to be insufficient to reduce congestion to acceptable levels. In this paper, we study the demand-based strategies of aggregate-level staging and routing to structure the evacuation demand, both with and without congestion. We provide a novel modeling framework that offers strategic flexibility and utilizes a lexicographic objective function that represents a hierarchy of relevant evacuation-based goals. We also provide insights into the nature and effect of network bottlenecks. We compare our model with and without congestion in relation to tractability, normative optimality, and robustness under demand uncertainty. We also show the effectiveness of using demand-based strategies as opposed to using the status quo that involves a non-staged or simultaneous evacuation process. Effective solution procedures are developed and tested using hypothetical problem instances as well as using a larger study based on a portion of coastal Virginia, USA.

In this paper, we model and solve the network interdiction problem of minimizing the maximum flow through a network from a given source node to a terminus node, while incorporating different forms of superadditive synergy effects of the resources applied to the arcs in the network. Within this context, we examine linear, concave, and convex–concave synergy relationships, illustrate their relative effect on optimal solution characteristics, and accordingly develop and test effective solution procedures for the underlying problems. For a concave synergy relationship, which yields a convex programme, we propose an inner-linearization procedure that significantly outperforms the competitive commercial solver SBB by improving the quality of solutions found by the latter by 6.2% (within a time limit of 1800 CPU s), while saving 84.5% of the required computational effort. For general non-concave synergy relationships, we develop an outer-approximation-based heuristic that achieves solutions of objective value 0.20% better than the commercial global optimization software BARON, with a 99.3% reduction in computational effort for the subset of test problems for which BARON could identify a feasible solution within the set time limit.

Wireless sensor networks are constrained by limited battery energy. Thus, finite network lifetime is widely regarded as a fundamental performance bottleneck. Recent breakthrough in the area of wireless power transfer offers the potential of removing this performance bottleneck, i.e., allowing a sensor network to remain operational forever. In this paper, we investigate the operation of a sensor network under this new enabling energy transfer technology. We consider the scenario of a mobile charging vehicle periodically traveling inside the sensor network and charging each sensor node's battery wirelessly. We introduce the concept of renewable energy cycle and offer both necessary and sufficient conditions. We study an optimization problem, with the objective of maximizing the ratio of the wireless charging vehicle (WCV)'s vacation time over the cycle time. For this problem, we prove that the optimal traveling path for the WCV is the shortest Hamiltonian cycle and provide a number of important properties. Subsequently, we develop a near-optimal solution by a piecewise linear approximation technique and prove its performance guarantee.

In this paper, we investigate scenario generation methods to establish lower bounds on the optimal objective value for stochastic scheduling problems that contain random parameters with continuous distributions. In contrast to the Sample Average Approximation (SAA) approach, which yields probabilistic bound values, we use an alternative bounding method that relies on the ideas of discrete bounding and recursive stratified sampling. Theoretical support is provided for deriving exact lower bounds for both expectation and conditional value-at-risk objectives. We illustrate the use of our method on the single machine total weighted tardiness problem. The results of our numerical investigation demonstrate good properties of our bounding method, compared with the SAA method and an earlier discrete bounding method.

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.

While the deployment of femtocell in residential buildings has firmly positioned it as a major performance leap in wireless communications, its deployment in commercial buildings remains under-explored. In commercial building environments, the femtocell base station (FBS) placement planning is particularly challenging due to the impact of the building size, layout, structure, and wall/floor separation. In this paper, we study the problem of jointly optimizing FBS placement and power control in commercial building environments to prolong the battery life for mobile handsets. We first propose a mathematical model that captures the unique building features. Based on this model, we employ a set of novel transformation strategies to formulate the FBS placement problem as a mixed-integer convex program (MICP). Accordingly, we propose an effective global optimization algorithm based on using the convex relaxation of the formulated MICP within a branch-and-bound framework. This approach guarantees finding a global optimal solution. To demonstrate the efficacy of our algorithm, we conduct extensive numerical studies. Our proposed model and optimization approach offer useful insights into femtocell deployments in commercial buildings.

Cooperative networking is known to have significant potential in increasing network capacity and transmission reliability. Although there have been extensive studies on applying cooperative networking in multi-hop ad hoc networks, most works are limited to the basic three-node relay scheme and single-antenna systems. These two limitations are interconnected and both are due to a limited theoretical understanding of the optimal power allocation structure in MIMO cooperative networks (MIMO-CN). In this paper, we study the structural properties of the optimal power allocation in MIMO-CN with per-node power constraints. More specifically, we show that the optimal power allocations at the source and each relay follow a matching structure in MIMO-CN. This result generalizes the power allocation result under the basic three-node setting to the multi-relay setting, for which the optimal power allocation structure has been heretofore unknown. We further quantify the performance gain due to cooperative relay and establish a connection between cooperative relay and pure relay. Finally, based on these structural insights, we reduce the MIMO-CN rate maximization problem to an equivalent scalar formulation. We then propose a global optimization method to solve this simplified and equivalent problem.

It has been shown that cooperative communications (CC) has the potential to significantly increase the capacity of wireless networks. However, most of the existing results are limited to single-hop wireless networks. To explore the behavior of CC in multi-hop wireless networks, we study a joint optimization problem of relay node assignment and flow routing for a group of sessions. We develop a mathematical model and propose a solution procedure based on the branch-and-bound framework augmented with cutting planes (BB-CP). We design several novel components to speed-up the computational time of BB-CP. Via numerical results, we show the potential rate gain that can be achieved by incorporating CC in multi-hop networks.

This paper addresses alternative formulations and model enhancements for two combinatorial optimization problems that arise in subassembly matching problems. The first problem seeks to minimize the total deviation in certain quality characteristics for the resulting final products from a vector of target values, whereas the second aims at maximizing the throughput under specified tolerance restrictions. We propose set partitioning and packing models in concert with a specialized column generation (CG) procedure that significantly outperform alternative assignment-based formulations presented in the literature, even when the latter are enhanced via tailored symmetry-defeating strategies. In particular, we emphasize the critical importance of incorporating a complementary CG feature to consistently produce near-optimal solutions to the proposed set partitioning and packing models. Extensive computational results are presented to demonstrate the relative effectiveness of the different proposed modelling and algorithmic strategies.

This paper develops and analyzes a family of models to predict operating daily airline schedules in the continental United States for future years. The study presented is part of an integrated supply-demand framework to study the evolution of the airline industry. The airline schedule is an important service variable that influences other factors of interest such as demand, profit, and load factor. Our approach attempts to predict the daily airline schedule for a given year, given the annual demand and schedule for the previous year, while minimizing the operating costs due to changes in the schedule. The modeling framework is comprised of three distinct sub-parts: a frequency generator to derive the optimal frequency in a market; a mechanism to obtain an integral solution from a fractional solution produced by the frequency generator; and a timetable generator to derive a daily operating schedule from the output of the second step. The model is validated using actual operating frequency information obtai...

In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0–1 linear programming problems. Similarly to delayed relax-and-cut approaches, the procedure dynamically appends valid inequalities to the linear programming relaxation as induced by the Reformulation-Linearization Technique (RLT). A Lagrangian dual algorithm that is augmented with a primal solution recovery scheme is applied implicitly to a full or partial first-level RLT relaxation, where RLT constraints that are currently being violated by the primal estimate are dynamically generated within the Lagrangian dual problem, thus controlling the size of the dual space while effectively capturing the strength of the RLT-enhanced relaxation. We present a preliminary computational study to demonstrate the efficacy of this approach.

In a recent paper, (see Xu et al. in Optim. Lett. 5(2):307–317, 2011) presented an algorithm for solving linear fractional programming problems over networks, and proposed and analyzed a dual formulation for this problem. This note shows that the algorithm of Xu et al. is precisely that of Gilmore and Gomory (Oper. Res. 11(6):863–888, 1963), and the related duality results follow directly by adopting the transformation of Charnes and Cooper (Naval Logist. Q. 9(3–4):181–186, 1962) to equivalently rewrite the linear fractional program as a linear program and then applying linear programming duality.

Cognitive radio networks (CRNs) have the potential to utilize spectrum efficiently and are positioned to be the core technology for the next-generation multihop wireless networks. An important problem for such networks is its capacity. We study this problem for CRNs in the SINR (signal-to-interference-and-noise-ratio) model, which is considered to be a better characterization of interference (but also more difficult to analyze) than disk graph model. The main difficulties of this problem are two-fold. First, SINR is a nonconvex function of transmission powers; an optimization problem in the SINR model is usually a nonconvex program and NP-hard in general. Second, in the SINR model, scheduling feasibility and the maximum allowed flow rate on each link are determined by SINR at the physical layer. To maximize capacity, it is essential to follow a cross-layer approach, but joint optimization at physical (power control), link (scheduling), and network (flow routing) layers with the SINR function is inherently difficult. In this paper, we give a mathematical characterization of the joint relationship among these layers. We devise a solution procedure that provides a (1- \varepsilon ) optimal solution to this complex problem, where \varepsilon is the required accuracy. Our theoretical result offers a performance benchmark for any other algorithms developed for practical implementation. Using numerical results, we demonstrate the efficacy of the solution procedure and offer quantitative understanding on the interaction of power control, scheduling, and flow routing in a CRN.

In this paper, we study an airspace flow program in the context of weather-related disruptions by augmenting the airspace planning and collaborative decision-making model (APCDM). The proposed model selects among alternative flight plans for the affected flights while integrating slot exchange mechanisms induced by multiple ground delay programs (GDPs) to permit airlines to improve flight efficiencies through a mediated bartering of assigned slots, and simultaneously considering issues related to sector workloads and airspace conflicts, as well as overall equity concerns among the involved airlines in regard to accepted slot trades and flight plans. The APCDM is enhanced to include (a) the selection of slot exchange trade offers suggested by the airlines based on their allotted slots under a GDP; (b) connections between continuing flights; and (c) several alternative equity concepts. Both full and light versions of this model are developed and tested using realistic data derived from the enhanced traffic management system data provided by the Federal Aviation Administration.

In this paper, we explore certain algorithmic strategies for accelerating the con- vergence of Benders decomposition method via the generation of maximal nondominated cuts. Based on interpreting the seminal work of Magnanti and Wong (Operations Research, 29(3), 464-484, 1981) for generating nondominated cuts within a multiobjective frame- work, we propose an algorithmic strategy that utilizes a preemptively small perturbation of the right-hand-side of the Benders subproblem to generate maximal nondominated Benders cuts, as well as a complimentary strategy that generates an additional cut in each iteration via an alternative emphasis on decision variable weights. We also examine the computa- tional effectiveness of solving a secondary subproblem using an objective cut as proposed by Magnanti and Wong versus identifying the Pareto-optimality region for cut generation by utilizing complementary slackness conditions. In addition, we exhibit how a standard fea- sibility cut can be extracted from the solution of subproblems that generate only optimality cuts through the use of artificial variables. With Magnanti and Wong's baseline procedure approximated during implementation via the use of a core point estimation technique (Pa- padakos in Computers and Operations Research, 36(1), 176-195, 2009), these algorithmic strategies are tested on instances from the literature concerning the fixed charge network flow program.

We study a multicast communication problem in a multi-hop ad hoc network where each node is equipped with a cognitive radio (CR). The goal is to minimize the required network-wide resource to support a set of multicast sessions, with a given bit rate requirement for each multicast session. The unique characteristics and complexity associated with CR distinguish this problem from existing multicast problems for ad hoc networks. In this paper, we formulate this problem via a cross-layer approach by taking consideration of scheduling and routing jointly. Although the problem formulation is in the form of a mixed-integer linear program, we develop a polynomial-time algorithm that offers highly competitive solutions. By comparing the solution values with a lower bound, we show that the proposed algorithm can provide a solution that is close to the optimum.

In this paper a discrete location model for non-essential service facilities planning is described, which seeks the number, location, and size of facilities, that maximizes the total expected demand attracted by the facilities. It is assumed that the demand for service is sensitive to the distance from facilities and to their size. It is also assumed that facilities must satisfy a threshold level of demand (facilities are not economically viable below that level). A Mixed-Integer Nonlinear Programming (MINLP) model is proposed for this problem. A branch-and-bound algorithm is designed for solving this MINLP and its convergence to a global minimum is established. A finite procedure is also introduced to find a feasible solution for the MINLP that reduces the overall search in the binary tree generated by the branch-and-bound algorithm. Some numerical results using a GAMS/MINOS implementation of the algorithm are reported to illustrate its efficacy and efficiency in practice.

This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds, which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global optimality in comparison with the basic RLT procedure as well as the commercial software BARON.

In this paper, we revisit the problem of determining the minimum-length schedule that satisfies certain traffic demands in a wireless network. Traditional approaches for the determination of minimum-length schedules are based on a collision channel model, in which neighboring transmissions cause destructive interference if and only if they are within the "interference region" of the receiving nodes. By contrast, we adopt here a more realistic model for the physical layer by requiring that a threshold be exceeded by the signal-to-interference-plus-noise ratio (SINR) for a transmission to be successful. We present a novel formulation of the problem that incorporates various power and rate adaptation schemes while seamlessly integrating the generation of "matchings" (i.e., sets of links that can be activated simultaneously) by taking into consideration the SINR constraints at the receivers. For the formulated problem, we propose a column-generation-based solution method and show that it theoretically converges to a globally optimal solution, with a potential advantage of not having to enumerate all the feasible matchings a priori. We also discuss the influence of power control, spatial reuse, and variable transmission rates on network performance. Furthermore, we include aspects of the routing problem and provide computational results for our proposed column-generation-based solution procedure.

Due to copyright restrictions, the access to the full text of this article is only available via subscription. The main airline operations consist of schedule planning, fleet assignment, aircraft routing, and crew scheduling. To improve profitability, we present in this paper an integrated fleet assignment model with schedule planning by simultaneously considering optional flight legs to select along with the assignment of aircraft types to all scheduled legs. In addition, we consider itinerary-based demands for multiple fare classes. A polyhedral analysis is conducted of the proposed mixed-integer programming model to tighten its representation via several classes of valid inequalities. Solution approaches are developed by applying Benders' decomposition method to the resulting lifted model, and computational results are presented using real data obtained from a major U.S. airline to demonstrate the efficacy of the proposed procedures. NSF ; Fatimah Alnijris' Research Chair for Advanced Manufacturing Technology

Due to copyright restrictions, the access to the full text of this article is only available via subscription. This paper investigates the quota version of the Prize Collecting Steiner Tree Problem (PCSTP) on a graph as a generalization of the well-known Steiner tree problem. For this challenging network design problem that arises in telecommunication settings, we present three MIP formulations: (a) the first one is a compact Miller-Tucker-Zemlin (MTZ-) based formulation, (b) the second one is derived through lifting the MTZ constraints, and (c) the third one is based on the RLT technique. We report the results of extensive computational experiments on large PCSTP instances, having up to 2500 nodes using a general-purpose MIP solver.

This paper presents a new model for a special type of traveling salesman problem called the High Multiplicity Asymmetric Traveling Salesman Problem (HMATSP). The formulation adopts a flow-based subtour elimination structure and establishes its validity for this problem. Also, we present computational results to demonstrate the efficacy of our modeling approach. The model is then incorporated as a substructure in a formulation for the lot-sizing problem involving parallel machines and sequence-dependent setup costs, also known as the Chesapeake Problem, and related test problems are solved to optimality for the first time in the literature.

We address a doubles tennis scheduling problem in the context of a training tournament, and develop a 0–1 mixed-integer programming model that attempts to balance the partnership and the opponentship pairings among the players. We propose effective symmetry-defeating strategies that impose certain decision hierarchies within the model, which serve to significantly enhance algorithmic performance via their pruning effect. We also discuss the concept of symmetry compatible formulations, and highlight the importance of crafting formulations in discrete optimization in a fashion that enhances the interplay between the original model structure, branch-and-bound algorithms (as implemented in commercial packages such as CPLEX), and the structure of specific symmetry-defeating hierarchical constraints. Finally, various specialized heuristics are devised and are computationally evaluated along with the exact solution schemes using a set of realistic practical test problems.

We present a novel dynamic network interdiction model that accounts for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. For the resulting minimax model, we develop a reformulation that facilitates a direct solution procedure using commercial software or via a proposed alternating heuristic. We examine certain related stability and convergence issues, demonstrate special convergence cases, and provide insights into the computational performance of the solution procedures.

In this paper, we consider a particular class of network flow problems that seeks a shortest path, if it exists, between a source node s and a destination node d in a connected digraph, such that we arrive at node d at a specified time τ while leaving node s no earlier than a lower-bounding time LB, and where the availability of each network link is time-dependent in the sense that it can be traversed only during specified intervals of time. We refer to this problem as the reverse time-restricted shortest path problem (RTSP), and it arises, for example, in the context of generating flight plans within air traffic management approaches under severe convective weather conditions. We show that this problem is NP-hard in general, but is polynomially solvable under a special regularity condition. A pseudo-polynomial time dynamic programming algorithm is developed to solve Problem RTSP, along with an effective heap implementation strategy. Computational results using real flight generation test cases as well as random simulated problems are presented.

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.

Due to copyright restrictions, the access to the full text of this article is only available via subscription. We describe models and exact solutions approaches for an integrated aircraft fleeting and routing problem arising at TunisAir. Given a schedule of flights to be flown, the problem consists of determining a minimum cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenanceactivity constraints. We investigate two tailored approaches for this problem: Benders decomposition and branch-and-price. Computational experiments conducted on real-data provide evidence that the branch-and-price approach outperforms the Benders decomposition approach and delivers optimal solutions within moderate CPUtimes. On the other hand, the Benders algorithm yields very quickly high quality near-optimal solutions. NSF ; Fatimah Alnijris’ Research Chair for Advanced Manufacturing Technology

The Reformulation-Linearization Technique (RLT) provides a hierarchy of relaxations spanning the spectrum from the continuous relaxation to the convex hull representation for linear 0-1 mixed-integer and general mixed-discrete programs. We show in this paper that this result holds identically for semi-infinite programs of this type. As a consequence, we extend the RLT methodology to describe a construct for generating a hierarchy of relaxations leading to the convex hull representation for bounded 0-1 mixed-integer and general mixed-discrete convex programs, using an equivalent semi-infinite linearized representation for such problems as an intermediate stepping stone in the analysis. For particular use in practice, we provide specialized forms of the resulting first-level RLT formulation for such mixed 0-1 and discrete convex programs, and illustrate these forms through two examples.