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 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.     

All-integer column generation for set partitioning: Basic principles and extensions

Column generation, combined with an appropriate integer programming technique, has shown to be a powerful tool for solving huge integer programmes arising in various applications. In these column generation approaches, the master problem is often of a set partitioning type.     

Accelerating column generation for variable sized bin-packing problems

In this paper, we study different strategies to stabilize and accelerate the column generation method, when it is applied specifically to the variable sized bin-packing problem, or to its cutting stock counterpart, the multiple length cutting stock problem. Many of the algorithms for these problems discussed in the literature rely on column generation, processes that are known to converge slowly due to primal degeneracy and the excessive oscillations of the dual variables. In the sequel, we introduce new dual-optimal inequalities, and explore the principle of model aggregation as an alternative way of controlling the progress of the dual variables. Two algorithms based on aggregation are proposed. The first one relies on a row aggregated LP, while the second one solves iteratively sequences of doubly aggregated models. Working with these approximations, in the various stages of an iterative solution process, has proven to be an effective way of achieving faster convergence.     

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.     

Vehicle routing via column generation

This paper explores an approximate method for solving a routing problem in a four-level distribution which has “double-ended” demand. Routes are represented as columns in a linear program and column generation is used to improve the solution by generating new routes. The generation of new routes is based on an LP sub-problem. Its solution is rounded down to integer values to insure its feasibility as a route for inclusion in the restricted master problem. Finally, an illustrative problem is solved.     

Column generation in the integral simplex method

The integral simplex method for set partitioning problems allows only pivots-on-one to be made, which results in a primal all-integer method. In this technical note we outline how to tailor the column generation principle to this method. Because of the restriction to pivots-on-one, only local optimality can be guaranteed, and to ensure global optimality we consider the use of implicit enumeration.     

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.     

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.     

Interior point stabilization for column generation

Interior point stabilization is an acceleration method for column generation algorithms. It addresses degeneracy and convergence difficulties by selecting a dual solution inside the optimal space rather than retrieving an extreme point. The method is applied to the case of the vehicle routing problem with time windows.     

Constraint programming for computing non-stationary (R, S) inventory policies

This paper proposes a constraint programming model for computing the finite horizon single-item inventory problem with stochastic demands in discrete time periods with service-level constraints under the non-stationary version of the “periodic review, order-up-to-level” policy (i.e., non-stationary (R, S) or, simply (R_n, S_n)). It is observed that the modeling process is more natural and the required number of variables is smaller compared to the MIP formulation of the same problem. The computational tests show that the CP approach is more tractable than the conventional MIP formulation. Two different domain reduction methods are proposed to improve the computational performance of solution algorithms. The numerical experiments confirmed the effectiveness of these methods.     

Row-reduced column generation for degenerate master problems

Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to often suffer from degeneracy in the master problem. Inspired by recent advances in coping with degeneracy in the primal simplex method, we propose a row-reduced column generation method that may take advantage of degenerate solutions. The idea is to reduce the number of constraints to the number of strictly positive basic variables in the current master problem solution. The advantage of this row-reduction is a smaller working basis, and thus a faster re-optimization of the master problem. This comes at the expense of a more involved pricing subproblem, itself eventually solved by column generation, that needs to generate weighted subsets of variables that are said compatible with the row-reduction, if possible. Such a subset of variables gives rise to a strict improvement in the objective function value if the weighted combination of the reduced costs is negative. We thus state, as a by-product, a necessary and sufficient optimality condition for linear programming.     

A constraint generation algorithm for large scale linear programs using multiple-points separation

In order to solve linear programs with a large number of constraints, constraint generation techniques are often used. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. In this paper, we present a separation procedure that uses several points to generate violated constraints. The complexity of this separation procedure and of some related problems is studied. Also, preliminary computational results about the advantages of using multiple-points separation procedures over traditional separation procedures are given for random linear programs and survivable network design. They illustrate that, for some specific families of linear programs, multiple-points separation can be computationally effective.     

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–     

An inexact bundle variant suited to column generation

We give a bundle method for constrained convex optimization. Instead of using penalty functions, it shifts iterates towards feasibility, by way of a Slater point, assumed to be known. Besides, the method accepts an oracle delivering function and subgradient values with unknown accuracy. Our approach is motivated by a number of applications in column generation, in which constraints are positively homogeneous—so that zero is a natural Slater point—and an exact oracle may be time consuming. Finally, our convergence analysis employs arguments which have been little used so far in the bundle community. The method is illustrated on a number of cutting-stock problems. Research supported by INRIA New Investigation Grant “Convex Optimization and Dantzig–Wolfe Decomposition”.     

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.     

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.     

Constraint qualifications in quasidifferentiable optimization

The classical linearization procedure for differentiable nonlinear programming problems can be naturally generalized to the quasidifferentiable case. As in the classical case one has to impose so-called constraint qualifications on the constraint functions in order to ensure that optimality of a feasible point implies optimality of the nullvector for the corresponding quasilinearized problem. We present various constraint qualifications in a unified setting, propose a new one, and investigate the relations between these conditions.Supported by DFG Grant Pa 219/5-1.