A column generation approach for the rail crew re-scheduling problem

When tracks are out of service for maintenance during a certain period, trains cannot be operated on those tracks. This leads to a modified timetable, and results in infeasible rolling stock and crew schedules. Therefore, these schedules need to be repaired. The topic of this paper is the re-scheduling of crew.     

A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size

We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3].     

Solving binary cutting stock problems by column generation and branch-and-bound

We present an algorithm for the binary cutting stock problem that employs both column generation and branch-and-bound to obtain optimal integer solutions. We formulate a branching rule that can be incorporated into the subproblem to allow column generation at any node in the branch-and-bound tree. Implementation details and computational experience are discussed.This research was supported by NSF and AFOSR grant DDM-9115768     

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

An exact algorithm for the network pricing problem

This work focuses on an improved exact algorithm for addressing an NP-hard network pricing problem. The method involves an efficient and partial generation of candidate solutions, a recursive scheme for generating improved upper bounds, and a column generation procedure for solving the network-structured subproblems. Its efficiency is assessed against both randomly generated instances involving three distinct topologies as well as instances based on real life situations in telecommunication and freight transportation.     

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 prototype column generation strategy for the multiple container loading problem

The multiple container loading cost minimization problem (MCLCMP) is a practical and useful problem in the transportation industry, where products of various dimensions are to be loaded into containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally formulated as a set cover problem and solved using column generation techniques, which is a popular method for handling huge numbers of variables. However, the direct application of column generation is not effective because feasible solutions to the pricing subproblem is required, which for the MCLCMP is NP-hard. We show that efficiency can be greatly improved by generating prototypes that approximate feasible solutions to the pricing problem rather than actual columns. For many hard combinatorial problems, the subproblem in column generation based algorithms is NP-hard; if suitable prototypes can be quickly generated that approximate feasible solutions, then our strategy can also be applied to speed up these algorithms.     

A matrix generation approach for eigenvalue optimization

We study the extension of a column generation technique to nonpolyhedral models. In particular, we study the problem of minimizing the maximum eigenvalue of an affine combination of symmetric matrices. At each step of the algorithm a restricted master problem in the primal space, corresponding to the relaxed dual (original) problem, is formed. A query point is obtained as an approximate analytic center of a bounded set that contains the optimal solution of the dual problem. The original objective function is evaluated at the query point, and depending on its differentiability a column or a matrix is added to the restricted master problem. We discuss the issues of recovering feasibility after the restricted master problem is updated by a column or a matrix. The computational experience of implementing the algorithm on randomly generated problems are reported and the cpu time of the matrix generation algorithm is compared with that of the primal-dual interior point methods on dense and sparse problems using the software SDPT3. Our numerical results illustrate that the matrix generation algorithm outperforms primal-dual interior point methods on dense problems with no structure and also on a class of sparse problems. This work has been completed with the partial support of a summer grant from the College of Business Administration, California State University San Marcos, and the University Professional Development/Research and Creative Activity Grant     

A column generation approach for solving the patient admission scheduling problem

This paper addresses the Patient Admission Scheduling (PAS) problem. The PAS problem entails assigning elective patients to beds, while satisfying a number of hard constraints and as many soft constraints as is possible, and arises at all planning levels for hospital management. There exist a few, different variants of this problem. In this paper we consider one such variant and propose an optimization-based heuristic building on branch-and-bound, column generation, and dynamic constraint aggregation to solve it. We achieve tighter lower bounds than previously reported in the literature and, in addition, we are able to produce new best known solutions for five out of twelve instances from a publicly available repository.     

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 column generation approach for determining optimal fleet mix,schedules, and transshipment facility locations for a vessel transportation problem

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

A column generation approach to train timetabling on a corridor

We propose heuristic and exact algorithms for the (periodic and non-periodic) train timetabling problem on a corridor that are based on the solution of the LP relaxation of an ILP formulation in which each variable corresponds to a full timetable for a train. This is in contrast with previous approaches to the same problem, which were based on ILP formulations in which each variable is associated with a departure and/or arrival of a train at a specific station in a specific time instant, whose LP relaxation is too expensive to be solved exactly. Experimental results on real-world instances of the problem show that the proposed approach is capable of producing heuristic solutions of better quality than those obtained by these previous approaches, and of solving some small-size instances to proven optimality.      

A facet generation and relaxation technique applied to an assignment problem with side constraints

We consider a solution method for combinatorial optimization problems based on a combination of Lagrangean relaxation and constraint generation techniques. The procedure is applied to a constrained assignment problem, where subsets of variables are specified, and variables belonging to the same subset must have the same value. The model can be applied to solve constrained job assignment or classroom assignment problems. The procedure we suggest requires only the solution of classical assignment subproblems. An illustrative numerical example is given.     

Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria

In some hospitals, an “open scheduling” strategy is applied to solve the operating room planning problem; i.e., surgeons can choose any workday for his surgical cases, and the staffing of anesthetists and nurses is adjusted to maximize the efficiency of operating room utilization. In this paper, we aim at obtaining an efficient operating program for an operating theatre with several multifunctional operating rooms by using this “open scheduling” strategy. First, a mathematical model is constructed to assign surgical cases to operating rooms within one week. This model complies with the availability of operating rooms and surgeons, and its objective is not only to maximize utilization of operating rooms, but to minimize their overtime cost. Then a column-generation-based heuristic (CGBH) procedure is proposed, where four different criteria are compared with each other so as to find a solution with the best performance. In addition, the best approximate solution, obtained by this CGBH procedure after running all the criteria proposed, is compared with the lower bound obtained by an explicit column generation (CG) procedure, LP, to evaluate the distance between the approximate solution obtained and the optimum one. Although no criterion, according to the experimental results, is found superior to all other three in both robustness and quality of the solution obtained, it is found that the best solution obtained among those four criteria is often very close to LP, which means that the proposed algorithm can obtain a near optimal solution. In one word, the CGBH procedure proposed in this paper can obtain an efficient assignment of the surgical cases if the other resources (anesthesia and nursing staff, equipment, beds in the recovery room and etc.) are well organized.     

A MIP-based approach to solve the prize-collecting local access network design problem

This paper presents a new combinatorial optimization problem that can be used to model the deployment of broadband telecommunications systems in which optical fiber cables are installed between a central office and a number of end-customers. In this capacitated network design problem the installation of optical fiber cables with sufficient capacity is required to carry the traffic from the central office to the end-customers at minimum cost. In the situation motivating this research the network does not necessarily need to connect all customers (or at least not with the best available technology). Instead, some nodes are potential customers. The aim is to select the customers to be connected to the central server and to choose the cable capacities to establish these connections. The telecom company takes the strategic decision of fixing a percentage of customers that should be served, and aims for minimizing the total cost of the network providing this minimum service. For that reason the underlying problem is called the Prize-Collecting Local Access Network Design problem (PC-LAN).     

Cutting planes and column generation techniques with the projective algorithm

The problem studied is that of solving linear programs defined recursively by column generation techniques or cutting plane techniques using, respectively, the primal projective method or the dual projective method.This research has been supported in part by FCAR of Quebec, Grant Nos. CE-130 and EQ-3078, by NSERC of Canada, Grant No. A4152, and by the Fonds National Suisse de la Recherche Scientifique, Grant No. 1.467.0.86.     

A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes

The Pickup and Delivery Problem with Shuttle routes (PDPS) is a special case of the Pickup and Delivery Problem with Time Windows (PDPTW) where the trips between the pickup points and the delivery points can be decomposed into two legs. The first leg visits only pickup points and ends at some delivery point. The second leg is a direct trip – called a shuttle – between two delivery points. This optimization problem has practical applications in the transportation of people between a large set of pickup points and a restricted set of delivery points.     

Survivable network design with shared-protection routing

In this paper we study the problem of designing a survivable telecommunication network with shared-protection routing. We develop a heuristic algorithm to solve this problem. Recent results in the area of global re-routing have been used to obtain very tight lower bounds for the problem. Our results indicate that in a majority of problem instances, the average gap between the heuristic solutions and the lower bounds is within 5%. Computational experience is reported on randomly generated problem instances with up to 35 nodes, 80 edges and 595 demand pairs and also on the instances available in SNDlib database.