A column generation based heuristic for sensor placement,activity scheduling and data routing in wireless sensor networks

A wireless sensor network is a network consisting of distributed autonomous electronic devices called sensors. In this work, we develop a mixed-integer linear programming model to maximize the network lifetime by optimally determining locations of sensors and sinks, sensor-to-sink data flows, and activity schedules of the deployed sensors subject to coverage, flow conservation, energy consumption and budget constraints. Since solving this model is difficult except for very small instances, we propose a heuristic method which works on a reformulation of the problem. In the first phase of this heuristic, the linear programming relaxation of the reformulation is solved by column generation. The second phase consists of constructing a feasible solution for the original problem using the columns obtained in the first phase. Computational experiments conducted on a set of test instances indicate that both the accuracy and the efficiency of the proposed heuristic is quite promising.     

A Slope Scaling/Lagrangean Perturbation Heuristic with Long-Term Memory for Multicommodity Capacitated Fixed-Charge Network Design

This paper describes a slope scaling heuristic for solving the multicomodity capacitated fixed-charge network design problem. The heuristic integrates a Lagrangean perturbation scheme and intensification/diversification mechanisms based on a long-term memory. Although the impact of the Lagrangean perturbation mechanism on the performance of the method is minor, the intensification/diversification components of the algorithm are essential for the approach to achieve good performance. The computational results on a large set of randomly generated instances from the literature show that the proposed method is competitive with the best known heuristic approaches for the problem. Moreover, it generally provides better solutions on larger, more difficult, instances.     

A two-echelon stochastic facility location model for humanitarian relief logistics

We develop a two-stage stochastic programming model for a humanitarian relief logistics problem where decisions are made for pre- and post-disaster rescue centers, the amount of relief items to be stocked at the pre-disaster rescue centers, the amount of relief item flows at each echelon, and the amount of relief item shortage. The objective is to minimize the total cost of facility location, inventory holding, transportation and shortage. The deterministic equivalent of the model is formulated as a mixed-integer linear programming model and solved by a heuristic method based on Lagrangean relaxation. Results on randomly generated test instances show that the proposed solution method exhibits good performance up to 25 scenarios. We also validate our model by calculating the value of the stochastic solution and the expected value of perfect information.     

Lower and upper bounds for a two-stage capacitated facility location problem with handling costs

We study in this paper multi-product facility location problem in a two-stage supply chain in which plants have production limitation, potential depots have limited storage capacity and customer demands must be satisfied by plants via depots. In the paper, handling cost for batch process in depots is considered in a realistic way by a set of capacitated handling modules. Each module can be regards as alliance of equipment and manpower. The problem is to locate depots, choose appropriate handling modules and to determine the product flows from the plants, opened depots to customers with the objective to minimize total location, handling and transportation costs. For the problem, we developed a hybrid method. The initial lower and upper bounds are provided by applying a Lagrangean based on local search heuristic. Then a weighted Dantzig–Wolfe decomposition and path-relinking combined method are proposed to improve obtained bounds. Numerical experiments on 350 randomly generated instances demonstrate our method can provide high quality solution with gaps below 2%.     

Lagrangean heuristic for primary routes assignment in survivable connection-oriented networks

Our discussion in this article centers on the application of a Lagrangean relaxation and a subgradient optimization technique to the problem of primary route assignment (PRA) in survivable connection-oriented networks. The PRA problem consists in a static optimization of primary routes minimizing the Lost Flow in Node (LFN) function. The major contribution of this work is a combination of the Lagrangean relaxation with other heuristic algorithms. We evaluate the performance of the proposed Lagrangean-based heuristic by making a comparison with their counterparts including evolutionary algorithm and GRASP using various network topologies and demand patterns. The results of simulation tests show that the new algorithm provides sub-optimal results, which are better than other heuristics.     

Multi-Item, Multi-Facility Supply Chain Planning: Models, Complexities, and Algorithms

We propose a planning model for products manufactured across multiple manufacturing facilities sharing similar production capabilities. The need for cross-facility capacity management is most evident in high-tech industries that have capital-intensive equipment and a short technology life cycle. We propose a multicommodity flow network model where each commodity represents a product and the network structure represents manufacturing facilities in the supply chain capable of producing the products. We analyze in depth the product-level (single-commodity, multi-facility) subproblem when the capacity constraints are relaxed. We prove that even the general-cost version of this uncapacitated subproblem is NP-complete. We show that there exists an optimization algorithm that is polynomial in the number of facilities, but exponential in the number of periods. We further show that under special cost structures the shortest-path algorithm could achieve optimality. We analyze cases when the optimal solution does not correspond to a source-to-sink path, thus the shortest path algorithm would fail. To solve the overall (multicommodity) planning problem we develop a Lagrangean decomposition scheme, which separates the planning decisions into a resource subproblem, and a number of product-level subproblems. The Lagrangean multipliers are updated iteratively using a subgradient search algorithm. Through extensive computational testing, we show that the shortest path algorithm serves as an effective heuristic for the product-level subproblem (a mixed integer program), yielding high quality solutions with only a fraction (roughly 2%) of the computer time.     

A Lagrangean-based heuristics for the target covering problem in wireless sensor network

We study the target coverage problem in wireless sensor networks. The problem consists in maximizing the network lifetime by grouping the sensors in disjoint set covers of the targets. A binary integer programing model is formulated to maximize the network lifetime. Since the problem is NP-complete, we provide an iterative approximation based on Lagrangean relaxation and subgradient optimization.     

Hierarchical design of an integrated production and 2-echelon distribution system

This study uses the method of Lagrangean relaxation in the hierarchical design of an integrated model of production–distribution functions in a 2-echelon system. A mixed integer mathematical model is developed with a centralized planning perspective to address production and distribution decisions simultaneously. In order to solve the resulting large-scale problem, the Lagrangean relaxation is used to decouple the imbedded distribution and production subproblems, and subgradient optimization is implemented to coordinate the information flow between these in a hierarchical manner. This corresponds to a decentralized organizational design where a central agent coordinates the information exchange between the distribution and production organizational units. A forward heuristic designed to solve the distribution subproblem is shown to provide good solutions. Hierarchical interdependency is incorporated into the Lagrangean heuristic such that distribution decisions are placed in the top level to restrict the solution of the production subproblem in the lower level.     

An effective heuristic for large-scale capacitated facility location problems

The Capacitated Facility Location Problem (CFLP) consists of locating a set of facilities with capacity constraints to satisfy the demands of a set of clients at the minimum cost. In this paper we propose a simple and effective heuristic for large-scale instances of CFLP. The heuristic is based on a Lagrangean relaxation which is used to select a subset of “promising” variables forming the core problem and on a Branch-and-Cut algorithm that solves the core problem. Computational results on very large scale instances (up to 4 million variables) are reported.     

Lagrangean relaxation

This paper reviews some of the most intriguing results and questions related to Lagrangean relaxation. It recalls essential properties of the Lagrangean relaxation and of the Lagrangean function, describes several algorithms to solve the Lagrangean dual problem, and considers Lagrangean heuristics, ad-hoc or generic, because these are an integral part of any Lagrangean approximation scheme. It discusses schemes that can potentially improve the Lagrangean relaxation bound, and describes several applications of Lagrangean relaxation, which demonstrate the flexibility of the approach, and permit either the computation of strong bounds on the optimal value of the MIP problem, or the use of a Lagrangean heuristic, possibly followed by an iterative improvement heuristic. The paper also analyzes several interesting questions, such as why it is sometimes possible to get a strong bound by solving simple problems, and why an a-priori weaker relaxation can sometimes be “just as good” as an a-priori stronger one.     

Designing vehicle routes for a mix of different request types,under time windows and loading constraints

This article introduces and solves a new rich routing problem integrated with practical operational constraints. The problem examined calls for the determination of the optimal routes for a vehicle fleet to satisfy a mix of two different request types. Firstly, vehicles must transport three-dimensional, rectangular and stackable boxes from a depot to a set of predetermined customers. In addition, vehicles must also transfer products between pairs of pick-up and delivery locations. Service of both request types is subject to hard time window constraints. In addition, feasible palletization patterns must be identified for the transported products. A practical application of the problem arises in the transportation systems of chain stores, where vehicles replenish the retail points by delivering products stored at a central depot, while they are also responsible for transferring stock between pairs of the retailer network. To solve this very complex combinatorial optimization problem, our major objective was to develop an efficient methodology whose required computational effort is kept within reasonable limits. To this end, we propose a local search-based framework for optimizing vehicle routes, in which feasible loading arrangements are identified via a simple-structured packing heuristic. The algorithmic framework is enhanced with various memory components which store and retrieve useful information gathered through the search process, in order to avoid any duplicate unnecessary calculations. The proposed solution approach is assessed on newly introduced benchmark instances.     

Optimization methods for pipeline transportation of natural gas with variable specific gravity and compressibility

In this paper, the problem of flow maximization in pipeline systems for transmission of natural gas is addressed. We extend previously suggested models by incorporating the variation in pipeline flow capacities with gas specific gravity and compressibility. Flow capacities are modeled as functions of pressure, compressibility and specific gravity by the commonly-used Weymouth equation, and the California Natural Gas Association method is used to model compressibility as a function of specific gravity and pressure. The sources feeding the transmission network do not necessarily supply gas with equal specific gravity. In our model, it is assumed that when different flow streams enter a junction point, the specific gravity of the resulting flow is a weighted average of the specific gravities of entering flows. We also assume the temperature to be constant, and the system to be in steady state. Since the proposed model is non-convex, and global optimization hence can be time consuming, we also propose a heuristic method based on an iterative scheme in which a simpler NLP model is solved in each iteration. Computational experiments are conducted in order to assess the computability of the model by applying a global optimizer, and to evaluate the performance of the heuristic approach. When applied to a wide set of test instances, the heuristic method provides solutions with deviations less than 10% from optimality, and in many instances turns out to be exact. We also report several experiments demonstrating that letting the compressibility and the specific gravity be global constants can lead to significant errors in the estimates of the total network capacity.     

Simultaneous evacuation and entrance planning in complex building based on dynamic network flows

This paper presents mathematical models and a heuristic algorithm that address a simultaneous evacuation and entrance planning. For the simultaneous evacuation and entrance planning, four types of mathematical models based on the discrete time dynamic network flow model are developed to provide the optimal routes for evacuees and responders within a critical timeframe. The optimal routes obtained by the mathematical models can minimize the densification of evacuees and responders into specific areas. However, the mathematical model has a weakness in terms of long computation time for the large-size problem. To overcome the limitation, we developed a heuristic algorithm. We also analyzed the characteristics of each model and the heuristic algorithm by conducting case studies. This study pioneers area related to evacuation planning by developing and analyzing four types of mathematical models and a heuristic algorithm which take into account simultaneous evacuation and entrance planning.     

A model and two heuristic approaches for a forage harvester planning problem: a case study

This work considers a decision problem about orders of owners and routes of smallholdings for a harvester in an agricultural cooperative in which each owner has a proposal about the instant time in which he would like that the machine starts the activity in his land and the different smallholdings of each owner should be processed as a block. A binary linear programming model is introduced in order to reducing costs. Solving the model for actual size instances is computationally burdensome. Hence, we introduce and implement two heuristic algorithms to reduce the computational time. The heuristics are applied to the real case of the cooperative “Os Irmandiños” with a large number of owners and smallholdings. The numerical results show that the heuristics can solve large instances effectively with reasonable computational effort.     

Maximizing system lifetime in wireless sensor networks

One of the most critical issues in wireless sensor networks is represented by the limited availability of energy on network nodes; thus, making good use of energy is necessary to increase network lifetime. In this paper, we define network lifetime as the time spanning from the instant when the network starts functioning properly, i.e., satisfying the target level of coverage of the area of interest, until the same level of coverage cannot be guaranteed any more due to lack of energy in sensors. To maximize system lifetime, we propose to exploit sensor spatial redundancy by defining subsets of sensors active in different time periods, to allow sensors to save energy when inactive. Two approaches are presented to maximize network lifetime: the first one, based on column generation, must run in a centralized way, whereas the second one is based on a heuristic algorithm aiming at a distributed implementation. To assess their performance and provide guidance to network design, the two approaches are compared by varying several network parameters. The column generation based approach typically yields better solutions, but it may be difficult to implement in practice. Nevertheless it provides both a good benchmark against which heuristics may be compared and a modeling framework which can be extended to deal with additional features, such as reliability.     

Single-commodity robust network design problem: Complexity,instances and heuristic solutions

We study a single-commodity Robust Network Design problem (RND) in which an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. In each scenario, a subset of the nodes is exchanging flow. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. Previously conducted computational investigations on the problem motivated the study of the complexity of some special cases and we present complexity results on them, including hypercubes. In turn, these results lead to the definition of new instances (random graphs with {−1, 0, 1} balances) that are computationally hard for the natural flow formulation. These instances are then solved by means of a new heuristic algorithm for RND, which consists of three phases. In the first phase the graph representing the network is reduced by heuristically deleting a subset of the arcs, and a feasible solution is built. The second phase consists of a neighborhood search on the reduced graph based on a Mixed-Integer (Linear) Programming (MIP) flow model. Finally, the third phase applies a proximity search approach to further improve the solution, taking into account the original graph. The heuristic is tested on the new instances, and the comparison with the solutions obtained by Cplex on a natural flow formulation shows the effectiveness of the proposed method.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

Material allocation in MRP with tardiness penalties

In this paper, we address some flaws in the material allocation function of Materials Requirements Planning (MRP). The problem formulation differs from standard MRP logic in certain important ways: start and finish times for orders are forced to be realistic and material allocations are made to minimize the total tardiness penalty associated with late completion. We show that the resulting MRP material allocation problem is NP-hard in the strong sense. A lower bound and a heuristic are developed from a mixed integer linear formulation and its Lagrangean relaxation. The lower bound and the heuristics are closer to the optimum in cases where there is either abundant material or considerable competition for material; in intermediate cases, small perturbations in material allocation can have a significant effect. A group of heuristics based on the MRP approach and its modifications is examined; they are optimal under certain conditions. An improvement method that preserves priorities inherent in any given starting solution is also presented. The Lagrangean heuristic performs better than the MRP based heuristics for a set of 3900 small problems, yielding solutions that are about 5% to 10% over the optimal. The best MRP based heuristic does about as well as the Lagrangean heuristic on a set of 120 larger problems, and is 25% to 40% better than the standard MRP approach, on the data sets tested.     

An Integer Multicommodity Flow Model Applied to the Rerostering of Nurse Schedules

The problem of rerostering service schedules is very common in organizations that work shifts around the clock every day of the year with a set number of employees. Whenever one or more workers announce that they will not be able to attend to tasks previously assigned in their schedule, those tasks must be performed at the expense of alterations in the schedules of other workers. These changes should not conflict with the rules laid down by the administration and employment contracts and should affect the previous schedules as little as possible. This is a difficult real problem calling for a computational tool to cope with it easily. In the paper the issue is described in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. A heuristic was implemented as a first approach to solving the problem. Subsequently the integer linear programming formulation of the multicommodity flow model and two linear relaxations were tested using CPLEX [2] optimizers. The computational results reported regard real instances from a Lisbon state hospital. Satisfactory rosters were obtained within acceptable computational times in all instances tested, either with the integer optimizer, or with the heuristic. This being so, refinements will be undertaken to embed these methodologies in a decision support system that may assist the head nurse in her daily rerostering activities.