An arc flow-based optimization approach for the two-stage guillotine strip cutting problem

Despite its broad range of industrial applications, the two-stage guillotine restriction has received very scant attention in the strip cutting literature. An integer linear programming model that is based on a special graph structure is devised for this strongly NP-hard problem. In addition to being easy to implement, the empirical study on a large set of instances from the literature and from real industrial world cases shows the efficiency of the proposed method while solving instances with high multiplicity factor.     

A branch-and-price algorithm for the two-stage guillotine cutting stock problem

We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly arises in the industry when small rectangular items need to be cut out of large stock sheets. We propose an integer programming formulation that extends the well-known Gilmore and Gomory model by explicitly considering solutions that are obtained by both slitting some stock sheets down their widths and others down their heights. To solve this model, we propose an exact branch-and-price algorithm. To the best of our knowledge, this is the first contribution with regard to obtaining integer optimal solutions to Gilmore and Gomory model. Extensive results, on a set of real-world problems, indicate that the proposed algorithm delivers optimal solutions for instances with up to 809 items and that the hybrid cutting strategy often yields improved solutions. Furthermore, our computational study reveals that the proposed modelling and algorithmic strategy outperforms a recently proposed arc-flow model-based solution strategy.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

Minimizing weighted earliness–tardiness on a single machine with a common due date using quadratic models

In this paper we study the problem of minimizing weighted earliness and tardiness on a single machine when all the jobs share the same due date. We propose two quadratic integer programming models for solving both cases of unrestricted and restricted due dates, an auxiliary model based on unconstrained quadratic integer programming and an algorithmic scheme for solving each instance, according to its size and characteristics, in the most efficient way. The scheme is tested on a set of well-known test problems. By combining the solutions of the three models we prove the optimality of the solutions obtained for most of the problems. For large instances, although optimality cannot be proved, we actually obtain optimal solutions for all the tested instances.     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

An effective and fast heuristic for the Dial-a-Ride problem

Dial-a-Ride is an emerging transport system, in which a fleet of vehicles, without fixed routes and schedules, carries people from the desired pickup point to the desired delivery point, during a pre-specified time interval. It can be modeled as an -hard routing and scheduling problem, with a suitable mixed integer programming formulation. Exact approaches to this problem are too limited to tackle real-life instances (hundred of trips), therefore heuristics are needed. The heuristic method proposed in this paper builds an auxiliary graph and then solves an assignment problem on this graph. The auxiliary graph is obtained by replacing pairs of nodes with a single one and associating an ad hoc cost function to the new set of arcs. Two different simple methods are employed to transform the infeasible solution given by the assignment problem into a feasible one. The proposed algorithms have been tested on instances created using the Milan network and shown to be fast and effective.      

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

Rules-based heuristic approach for the U-shaped assembly line balancing problem

The type-2 U-shaped assembly line balancing problem is important for many just-in-time manufactures, but an efficient algorithm is not available at present. Thus, in this study, a novel heuristic approach based on multiple rules and an integer programming model is proposed to address this problem. In the proposed approach, three rules are systematically grouped together, i.e., task selection, task assignment, and task exchange rules. The sufficient conditions for implementing the exchange rules are proposed and proved. Thirteen small or medium scale benchmark issues comprising 63 instances were solved, where the computational results demonstrate the efficiency and effectiveness of the proposed method compared with integer programming. The computational results obtained for 18 examples comprising 121 instances demonstrate that the task exchange rules significantly improve the computational accuracy compared with the traditional heuristic. Finally, 30 new standard instances produced by a systematic data generation process were also solved effectively by the proposed approach. The proposed heuristic approach with multiple rules can provide a theoretical basis for other local search algorithms, especially for addressing issues such as the U-Shaped assembly line balancing problem.     

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.     

Designing routes for WEEE collection: the vehicle routing problem with split loads and date windows

This paper presents an integer programming model and describes a GRASP based algorithm to solve a vehicle routing and scheduling problem for the collection of Waste of Electric and Electronic Equipment (WEEE). The difficulty of this problem arises from the fact that it is characterized by four variants of the vehicle routing problem that have been studied independently in the literature, but not together. The experimental analysis on a large set of randomly-generated instances shows the good performance of the proposed algorithm. Moreover, computational results using real data show that the method outperforms real existing approaches to reverse logistics.     

Revised multi-choice goal programming for multi-period,multi-stage inventory controlled supply chain model with popup stores in Guerrilla marketing

In this paper, we consider a supply chain network design problem with popup stores which can be opened for a few weeks or months before closing seasonally in a marketplace. The proposed model is multi-period and multi-stage with multi-choice goals under inventory management constraints and formulated by 0–1 mixed integer linear programming. The design tasks of the problem involve the choice of the popup stores to be opened and the distribution network design to satisfy the demand with three multi-choice goals. The first goal is minimization of the sum of transportation costs in all stages; the second is to minimization of set up costs of popup stores; and the third goal is minimization of inventory holding and backordering costs. Revised multi-choice goal programming approach is applied to solve this mixed integer linear programming model. Also, we provide a real-world industrial case to demonstrate how the proposed model works.     

A note on second-order stochastic dominance constraints induced by mixed-integer linear recourse

We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured, mixed- integer linear programming equivalents to the dominance constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instances from power optimization.     

Boosting the feasibility pump

The feasibility pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between LP feasible but fractional solutions, and integer but LP infeasible solutions. The process attempts to minimize the distance between consecutive iterates, producing an integer feasible solution when closing the distance between them. We investigate the benefits of enhancing the rounding procedure with a clever integer line search that efficiently explores a large set of integer points. An extensive computational study on benchmark instances demonstrates the efficacy of the proposed approach.     

A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks

The Minimum Power Multicast Problem arises in wireless sensor networks and consists in assigning a transmission power to each node of a network in such a way that the total power consumption over the network is minimized, while a source node is connected to a set of destination nodes, toward which a message has to be sent periodically. A new mixed integer programming model for the problem, based on paths, is presented. A practical exact algorithm based on column generation and branch and price is derived from this model. A comparison with state-of-the-art exact methods is presented, and it is shown that the new approach compares favorably to other algorithms when the number of destination nodes is moderate. Under this condition, the proposed method is able to solve previously unmanageable instances.     

Minimising total average cycle stock subject to practical constraints

Silver and Moon (J Opl Res Soc 50(8) (1999) 789–796) address the problem of minimising total average cycle stock subject to two practical constraints. They provide a dynamic programming formulation for obtaining an optimal solution and propose a simple and efficient heuristic algorithm. Hsieh (J Opl Res Soc 52(4) (2001) 463–470) proposes a 0–1 linear programming approach to the problem and a simple heuristic based on the relaxed 0–1 programming formulation. We show in this paper that the formulation of Hsieh can be improved for solving very large size instances of this inventory problem. So the mathematical approach is interesting for several reasons: the definition of the model is simple, its implementation is immediate by using a mathematical programming language together with a mixed integer programming software and the performance of the approach is excellent. Computational experiments carried out on the set of realistic examples considered in the above references are reported. We also show that the general framework for modelling given by mixed integer programming allows the initial model to be extended in several interesting directions.     

Mixed integer quadratically-constrained programming model to solve the irregular strip packing problem with continuous rotations

The irregular strip packing problem consists of cutting a set of convex and non-convex two-dimensional polygonal pieces from a board with a fixed height and infinite length. Owing to the importance of this problem, a large number of mathematical models and solution methods have been proposed. However, only few papers consider that the pieces can be rotated at any angle in order to reduce the board length used. Furthermore, the solution methods proposed in the literature are mostly heuristic. This paper proposes a novel mixed integer quadratically-constrained programming model for the irregular strip packing problem considering continuous rotations for the pieces. In the model, the pieces are allocated on the board using a reference point and its allocation is given by the translation and rotation of the pieces. To reduce the number of symmetric solutions for the model, sets of symmetry-breaking constraints are proposed. Computational experiments were performed on the model with and without symmetry-breaking constraints, showing that symmetry elimination improves the quality of solutions found by the solution methods. Tests were performed with instances from the literature. For two instances, it was possible to compare the solutions with a previous model from the literature and show that the proposed model is able to obtain numerically accurate solutions in competitive computational times.     

The single-assignment hub covering problem: Models and linearizations

We study the hub covering problem which, so far, has remained one of the unstudied hub location problems in the literature. We give a combinatorial and a new integer programming formulation of the hub covering problem that is different from earlier integer programming formulations. Both new and old formulations are nonlinear binary integer programs. We give three linearizations for the old model and one linearization for the new one and test their computational performances based on 80 instances of the CAB data set. Computational results indicate that the linear version of the new model performs significantly better than the most successful linearization of the old model both in terms of average and maximum CPU times as well as in core storage requirements.     

A single machine scheduling problem with availability constraints and sequence-dependent setup costs

We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic.     

A combined local search and integer programming approach to the traveling tournament problem

The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.