A solution approach for log truck scheduling based on composite pricing and branch and bound

The logging truck scheduling problem is one of the most complex routing problems where both pick‐up and delivery operations are included. It consists in finding one feasible route for each vehicle in order to satisfy the demands of the customers and in such a way that the total transport cost is minimized. We use a mathematical formulation of the log truck scheduling problem where each column represents a feasible route. We generate a large pool of columns based on solving a transportation problem. Then we apply a composite pricing algorithm, which mainly consists of pricing the pool of columns and maintain an active set of these, for solving the LP relaxed model. A branch and price approach is used to obtain integer solutions in which we apply composite pricing to generate new columns. Numerical results from case studies at Swedish forestry companies are presented.     

A column generation heuristic for a dynamic generalized assignment problem

This paper studies the dynamic generalized assignment problem (DGAP) which extends the well-known generalized assignment problem by considering a discretized time horizon and by associating a starting time and a finishing time with each task. Additional constraints related to warehouse and yard management applications are also considered. Three linear integer programming formulations of the problem are introduced. The strongest one models the problem as an origin–destination integer multi-commodity flow problem with side constraints. This model can be solved quickly for instances of small to moderate size. However, because of its computer memory requirements, it becomes impractical for larger instances. Hence, a column generation algorithm is used to compute lower bounds by solving the linear program (LP) relaxation of the problem. This column generation algorithm is also embedded in a heuristic aimed at finding feasible integer solutions. Computational experiments on large-scale instances show the effectiveness of the proposed approach.     

An LP-based heuristic algorithm for the node capacitated in-tree packing problem

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard.We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem.We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods.     

A constraint programming based column generation approach to nurse rostering problems

This paper presents our investigations on a hybrid constraint programming based column generation (CP–CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world constraints in several benchmark nurse rostering problems. The hybrid CP–CG approach is featured with not only the effective relaxation and optimality reasoning of linear programming but also the powerful expressiveness of constraint programming in modeling the complex logical constraints in nurse rostering problems. In solving the CP pricing subproblem, we propose two strategies to generate promising columns which contribute to the efficiency of the CG procedure. A Depth Bounded Discrepancy Search is employed to obtain diverse columns. A cost threshold is adaptively tightened based on the information collected during the search to generate columns of good quality. Computational experiments on a set of benchmark nurse rostering problems demonstrate a faster convergence by the two strategies and justify the effectiveness and efficiency of the hybrid CP–CG approach.     

Hybrid column generation for large-size Covering Integer Programs: Application to transportation planning

The well-known column generation scheme is often an efficient approach for solving the linear relaxation of large-size Covering Integer Programs (CIP). In this paper, this technique is hybridized with an extension of the best-known CIP approximation heuristic, taking advantage of distinct criteria of columns selection. This extension uses fractional optimization for solving pricing subproblems. Numerical results on a real-case transportation planning problem show that the hybrid scheme accelerates the convergence of column generation both in terms of number of iterations and computational time. The integer solutions generated at the end of the process can also be improved for a significant proportion of instances, highlighting the potential of diversification of the approximation heuristic.     

A column generation approach to the heterogeneous fleet vehicle routing problem

We consider a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. An approach based on column generation (CG) is applied for its solution, hitherto successful only in the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the CG technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to obtain an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in terms of the quality of solutions generated and the solution time.     

An improved stepsize of the subgradient algorithm for solving the lagrangian relaxation problem

The Lagrangian relaxation approach has been successfully applied to many large-scale mathematical programming problems. The Lagrangian relaxation problem itself is a non-differentiable optimization problem. One of the methods for solving such problem is the subgradient algorithm. In this paper, we propose an improved stepsize of the subgradient algorithm for solving the Lagrangian relaxation problem. Our version of the algorithm may significantly improve the rate of convergence of subgradient algorithm when applied to the solution of Lagrangian relaxation problem. An illustrative numerical example is also given.     

A computational comparison of gomory and knapsack cuts

A common method of solving integer programs is to solve the problem first as a linear program (LP) then add constraints that cut off noninteger solutions from the set of LP feasible solutions. As soon as an optimal LP solution is all integer, then it is an optimal solution to the integer program. The method of Gomory can generate a variety of different cuts but there is a dearth of reports on systematic testing of the effectiveness of different cuts. We report extensive computational comparisons between a number of different cuts, including a successful one not previously publicised. It has been known for some time that Gomory cuts can be unsuccessful because of slow convergence with the accompanying difficulties of computer round-off error. Recently a method has been proposed for generating, for 0–1 integer problems, cuts that are usually tighter than Gomory cuts and thus give faster convergence. This method of knapsack cuts is tested in comparison with Gomory cuts for moderate size problems and is found to be superior for 0–1 problems having dense constraint matrices but only slightly better than Gomory cuts for problems with sparse matrices. On the other hand, knapsack cuts applied to general integer problems reformulated as 0–1 are found to be less successful than Gomory cuts applied to the original integer problem.     

并行机实时调度问题的LR&CG算法

研究了目标函数为最小化总加权完成时间的并行机实时调度问题.建立该问题混合整数规划模型,并提出融合拉格朗日松弛(LR)和列生成(CG)的 LR & CG 混合算法.该算法包含双重迭代,在内环以次梯度法作为下界求解器和列生成器,在外环通过求解限制主问题来获得影子价格以调节拉格朗日乘子.计算实验结果表明,在相同的计算时间内, LR & CG 能够比常规的 LR 算法获得更好的上界和下界,表明了前者具有更好的收敛性能.     

The train driver recovery problem—A set partitioning based model and solution method

The need to recover a train driver schedule occurs during major disruptions in the daily railway operations. Based on data from the Danish passenger railway operator DSB S-tog A/S, a solution method to the train driver recovery problem (TDRP) is developed. The TDRP is formulated as a set partitioning problem. We define a disruption neighbourhood by identifying a small set of drivers and train tasks directly affected by the disruption. Based on the disruption neighbourhood, the TDRP model is formed and solved. If the TDRP solution provides a feasible recovery for the drivers within the disruption neighbourhood, we consider that the problem is solved. However, if a feasible solution is not found, the disruption neighbourhood is expanded by adding further drivers or increasing the recovery time period. Fractional solutions to the LP relaxation of the TDRP are resolved with a constraint branching strategy using the depth-first search of the Branch & Bound tree. The LP relaxation of the TDRP possesses strong integer properties. We present test scenarios generated from the historical real-life operations data of DSB S-tog A/S. The numerical results show that all but one tested instances produce integer solutions to the LP relaxation of the TDRP and solutions are found within a few seconds.     

A Branch and Bound Algorithm for An Uncapacitated Facility Location Problem with a Side Constraint

In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p-median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p -median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump-backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported.     

An improved hybrid algorithm for the set covering problem

The state-of-the-art ant colony optimization (ACO) algorithm to solve large scale set covering problems (SCP) starts by solving the Lagrangian dual (LD) problem of the SCP to obtain quasi-optimal dual values. These values are then exploited by the ACO algorithm in the form of heuristic estimates. This article starts by discussing the complexity of this approach where a number of new parameters are introduced to escape local optimums and normalize the heuristic values. To avoid these complexities, we propose a new hybrid algorithm that starts by solving the linear programming (LP) relaxation of the SCP. This solution is used to eliminate unnecessary columns, and to estimate the heuristic information. To generate solutions, we use a Max–Min Ant System (MMAS) algorithm that employs a novel mechanism to update the pheromone trail limits to maintain a predetermined exploration rate. Computational experiments on different sets of benchmark instances prove that our proposed algorithm can be considered the new state-of-the-art meta-heuristic to solve the SCP.     

A new formulation and approach for the black and white traveling salesman problem

This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.     

启发式列生成算法求解带恶化效应的同构并行机调度问题

针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解.HCGA与商用求解器GUROBI的对比实验结果表明,HCGA可在较短时间内获得更优的解.     

In situ column generation for a cutting-stock problem

Working with an integer bilinear programming formulation of a one-dimensional cutting-stock problem, we develop an ILP-based local-search heuristic. The ILPs holistically integrate the master and subproblem of the usual price driven pattern-generation paradigm, resulting in a unified model that generates new patterns in situ. We work harder to generate new columns, but we are guaranteed that new columns give us an integer linear-programming improvement (rather then the continuous linear-programming improvement sought by the usual price driven column generation). The method is well suited to practical restrictions such as when a limited number of cutting patterns should be employed, and our goal is to generate a profile of solutions trading off trim loss against the number of patterns utilized. We describe our implementation and results of computational experiments on instances from a chemical-fiber company.     

Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound

We propose exact hybrid methods based on integer linear programming (ILP) and constraint programming (CP) for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a CP formulation associated with an LP relaxation. Under a CP framework, the LP relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two different LP relaxations. The first formulation is based on a direct representation of the problem. The second formulation is based on a decomposition in intervals of the possible operation starting times. We show the theoretical interest of the decomposition-based representation compared to the direct representation through the analysis of dominant schedules. Computational experiments on a set of randomly generated instances confirm the superiority of the decomposition-based representation. In both cases, the hybrid methods outperform pure CP for employee cost minimization while it is not the case for makespan minimization. The experiments also investigate the interest of the proposed integrated method compared to a sequential approach and show its potential for multiobjective optimization.     

Tight Relaxation of Quadratic Matching

Establishing point correspondences between shapes is extremely challenging as it involves both finding sets of semantically persistent feature points, as well as their combinatorial matching. We focus on the latter and consider the Quadratic Assignment Matching (QAM) model. We suggest a novel convex relaxation for this NP‐hard problem that builds upon a rank‐one reformulation of the problem in a higher dimension, followed by relaxation into a semidefinite program (SDP). Our method is shown to be a certain hybrid of the popular spectral and doubly‐stochastic relaxations of QAM and in particular we prove that it is tighter than both. Experimental evaluation shows that the proposed relaxation is extremely tight: in the majority of our experiments it achieved the certified global optimum solution for the problem, while other relaxations tend to produce sub‐optimal solutions. This, however, comes at the price of solving an SDP in a higher dimension. Our approach is further generalized to the problem of Consistent Collection Matching (CCM), where we solve the QAM on a collection of shapes while simultaneously incorporating a global consistency constraint. Lastly, we demonstrate an application to metric learning of collections of shapes.     

An aggregation heuristic for large scale p-median problem

The p-median problem (PMP) consists of locating p facilities (medians) in order to minimize the sum of distances from each client to the nearest facility. The interest in the large-scale PMP arises from applications in cluster analysis, where a set of patterns has to be partitioned into subsets (clusters) on the base of similarity.In this paper we introduce a new heuristic for large-scale PMP instances, based on Lagrangean relaxation. It consists of three main components: subgradient column generation, combining subgradient optimization with column generation; a “core” heuristic, which computes an upper bound by solving a reduced problem defined by a subset of the original variables chosen on a base of Lagrangean reduced costs; and an aggregation procedure that defines reduced size instances by aggregating together clients with the facilities. Computational results show that the proposed heuristic is able to compute good quality lower and upper bounds for instances up to 90,000 clients and potential facilities.     

Row and column generation technique for a multistage cutting stock problem

The multistage cutting stock problem (CSP) generalizes the one-dimensional CSP when a lengthwise cutting process is distributed over two or more successive stages. At every stage of the cutting process incoming rolls are slit into smaller rolls by width. The problem is to minimize total trim loss occurring at all stages of technological process meeting customer demands for finished rolls. We propose a row and column generation technique for solving the multistage one-dimensional CSP. The technique is a generalization of the column generation method suggested by Gilmore and Gomory for solving a classic CSP. The procedure generates only those intermediate rolls (rows) and cutting patterns (columns) that are needed. An auxiliary problem embedded into the frame of the revised simplex algorithm is a non-linear knapsack problem that can be solved efficiently. Computational results prove the overall method is a valuable addition to the tool set for modeling and solving the multistage CSP.Scope and purposeWe investigate a broad class of large-scale linear programming models and suggest a new and efficient way to solve them. The proposed method belongs to a category of decomposition techniques generalizing the famous column generation method. An iteration of the revised simplex algorithm may “enrich” the LP matrix either by generating a new column, as a purely column generation method does, or by generating a combination of a new row and a pair of new columns. The method is a row and column generation technique that we propose and investigate. Applications modeled by a multistage CSP occur in the industries that use a multistage cutting process: paper, leather, film, steel, etc., or a nested packing/loading process: transportation. The unknown variables in the multistage cutting stock problem are intermediate sizes (rows) and cutting patterns (columns). According to the algorithm both are to be generated dynamically. The proposed algorithm brings tremendous benefits in terms of the quality of solutions and computational performance.     

实时无等待HFS调度的一种拉格朗日松弛算法

研究了实时无等待HFS调度问题，并建立一个整数规划模型，提出运用拉格朗日松弛算法来求解，在此算法中，常采用次梯度方法更新拉格朗日乘子，但它随着迭代数的增加收敛速度会减慢，因此设计了一个改进的bundle方法。将以前的次梯度累积到bundle中，以获得一个更好的乘子更新方向．仿真实验表明，与次梯度方法相比，所设计的bundle法不仅在较少的迭代数内得到了更快的收敛速度而且改进了优化性能，对于大规模问题效果更为显著。