Solving large set covering problems for crew scheduling

This paper presents a computationally effective heuristic method which produces good-quality solutions for large-scale set covering problems with thousands of constraints and about one million variables. The need to solve such large-scale problems arises from a crew scheduling problem of mass transit agencies where the number of work shifts required has to be minimized. This problem may be formulated as a large-scale non-unicost set covering problem whose rows are trips to be performed while columns stand for round trips. The proposed method is mainly based on lagragian relaxation and sub-gradient optimization. After the reduction of the number of rows and columns by the logical tests, “greedy” heuristic algorithms provide upper and lower bounds which are continuously improved to produce goodquality solutions. Computational results, regarding randomly generated problems and real life problems concerning crew scheduling at Italian Railways Company, show that good-quality solutions can be obtained at an acceptable computational cost. This work was supported by the project “Progetto Finalizzato Transporti 2” of National Research Council of Italy (C.N.R.) contract No. 94.01436PF74 and by “Ferrovie dello Stato S.p.A.”     

Two-level evolutionary approach to the survivable mesh-based transport network topological design

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be NP\mathcal{NP} -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.     

Comparative analysis of three metaheuristics for short-term open pit block sequencing

This paper presents the application of simulated annealing (SA), Tabu search (TS) and hybrid TS–SA to solve a real-world mining optimisation problem called open pit block sequencing (OPBS). The OPBS seeks the optimum extraction sequences under a variety of geological and technical constraints over short-term horizons. As industry-scale OPBS instances are intractable for standard mixed integer programming (MIP) solvers, SA, TS and hybrid TS–SA are developed to solve the OPBS problem. MIP exact solution is also combined with the proposed metaheuristics to polish solutions in feasible neighbourhood moves. Extensive sensitivity analysis is conducted to analyse the characteristics and determine the optimum sets of values of the proposed metaheuristics algorithms’ parameters. Computational experiments show that the proposed algorithms are satisfactory for solving the OPBS problem. Additionally, this comparative study shows that the hybrid TS–SA is superior to SA or TS in solving the OPBS problem in several aspects.     

The Economic Lot Scheduling Problem without Capacity Constraints

This study presents a comprehensive analysis on the Economic Lot Scheduling Problem (ELSP) without capacity constraints. We explore the optimality structure of the ELSP without capacity constraints and discover that the curve for the optimal objective values is piecewise convex with repsect to B, i.e., the values of basic period. The theoretical properties of the junction points on the piecewise convex curve not only provides us the information on “which product i” to modify, but also on “where on the B-axis” to change the set of optimal multpliers in the search process. By making use of the junction points, we propose an effective search algorithm to secure a global optimal solution for the ELSP without capacity constraints. Also, we use random experiments to verify that the proposed algorithm is efficient. The results in this paper lay important foundation for deriving an efficient heuristic to solve the conventional ELSP with capacity constraints.     

Discrete time dynamic traffic assignment models and solution algorithm for managed lanes

“Managed” lanes of highways usually refer to lanes that are not open to all types of vehicles, such as “High Occupancy Vehicles” (HOV) lanes and “High Occupancy Toll” (HOT) lanes, etc. The HOV lanes of highways are reserved only for vehicles with a driver and one or more passengers. Whereas, HOT lanes allow all vehicles but require tolls from the vehicles with no passenger except the driver. In this paper, we present a discrete-time traffic assignment system optimum model to predict the optimal traffic flows on managed lanes at various times in the entire planning horizon. This model minimizes the overall delay (travel time) and belongs to the class of dynamic traffic assignment (DTA) problems. When applied to general networks, DTA problems can be large and difficult to solve, but the problem is manageable when it is applied to a network with managed lanes. In particular, the DTA model in this paper for managed lanes is reduced to a mixed integer program for which several efficient heuristic algorithms exist. This paper also discusses the special properties of the discrete-time DTA model, based upon which a heuristic algorithm is proposed. Numerical results show that this algorithm is efficient for many cases of the managed lane problems.     

A constraint programming approach for the resource-constrained project scheduling problem

A “pure” Constraint Programming approach for the Resource-Constrained Project Scheduling Problem (RCPSP) is presented. Our basic idea was to substitute the resource constraints by a set of “sub-constraints” generated as needed. Each of these sub-constraints corresponds to a set of tasks that cannot be executed together without violating one of the resource constraints. A filtering algorithm for these sub-constraints has been developed. When applied to the initial resource constraints together with known filtering algorithms, this new filtering algorithm provides very good numerical results.     

Optimization-based heuristics for underground mine scheduling

Underground mine production scheduling possesses mathematical structure similar to and yields many of the same challenges as general scheduling problems. That is, binary variables represent the time at which various activities are scheduled. Typical objectives seek to minimize costs or some measure of production time, or to maximize net present value; two principal types of constraints exist: (i) resource constraints and (ii) precedence constraints. In our setting, we maximize “discounted metal production” for the remaining life of an underground lead and zinc mine that uses three different underground methods to extract the ore. Resource constraints limit the grade, tonnage, and backfill paste (used for structural stability) in each time period, while precedence constraints enforce the sequence in which extraction (and backfill) is performed in accordance with the underground mining methods used. We tailor exact and heuristic approaches to reduce model size, and develop an optimization-based decomposition heuristic; both of these methods transform a computationally intractable problem to one for which we obtain solutions in seconds, or, at most, hours for problem instances based on data sets from the Lisheen mine near Thurles, Ireland.     

Dynamic Game Model of Endogenous Growth with Consumption Externalities

This paper introduces consumption externalities into an endogenous growth model of common capital accumulation and characterizes balanced growth equilibria. Contrary to the standard argument in previous studies, we show that the growth rate in a feedback Nash equilibrium can be higher than that in an open-loop Nash equilibrium if agents strongly admire the consumption of others. This result is irrelevant to whether preferences exhibit “keeping up with the Joneses” or “running away from the Joneses”.     

Exact and heuristic algorithms for routing problems

This is a summary of the authors PhD thesis supervised by Daniele Vigo and defended on 30 March 2010, at the Università di Bologna. The thesis is written in English and is available from the author upon request. Several rich routing problems attaining to the transportation area have been studied. “Simple” algorithms have been proposed to solve them, both exact and heuristic, producing high quality solutions and transferrable methods.     

Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology

This paper addresses the problem of scheduling activities in projects with stochastic activity durations. The aim is to determine for each activity a gate—a time before it the activity cannot begin. Setting these gates is analogous to setting inventory levels in the news vendor problem. The resources required for each activity are scheduled to arrive according to its gate. Since activities’ durations are stochastic, the start and finish time of each activity is uncertain. This fact may lead to one of two outcomes: (1) an activity is ready to start its processing as all its predecessors have finished, but it cannot start because the resources required for it were scheduled to arrive at a later time. (2) The resources required for the activity have arrived and are ready to be used but the activity is not ready to start because of precedence constraints. In the first case we will incur a “holding” cost while in the second case, we will incur a “shortage” cost. Our objective is to set gates so as to minimize the sum of the expected holding and shortage costs. We employ the Cross-Entropy method to solve the problem. The paper describes the implementation of the method, compares its results to various heuristic methods and provides some insights towards actual applications.     

ω 1 can be measurable

It is shown that ifZF + the axiom of choice + “there is a measurable cardinal” is consistent thenZF + “ω ₁ is measurable” is consistent. The corresponding model is a symmetric submodel of the Cohen-type extension which collapses the first measurable cardinal onto ω₀.     

Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology

This paper addresses the problem of scheduling activities in projects with stochastic activity durations. The aim is to determine for each activity a gate—a time before it the activity cannot begin. Setting these gates is analogous to setting inventory levels in the news vendor problem. The resources required for each activity are scheduled to arrive according to its gate. Since activities’ durations are stochastic, the start and finish time of each activity is uncertain. This fact may lead to one of two outcomes: (1) an activity is ready to start its processing as all its predecessors have finished, but it cannot start because the resources required for it were scheduled to arrive at a later time. (2) The resources required for the activity have arrived and are ready to be used but the activity is not ready to start because of precedence constraints. In the first case we will incur a “holding” cost while in the second case, we will incur a “shortage” cost. Our objective is to set gates so as to minimize the sum of the expected holding and shortage costs. We employ the Cross-Entropy method to solve the problem. The paper describes the implementation of the method, compares its results to various heuristic methods and provides some insights towards actual applications.     

Pivot,Cut, and Dive: a heuristic for 0-1 mixed integer programming

This paper describes a heuristic for 0-1 mixed-integer linear programming problems, focusing on “stand-alone” implementation. Our approach is built around concave “merit functions” measuring solution integrality, and consists of four layers: gradient-based pivoting, probing pivoting, convexity/intersection cutting, and diving on blocks of variables. The concavity of the merit function plays an important role in the first and third layers, as well as in connecting the four layers. We present both the mathematical and software details of a test implementation, along with computational results for several variants.     

On synthesizing impulse controls and the theory of fast controls

We describe the theory of feedback control in the class of impulse-type inputs which allow higher derivatives of delta functions. We provide solutions based on Hamiltonian techniques in the dynamic programming form. Further we describe physically realizable approximations of the “ideal” impulse-type solutions by bounded functions which may also serve as “fast” feedback controls that solve the target control problem in arbitrarily small time.     

On numerical optimization theory of infinite kernel learning

In Machine Learning algorithms, one of the crucial issues is the representation of the data. As the given data source become heterogeneous and the data are large-scale, multiple kernel methods help to classify “nonlinear data”. Nevertheless, the finite combinations of kernels are limited up to a finite choice. In order to overcome this discrepancy, a novel method of  “infinite”  kernel combinations is proposed with the help of infinite and semi-infinite programming regarding all elements in kernel space. Looking at all infinitesimally fine convex combinations of the kernels from the infinite kernel set, the margin is maximized subject to an infinite number of constraints with a compact index set and an additional (Riemann–Stieltjes) integral constraint due to the combinations. After a parametrization in the space of probability measures, it becomes semi-infinite. We adapt well-known numerical methods to our infinite kernel learning model and analyze the existence of solutions and convergence for the given algorithms. We implement our new algorithm called “infinite” kernel learning (IKL) on heterogenous data sets by using exchange method and conceptual reduction method, which are well known numerical techniques from solve semi-infinite programming. The results show that our IKL approach improves the classifaction accuracy efficiently on heterogeneous data compared to classical one-kernel approaches.     

Lagrangean relaxation based heuristics for lot sizing with setup times

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design a primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop a simple branch and bound heuristic to solve the problem. Computational results on test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.     

A piecewise linearization for retail shelf space allocation problem and a local search heuristic

Retail shelf space allocation problem is well known in literature. In this paper, we make three contributions to retail shelf space allocation problem considering space elasticity (SSAPSE). First, we reformulate an existing nonlinear model for SSAPSE to an integer programming (IP) model using piecewise linearization. Second, we show that the linear programming relaxation of the proposed IP model produces tight upper bound. Third, we develop a heuristic that consistently produces near optimal solutions for randomly generated instances of problems with size (products, shelves) varying from (25, 5) to (200, 50) within a minute of CPU time.     

A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems

This paper presents a hybrid multi-objective model that combines integer programming (IP) and variable neighbourhood search (VNS) to deal with highly-constrained nurse rostering problems in modern hospital environments. An IP is first used to solve the subproblem which includes the full set of hard constraints and a subset of soft constrains. A basic VNS then follows as a postprocessing procedure to further improve the IP’s resulting solutions. The satisfaction of the excluded constraints from the preceding IP model is the major focus of the VNS. Very promising results are reported compared with a commercial genetic algorithm and a hybrid VNS approach on real instances arising in a Dutch hospital. The comparison results demonstrate that our hybrid approach combines the advantages of both the IP and the VNS to beat other approaches in solving this type of problems. We also believe that the proposed methodology can be applied to other resource allocation problems with a large number of constraints.     

Fast inputs in the problem of control synthesis under uncertainty

We present a class of bounded control inputs that permits one to solve target control synthesis problems for linear systems with geometric (“instantaneous”) constraints on the perturbations by reduction to simpler programmed control problems.     

A new dispatching rule based genetic algorithm for the multi-objective job shop problem

Hyper-heuristics or “methodologies to choose heuristics” are becoming increasingly popular given their suitability to solve hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of NSGA-II when handling multi-objective problems.