A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) is a well-known NP-hard combinatorial optimization problem with a number of important applications. In this paper, we present a “reduce and solve” heuristic approach which combines problem reduction techniques with an Integer Linear Programming (ILP) solver (CPLEX). The key ingredient of the proposed approach is a set of group fixing and variable fixing rules. These fixing rules rely mainly on information from the linear relaxation of the given problem and aim to generate reduced critical subproblem to be solved by the ILP solver. Additional strategies are used to explore the space of the reduced problems. Extensive experimental studies over two sets of 37 MMKP benchmark instances in the literature show that our approach competes favorably with the most recent state-of-the-art algorithms. In particular, for the set of 27 conventional benchmarks, the proposed approach finds an improved best lower bound for 11 instances and as a by-product improves all the previous best upper bounds. For the 10 additional instances with irregular structures, the method improves 7 best known results.     

Effective search space control for large and/or complex driver scheduling problems

For real life bus and train driver scheduling instances, the number of columns in terms of the set covering/partitioning ILP model could run into billions making the problem very difficult. Column generation approaches have the drawback that the sub-problems for generating the columns would be computationally expensive in such situations. This paper proposes a hybrid solution method, called PowerSolver, of using an iterative heuristic to derive a series of small refined sub-problem instances fed into an existing efficient set covering ILP based solver. In each iteration, the minimum set of relief opportunities that guarantees a solution no worse than the current best is retained. Controlled by a user-defined strategy, a small number of the banned relief opportunities would be reactivated and some soft constraints may be relaxed before the new sub-problem instance is solved. PowerSolver is proving successful by many transport operators who are now routinely using it. Test results from some large scale real-life exercises will be reported.     

The balanced academic curriculum problem revisited

The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its formulation is simpler than the problem solved in practice by universities. In this article, we introduce a generalized version of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem instances arisen at University of Udine. Since the existing formulation based on a min–max objective function does not balance effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented, and analyzed heuristics based on local search. We have collected computational results on all the new instances with the proposed approaches and assessed the quality of solutions with respect to the lower bounds found by ILP on a relaxed and decomposed problem. Results show that a selected heuristic finds solutions of quality at 9%–60% distance from the lower bound. We make all data publicly available, in order to stimulate further research on this problem.     

Solving the CLSP by a Tabu Search Heuristic

The multi-item, single-level, capacitated, dynamic lot-sizing problem, commonly abbreviated as CLSP, is considered. The problem is cast in a tight mixed-integer programming model (MIP); tight in the sense that the gap between the optimal value of MIP and that of its linear programming relaxation (LP) is small. The LP relaxation of MIP is then solved by column generation. The resulting feasible solution is further improved by adopting the corresponding set-up schedule and re-optimizing variable costs by solving a minimum-cost network flow (trans-shipment) problem. Subsequently, the improved solution is used as a starting solution for a tabu search procedure, with the worth of moves assessed using the same trans-shipment problem. Results of computational testing of benchmark problem instances are presented. They show that the heuristic solutions obtained are effective, in that they are extremely close to the best known solutions. The computational efficiency makes it possible to solve realistically large problem instances routinely on a personal computer; in particular, the solution procedure is most effective, in terms of solution quality, for larger problem instances.     

An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem

In this paper we present two major approaches to solve the car sequencing problem, in which the goal is to find an optimal arrangement of commissioned vehicles along a production line with respect to constraints of the form “no more than l_ccars are allowed to require a component c in any subsequence of m_cconsecutive cars”. The first method is an exact one based on integer linear programming (ILP). The second approach is hybrid: it uses ILP techniques within a general variable neighborhood search (VNS) framework for examining large neighborhoods. We tested the two methods on benchmark instances provided by CSP_LIB and the automobile manufacturer RENAULT for the ROADEF Challenge 2005. These tests reveal that our approaches are competitive to previous reported algorithms. For the CSP_LIB instances we were able to shorten the required computation time for reaching and proving optimality. Furthermore, we were able to obtain tight bounds on some of the ROADEF instances. For two of these instances the proposed ILP-method could provide new optimality proofs for already known solutions. For the VNS, the individual contributions of the used neighborhoods are also experimentally analyzed. Results highlight the significant impact of each structure. In particular the large ones examined using ILP techniques enhance the overall performance significantly, so that the hybrid approach clearly outperforms variants including only commonly defined neighborhoods.     

Freight transportation in railway networks with automated terminals: A mathematical model and MIP heuristic approaches

In this paper we propose a planning procedure for serving freight transportation requests in a railway network with fast transfer equipment at terminals. We consider a transportation system where different customers make their requests (orders) for moving boxes, i.e., either containers or swap bodies, between different origins and destinations, with specific requirements on delivery times. The decisions to be taken concern the route (and the corresponding sequence of trains) that each box follows in the network and the assignment of boxes to train wagons, taking into account that boxes can change more than one train and that train timetables are fixed.The planning procedure includes a pre-analysis step to determine all the possible sequences of trains for serving each order, followed by the solution of a 0-1 linear programming problem to find the optimal assignment of each box to a train sequence and to a specific wagon for each train in the sequence. This latter is a generalized assignment problem which is NP-hard. Hence, in order to find good solutions in acceptable computation times, two MIP heuristic approaches are proposed and tested through an experimental analysis considering realistic problem instances.     

Variable neighbourhood search for bandwidth reduction

The problem of reducing the bandwidth of a matrix consists of finding a permutation of rows and columns of a given matrix which keeps the non-zero elements in a band as close as possible to the main diagonal. This NP-complete problem can also be formulated as a vertex labelling problem on a graph, where each edge represents a non-zero element of the matrix. We propose a variable neighbourhood search based heuristic for reducing the bandwidth of a matrix which successfully combines several recent ideas from the literature. Empirical results for an often used collection of 113 benchmark instances indicate that the proposed heuristic compares favourably to all previous methods. Moreover, with our approach, we improve best solutions in 50% of instances of large benchmark tests.     

Linear programming relaxations and marginal productivity index policies for the buffer sharing problem

We study the dynamic admission control for a finite shared buffer with support of multiclass traffic under Markovian assumptions. The problem is often referred to as buffer sharing in the literature. From the linear programming (LP) formulation of the continuous-time Markov decision process (MDP), we construct a hierarchy of increasingly stronger LP relaxations where the hierarchy levels equal the number of job classes. Each relaxation in the hierarchy is obtained by projecting the original achievable performance region onto a polytope of simpler structure. We propose a heuristic policy for admission control, which is based on the theory of Marginal Productivity Index (MPI) and the Lagrangian decomposition of the first order LP relaxation. The dual of the relaxed buffer space constraint in the first order LP relaxation is used as a proxy to the cost of buffer space. Given that each of the decomposed queueing admission control problems satisfies the indexability condition, the proposed heuristic accepts a new arrival if there is enough buffer space left and the MPI of the current job class is greater than the incurred cost of buffer usage. Our numerical examples for the cases of two and eight job classes show the near-optimal performance of the proposed MPI heuristic.     

Auxiliary tool allocation in flexible manufacturing systems

This paper analyses a new approach to the machine loading problem arising in flexible manufacturing systems (FMSs). This approach allows the operations to be assigned to machines assuming that machines have access to all the tools required for their operations. This exploits the flexibility of the FMS completely. Next an allocation of tools to machines is determined which satisfies the tool requirements for each machine and minimizes the total number of tools. Thus this approach minimizes the unnecessary tool duplications in the system and maximizes the tool utilization. The problem is modeled as an integer linear program (ILP). We notice that the main problem has a block diagonal structure which is decomposable by relaxing a set of linking constraints. Each separated sub-problem represents a problem of allocation of a single type of tools. We develop a branch-and-bound based exact solution procedure and three heuristic procedures to solve the sub-problems. Our lower bounding approach uses Lanrangean relaxation. The solutions to the Lagrangean relaxation are further used to determine the branching sequences and to develop heuristic approaches. Since finding even a feasible solution to the main problem is NP-hard, we develop only enumerative procedures to solve the main problem. Finally, these solution procedures are tested on randomly generated test problems.     

Lower bounds for the ITC-2007 curriculum-based course timetabling problem

This paper describes an approach for generating lower bounds for the curriculum-based course timetabling problem, which was presented at the International Timetabling Competition (ITC-2007, Track 3). So far, several methods based on integer linear programming have been proposed for computing lower bounds of this minimization problem. We present a new partition-based approach that is based on the “divide and conquer” principle. The proposed approach uses iterative tabu search to partition the initial problem into sub-problems which are solved with an ILP solver. Computational outcomes show that this approach is able to improve on the current best lower bounds for 12 out of the 21 benchmark instances, and to prove optimality for 6 of them. These new lower bounds are useful to estimate the quality of the upper bounds obtained with various heuristic approaches.     

An algorithm and upper bounds for the weighted maximal planar graph problem

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.     

Lagrangian relaxation guided problem space search heuristics for generalized assignment problems

We develop and test a heuristic based on Lagrangian relaxation and problem space search to solve the generalized assignment problem (GAP). The heuristic combines the iterative search capability of subgradient optimization used to solve the Lagrangian relaxation of the GAP formulation and the perturbation scheme of problem space search to obtain high-quality solutions to the GAP. We test the heuristic using different upper bound generation routines developed within the overall mechanism. Using the existing problem data sets of various levels of difficulty and sizes, including the challenging largest instances, we observe that the heuristic with a specific version of the upper bound routine works well on most of the benchmark instances known and provides high-quality solutions quickly. An advantage of the approach is its generic nature, simplicity, and implementation flexibility.     

A Multi-Stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.     

Efficient solution of large scale,single-source,capacitated plant location problems

The single-source, capacitated plant location problem is considered. This problem differs from the capacitated plant location problem by the additional requirement that each customer must be supplied with all its demand from a single plant. An efficient heuristic solution, capable of solving large problem instances, is presented. The heuristic combines Lagrangian relaxation with restricted neighbourhood search. Computational experiments on two sets of problem instances are presented.     

An linear programming based lower bound for the simple assembly line balancing problem

The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem.     

An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times

This paper considers the capacitated multi-level lot-sizing problem with setup times, a class of difficult problems often faced in practical production planning settings. In the literature, relax-and-fix is a technique commonly applied to solve this problem due to the fact that setup decisions in later periods of the planning horizon are sensitive to setup decisions in the early periods but not vice versa. However, the weakness of this method is that setup decisions are optimized only on a small subset of periods in each iteration, and setup decisions fixed in early iterations might adversely affect setup decisions in later periods. In order to avoid these weaknesses, this paper proposes an extended relax-and-fix based heuristic that systematically uses domain knowledge derived from several strategies of relax-and-fix and a linear programming relaxation technique. Computational results show that the proposed heuristic is superior to other well-known approaches on solution qualities, in particular on hard test instances.     

Exact and heuristic methods for a full-load,multi-terminal,vehicle scheduling problem with backhauling and time windows

The problem considered is the full-load pickup and delivery problem with time windows (PDPTW), and heterogeneous products and vehicles, where the assignment of pickup points to requests is not predetermined. The problem is first formulated as a 0-1 LP, then a hybrid algorithm is developed, which chooses dynamically between a Greedy heuristic and one based on Regret costs. A multi-level constructive heuristic that consists of three post-optimizers is presented. Two lower bounds are used to evaluate the performance of the proposed heuristics when tested on random instances and selected data from a construction company.     

Partial Lagrangian relaxation for the unbalanced orthogonal Procrustes problem

Based on a novel reformulation of the feasible region, we propose and analyze a partial Lagrangian relaxation approach for the unbalanced orthogonal Procrustes problem (UOP). With a properly selected Lagrangian multiplier, the Lagrangian relaxation (LR) is equivalent to the recent matrix lifting semidefinite programming relaxation (MSDR), which has much more variables and constraints. Numerical results show that (LR) is solved more efficiently than (MSDR). Moreover, based on the special structure of (LR), we successfully employ the well-known Frank–Wolfe algorithm to efficiently solve very large instances of (LR). The rate of the convergence is shown to be independent of the row-dimension of the matrix variable of (UOP). Finally, motivated by (LR), we propose a Lagrangian heuristic for (UOP). Numerical results show that it can efficiently find the global optimal solutions of some randomly generated instances of (UOP).     

A Lagrangian relaxation-based heuristic for the vehicle routing with full container load

We address a problem of vehicle routing that arises in picking up and delivering full container load from/to an intermodal terminal. The substantial cost and time savings are expected by efficient linkage between pickup and delivery tasks, if the time of tasks and the suitability of containers for cargo allow. As this problem is NP-hard, we develop a subgradient heuristic based on a Lagrangian relaxation which enables us to identify a near optimal solution. The heuristic consists of two sub-problems: the classical assignment problem and the generalized assignment problem. As generalized assignment problem is also NP-hard, we employ an efficient solution procedure for a bin packing based problem, which replaces the generalized assignment problem. The heuristic procedure is tested on a wide variety of problem examples. The test results demonstrate that the procedure developed here can efficiently solve large instances of the problem.