Solving a minimum-power covering problem with overlap constraint for cellular network design

We consider a type of covering problem in cellular networks. Given the locations of base stations, the problem amounts to determining cell coverage at minimum cost in terms of the power usage. Overlap between adjacent cells is required in order to support handover. The problem we consider is NP-hard. We present integer linear models and study the strengths of their continuous relaxations. Preprocessing is used to reduce problem size and tighten the models. Moreover, we design a tabu search algorithm for finding near-optimal solutions effectively and time-efficiently. We report computational results for both synthesized instances and networks originating from real planning scenarios. The results show that one of the integer models leads to tight bounds, and the tabu search algorithm generates high-quality solutions for large instances in short computing time.     

A branch-and-price approach for the partition coloring problem

This work proposes a new integer programming model for the partition coloring problem and a branch-and-price algorithm to solve it. Experiments are reported for random graphs and instances originating from routing and wavelength assignment problems arising in telecommunication network design. We show that our method largely outperforms previously existing approaches.     

A column generation approach for the split delivery vehicle routing problem

A column generation approach is presented for the split delivery vehicle routing problem with large demand. Columns include route and delivery amount information. Pricing sub-problems are solved by a limited-search-with-bound algorithm. Feasible solutions are obtained iteratively by fixing one route once. Numerical experiments show better solutions than in the literature.     

A solution method for a car fleet management problem with maintenance constraints

The problem retained for the ROADEF’99 international challenge was an inventory management problem for a car rental company. It consists in managing a given fleet of cars in order to satisfy requests from customers asking for some type of cars for a given time period. When requests exceed the stock of available cars, the company can either offer better cars than those requested, subcontract some requests to other providers, or buy new cars to enlarge the available stock. Moreover, the cars have to go through a maintenance process at a regular basis, and there is a limited number of workers that are available to perform these maintenances. The problem of satisfying all customer requests at minimum cost is known to be NP-hard. We propose a solution technique that combines two tabu search procedures with algorithms for the shortest path, the graph coloring and the maximum weighted independent set problems. Tests on benchmark instances used for the ROADEF’99 challenge give evidence that the proposed algorithm outperforms all other existing methods (thirteen competitors took part to this contest).     

Heuristic algorithms for the multi-depot ring-star problem

In this paper, we consider the problem of designing urban optical networks. In particular, given a set of telephone exchanges, we must design a collection of ring-stars, where each ring-star is a cycle composed of a telephone exchange, some customers, some transition points used to save routing costs and customers not on the cycle connected to the cycle by a single edge. The ring topology is chosen in many fiber optic communication networks since it allows to prevent the loss of connection due to a single edge or even a single node failure. The objective is to minimize the total cost of the optical network which is mainly due to the excavation costs. We call this problem Multi-Depot Ring-Star Problem (MDRSP) and we formulate it as an optimization problem in Graph Theory. We present lower bounds and heuristic algorithms for the MDRSP. Computational results on randomly generated instances and real-life datasets are also presented.     

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.     

Comparison of wavelength requirements between two wavelength assignment methods in survivable WDM networks

We consider the routing and wavelength assignment (RWA) in survivable WDM network. A path protection scheme assumed and two different wavelength assignment methods for protection paths are considered. Integer programming formulations of RWA under two wavelength assignment methods are proposed and we devised algorithms to solve them. Test results show that the difference of wavelength requirements between two wavelength assignment methods is 5–30–     

0-1 reformulations of the multicommodity capacitated network design problem

We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

An efficient tabu algorithm for the single row facility layout problem

The general goal of the facility layout problem is to arrange a given number of facilities to minimize the total cost associated with the known or projected interactions between them. One of the special classes of the facility layout problem is the Single Row Facility Layout Problem (SRFLP), which consists of finding an optimal linear placement of rectangular facilities with varying dimensions on a straight line. This paper first presents and proves a theorem to find the optimal solution of a special case of SRFLP. The results obtained by this theorem prove to be very useful in reducing the computational efforts when a new algorithm based on tabu search for the SRFLP is proposed in this paper. Computational results of the proposed algorithm on benchmark problems show the greater efficiency of the algorithm compared to the other heuristics for solving the SRFLP.     

Biclique completion problems for multicast network design

This paper considers the problem of aggregating several multicast sessions. A multicast session is defined as a subset of clients requiring the same information. Besides, each client can require several multicast sessions. A telecommunication network cannot manage many multicast sessions at the same time. It is hence necessary to group the sessions into a limited number of clusters. The problem then consists in aggregating the sessions into clusters to limit the number of unnecessary information sent to clients. The strong relationship of the problems with biclique problems in bipartite graph is established. We then model the problems using integer quadratic and linear programming formulations. We investigate some properties to strengthen the models. Several algorithms are provided and compared with a series of numerical experiments.     

A column generation approach to the discrete barycenter problem

The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of discrete probability measures. Although an exact barycenter is computable through linear programming, the underlying linear program can be extremely large. For worst-case input, a best known linear programming formulation is exponential in the number of variables, but has a low number of constraints, making it an interesting candidate for column generation.In this paper, we devise and study two column generation strategies: a natural one based on a simplified computation of reduced costs, and one through a Dantzig–Wolfe decomposition. For the latter, we produce efficiently solvable subproblems, namely, a pricing problem in the form of a classical transportation problem. The two strategies begin with an efficient computation of an initial feasible solution. While the structure of the constraints leads to the computation of the reduced costs of all remaining variables for setup, both approaches may outperform a computation using the full program in speed, and dramatically so in memory requirement. In our computational experiments, we exhibit that, depending on the input, either strategy can become a best choice.     

A systematic two phase approach for the nurse rostering problem

Nurse rostering is an NP-hard combinatorial problem which makes it extremely difficult to efficiently solve real life problems due to their size and complexity. Usually real problem instances have complicated work rules related to safety and quality of service issues in addition to rules about quality of life of the personnel. For the aforementioned reasons computer supported scheduling and rescheduling for the particular problem is indispensable. The specifications of the problem addressed were defined by the First International Nurse Rostering Competition (INRC2010) sponsored by the leading conference in the Automated Timetabling domain, PATAT-2010. Since the competition imposed quality and time constraint requirements, the problem instances were partitioned into sub-problems of manageable computational size and were then solved sequentially using Integer Mathematical Programming. A two phase strategy was implemented where in the first phase the workload for each nurse and for each day of the week was decided while in the second phase the specific daily shifts were assigned. In addition, local optimization techniques for searching across combinations of nurses’ partial schedules were also applied. This sequence is repeated several times depending on the available computational time. The results of our approach and the submitted software produced excellent solutions for both the known and the hidden problem instances, which in respect gave our team the first position in all tracks of the INRC-2010 competition.     

Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges

Wireless sensor networks involve many different real-world contexts, such as monitoring and control tasks for traffic, surveillance, military and environmental applications, among others. Usually, these applications consider the use of a large number of low-cost sensing devices to monitor the activities occurring in a certain set of target locations. We want to individuate a set of covers (that is, subsets of sensors that can cover the whole set of targets) and appropriate activation times for each of them in order to maximize the total amount of time in which the monitoring activity can be performed (network lifetime), under the constraint given by the limited power of the battery contained in each sensor. A variant of this problem considers that each sensor can be activated in a certain number of alternative power levels, which determine different sensing ranges and power consumptions. We present some heuristic approaches and an exact approach based on the column generation technique. An extensive experimental phase proves the advantage in terms of solution quality of using adjustable sensing ranges with respect to the classical single range scheme.     

The multi-depot vehicle routing problem with inter-depot routes

This article addresses an extension of the multi-depot vehicle routing problem in which vehicles may be replenished at intermediate depots along their route. It proposes a heuristic combining the adaptative memory principle, a tabu search method for the solution of subproblems, and integer programming. Tests are conducted on randomly generated instances.     

Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks

In this paper, we consider the duty scheduling of sensor activities in wireless sensor networks to maximize the lifetime. We address full target coverage problems contemplating sensors used for sensing data and transmit it to the base station through multi-hop communication as well as sensors used only for communication purposes. Subsets of sensors (also called covers) are generated. Those covers are able to satisfy the coverage requirements as well as the connection to the base station. Thus, maximum lifetime can be obtained by identifying the optimal covers and allocate them an operation time. The problem is solved through a column generation approach decomposed in a master problem used to allocate the optimal time interval during which covers are used and in a pricing subproblem used to identify the covers leading to maximum lifetime. Additionally, Branch-and-Cut based on Benders’ decomposition and constraint programming approaches are used to solve the pricing subproblem. The approach is tested on randomly generated instances. The computational results demonstrate the efficiency of the proposed approach to solve the maximum network lifetime problem in wireless sensor networks with up to 500 sensors.     

A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem

In the multiple container loading cost minimization problem (MCLCMP), rectangular boxes of various dimensions are loaded into rectangular containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally modeled as a set cover problem. We generalize the set cover formulation by introducing a new parameter to model the gross volume utilization of containers in a solution. The state-of-the-art algorithm tackles the MCLCMP using the prototype column generation (PCG) technique. PCG is an effective technique for speeding up the column generation technique for extremely hard optimization problems where their corresponding pricing subproblems are NP-hard. We propose a new approach to the MCLCMP that combines the PCG technique with a goal-driven search. Our goal-driven prototype column generation (GD-PCG) algorithm improves the original PCG approach in three respects. Computational experiments suggest that all three enhancements are effective. Our GD-PCG algorithm produces significantly better solutions for the 350 existing benchmark instances than all other approaches in the literature using less computation time. We also generate two new set instances based on industrial data and the classical single container loading instances.     

A column generation approach for the unconstrained binary quadratic programming problem

This paper proposes a column generation approach based on the Lagrangean relaxation with clusters to solve the unconstrained binary quadratic programming problem that consists of maximizing a quadratic objective function by the choice of suitable values for binary decision variables. The proposed method treats a mixed binary linear model for the quadratic problem with constraints represented by a graph. This graph is partitioned in clusters of vertices forming sub-problems whose solutions use the dual variables obtained by a coordinator problem. The column generation process presents alternative ways to find upper and lower bounds for the quadratic problem. Computational experiments were performed using hard instances and the proposed method was compared against other methods presenting improved results for most of these instances.     

Improved formulation,branch-and-cut and tabu search heuristic for single loop material flow system design

The single loop material flow system design is a combinatorial optimization problem, arising in material handling system design, which amounts to designing an unidirectional loop flow pattern as well as to locate pickup and delivery stations. The objective is to minimize the time required to carry out all material flow movements between cells. In this paper, we develop valid inequalities for a previously proposed formulation. The valid inequalities are then embedded into a branch-and-cut framework which is shown to solve much larger instances to optimality than those reported in the literature. A tailored tabu search heuristic is also illustrated and computationally assessed.