An integer linear formulation for the file transfer scheduling problem

In this paper, we propose a new integer linear programming (ILP) formulation for solving a file transfer scheduling problem (FTSP), which is to minimize the overall time needed to transfer all files to their destinations for a given collection of various sized files in a computer network. Each computer in this network has a limited number of communication ports. The described problem is proved to be NP-hard in a general case. Our formulation enables solving the problem by standard ILP solvers like CPLEX or Gurobi. To prove the validity of the proposed ILP formulation, two new reformulations of FTSP are presented. The results obtained by CPLEX and Gurobi solvers, based on this formulation, are presented and discussed.     

A mixed integer linear programming formulation of the maximum betweenness problem

This paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time.     

Semi-Lagrangian relaxation applied to?the?uncapacitated facility location problem

We show how the performance of general purpose Mixed Integer Programming (MIP) solvers, can be enhanced by using the Semi-Lagrangian Relaxation (SLR) method. To illustrate this procedure we perform computational experiments on large-scale instances of the Uncapacitated Facility Location (UFL) problems with unknown optimal values. CPLEX solves 3 out of the 36 instances. By combining CPLEX with SLR, we manage to solve 18 out of the 36 instances and improve the best known lower bound for the other instances. The key point has been that, on average, the SLR approach, has reduced by more than 90% the total number of relevant UFL variables.     

A comparison of reduced and unreduced KKT systems arising from interior point methods

This paper addresses the solution of a cardinality Boolean quadratic programming problem using three different approaches. The first transforms the original problem into six mixed-integer linear programming (MILP) formulations. The second approach takes one of the MILP formulations and relies on the specific features of an MILP solver, namely using starting incumbents, polishing, and callbacks. The last involves the direct solution of the original problem by solvers that can accomodate the nonlinear combinatorial problem. Particular emphasis is placed on the definition of the MILP reformulations and their comparison with the other approaches. The results indicate that the data of the problem has a strong influence on the performance of the different approaches, and that there are clear-cut approaches that are better for some instances of the data. A detailed analysis of the results is made to identify the most effective approaches for specific instances of the data.     

A fast approximation algorithm for solving the complete set packing problem

We study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature.     

A hybrid algorithm for the unbounded knapsack problem

This paper presents a new approach for exactly solving the Unbounded Knapsack Problem (UKP) and proposes a new bound that was proved to dominate the previous bounds on a special class of UKP instances. Integrating bounds within the framework of sparse dynamic programming led to the creation of an efficient and robust hybrid algorithm, called EDUK2. This algorithm takes advantage of the majority of the known properties of UKP, particularly the diverse dominance relations and the important periodicity property. Extensive computational results show that, in all but a very few cases, EDUK2 significantly outperforms both MTU2 and EDUK, the currently available UKP solvers, as well the well-known general purpose mathematical programming optimizer CPLEX of ILOG. These experimental results demonstrate that the class of hard UKP instances needs to be redefined, and the authors offer their insights into the creation of such instances.     

Surgical case scheduling as a generalized job shop scheduling problem

Surgical case scheduling allocates hospital resources to individual surgical cases and decides on the time to perform the surgeries. This task plays a decisive role in utilizing hospital resources efficiently while ensuring quality of care for patients. This paper proposes a new surgical case scheduling approach which uses a novel extension of the Job Shop scheduling problem called multi-mode blocking job shop (MMBJS). It formulates the MMBJS as a mixed integer linear programming (MILP) problem and discusses the use of the MMBJS model for scheduling elective and add-on cases. The model is illustrated by a detailed example, and preliminary computational experiments with the CPLEX solver on practical-sized instances are 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.     

Fast algorithm for singly linearly constrained quadratic programs with box-like constraints

This paper focuses on a singly linearly constrained class of convex quadratic programs with box-like constraints. We propose a new fast algorithm based on parametric approach and secant approximation method to solve this class of quadratic problems. We design efficient implementations for our proposed algorithm and compare its performance with two state-of-the-art standard solvers called Gurobi and Mosek. Numerical results on a variety of test problems demonstrate that our algorithm is able to efficiently solve the large-scale problems with the dimension up to fifty million and it substantially outperforms Gurobi and Mosek in terms of the running time.     

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods

We present effective linear programming based computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal–Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex quadratic programs with linear constraints.     

Frequency optimization in public transportation systems: Formulation and metaheuristic approach

We study the transit frequency optimization problem, which aims to determine the time interval between subsequent buses for a set of public transportation lines given by their itineraries, i.e., sequences of stops and street sections. The solution should satisfy a given origin–destination demand and a constraint on the available fleet of buses. We propose a new mixed integer linear programming (MILP) formulation for an already existing model, originally formulated as a nonlinear bilevel one. The proposed formulation is able to solve to optimality real small-sized instances of the problem using MILP techniques. For solving larger instances we propose a metaheuristic which accuracy is estimated by comparing against exact results (when possible). Both exact and approximated approaches are tested by using existing cases, including a real one related to a small-city which public transportation system comprises 13 lines. The magnitude of the improvement of that system obtained by applying the proposed methodologies, is comparable with the improvements reported in the literature, related to other real systems. Also, we investigate the applicability of the metaheuristic to a larger-sized real case, comprising more than 130 lines.     

An integer optimization approach for reverse engineering of gene regulatory networks

Gene regulatory networks are a common tool to describe the chemical interactions between genes in a living cell. This paper considers the Weighted Gene Regulatory Network (WGRN) problem, which consists in identifying a reduced set of interesting candidate regulatory elements which can explain the expression of all other genes. We provide an integer programming formulation based on a graph model and derive from it a branch-and-bound algorithm which exploits the Lagrangian relaxation of suitable constraints. This allows to determine lower bounds tighter than CPLEX on most benchmark instances, with the exception of the sparser ones. In order to determine feasible solutions for the problem, which appears to be a hard task for general-purpose solvers, we also develop and compare two metaheuristic approaches, namely a Tabu Search and a Variable Neighborhood Search algorithm. The experiments performed on both of them suggest that diversification is a key feature to solve the problem.     

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.     

Job scheduling in virtual manufacturing cells with lot-streaming strategy: a new mathematical model formulation and a genetic algorithm approach

This paper discusses the job scheduling problem in virtual manufacturing cells (VMCs) with the objective of makespan minimization. In the VMC scheduling problem, each job undergoes different processing routes and there is a set of machines to process any operation. Jobs are produced in lot and lot-streaming is permitted. In addition, machines are distributed through the facility, which raises the travelling time issue. For this reason, the decisions are machine assignments, starting times and sub-lot sizes of the operations. We develop a new Mixed Integer Linear Programming (MILP) formulation that considers all aspects of the problem. Owing to the intractability matter, it is unlikely that the MILP could provide solutions for big-sized instances within a reasonable amount of time. We therefore present a Genetic Algorithm (GA) with a new chromosome structure for the VMC environment. Based on a wide range of examinations, comparative results show that GA is quite favourable and that it obtains the optimum solution for any of the instances in the case where sub-lot number equals 1.     

A Flexible, Fast, and Optimal Modeling Approach Applied to Crew Rostering at London Underground

We present a general modeling approach to crew rostering and its application to computer-assisted generation of rotation-based rosters (or rotas) at the London Underground. Our goals were flexibility, speed, and optimality, and our approach is unique in that it achieves all three. Flexibility was important because requirements at the Underground are evolving and because specialized approaches in the literature did not meet our flexibility-implied need to use standard solvers. We decompose crew rostering into stages that can each be solved with a standard commercial MILP solver. Using a 167 MHz Sun UltraSparc 1 and CPLEX 4.0 MILP solver, we obtained high-quality rosters in runtimes ranging from a few seconds to a few minutes within 2% of optimality. Input data were takes from different depots with crew sizes ranging from 30–150 drivers, i.e., with number of duties ranging from about 200–1000. Using an argument based on decomposition and aggregation, we prove the optimality of our approach for the overall crew rostering problem.     

Models and algorithms for three-stage two-dimensional bin packing

We consider the three-stage two-dimensional bin packing problem (2BP) which occurs in real-world applications such as glass, paper, or steel cutting. We present new integer linear programming formulations: models for a restricted version and the original version of the problem are developed. Both only involve polynomial numbers of variables and constraints and effectively avoid symmetries. Those models are solved using CPLEX. Furthermore, a branch-and-price (B&P) algorithm is presented for a set covering formulation of the unrestricted problem, which corresponds to a Dantzig-Wolfe decomposition of the polynomially-sized model. We consider column generation stabilization in the B&P algorithm using dual-optimal inequalities. Fast column generation is performed by applying a hierarchy of four methods: (a) a fast greedy heuristic, (b) an evolutionary algorithm, (c) solving a restricted form of the pricing problem using CPLEX, and finally (d) solving the complete pricing problem using CPLEX. Computational experiments on standard benchmark instances document the benefits of the new approaches: The restricted version of the integer linear programming model can be used to quickly obtain near-optimal solutions. The unrestricted version is computationally more expensive. Column generation provides a strong lower bound for 3-stage 2BP. The combination of all four pricing algorithms and column generation stabilization in the proposed B&P framework yields the best results in terms of the average objective value, the average run-time, and the number of instances solved to proven optimality.     

Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers

The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearizations are tight, but rarely exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation (Eur. J. Oper. Res. 2(3):204–211, 1978) is the smallest of these linearizations, but very weak. In this paper, we analyze how the Kaufman and Broeckx formulation can be tightened to obtain better QAP-MILP formulations. As shown in our numerical experiments, these tightened formulations remain small but computationally effective to solve the QAP by means of general purpose MILP solvers.     

On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon

A 0-1 quadratic programming model is presented for solving the strategic problem of timing the location of facilities and the assignment of customers to facilities in a multi-period setting. It is assumed that all parameters are known and, on the other hand, the quadratic character of the objective function is due to considering the interaction cost incurred by the joint assignment of customers belonging to different categories to a facility at a period. The plain use of a state-of-the-art MILP engine with capabilities for dealing with quadratic terms does not give any advantage over the matheuristic algorithm proposed in this work. In fact, the MILP engine was frequently running out of memory before reaching optimality for the equivalent mixed 0-1 linear formulation, being its best lower bound at that time instant too far from the incumbent solution for the large-sized instances which we have worked with. As an alternative, a fix-and-relax algorithm is presented. A deep computational comparison between MILP alternatives is performed, such that fix-and-relax provides a solution value very close to (and, frequently, a better than) the one provided by the MILP engine. The time required by fix-and-relax is very affordable, being frequently two times smaller than the time required by the MILP engine.     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

An exact solution procedure for a cluster hub location problem

This paper proposes a new (MIP) model formulation and a new solution procedure for the hub network design problem under a non-restrictive policy introduced by Sung and Jin [Sung, C.S., Jin, H.W., 2001. Dual-based approach for a hub network design problem under non-restrictive policy. European Journal of Operational Research 132 (1), 88–105]. The model formulation contains significantly fewer variables so that optimal solutions for the LP-relaxation of the model can be determined for large instances using standard procedures for LP-models. Furthermore, the LP-relaxation provides very tight lower bounds. Computational results are given, which demonstrate that the new model formulation allows for solving much larger instances. It turned out that the new (exact) solution procedure, which utilises the new model formulation, is faster than the heuristic proposed by Sung and Jin (2001). It is also shown that the problem is np-hard.