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.     

Real-world flexible resource profile scheduling with multiple criteria: learning scalarization functions for MIP and heuristic approaches

This article addresses a scheduling problem for a chemical research laboratory. Activities with potentially variable, non-rectangular resource allocation profiles must be scheduled on discrete renewable resources. A mixed-integer programming (MIP) formulation for the problem includes maximum time lags, custom resource allocation constraints, and multiple nonstandard objectives. We present a list scheduling heuristic that mimics the human decision maker and thus provides reference solutions. These solutions are the basis for an automated learning-based determination of coefficients for the convex combination of objectives used by the MIP and a dedicated variable neighborhood search (VNS) approach. The development of the VNS also involves the design of new neighborhood structures that prove particularly effective for the custom objectives under consideration. Relative improvements of up to 60% are achievable for isolated objectives, as demonstrated by the final computational study based on a broad spectrum of randomly generated instances of different sizes and real-world data from the company’s live system.     

Comparison of a branch-and-bound heuristic,a newsvendor-based heuristic and periodic Bailey rules for outpatients appointment scheduling systems

Appointment-based service systems admit limited number of customers at a specific time interval to make service providers more accessible by reducing customers’ waiting time and make the costly resources more productive. A traditional approach suggests the Bailey rule, which assigns one or more customers at the initial block and only one customer at remaining blocks. We prescribe two heuristic approaches and variations of the traditional Bailey rule to appointment scheduling systems with the objective of minimizing total expected costs of delay and idle times between blocks. The first heuristic adopts a branch-and-bound approach using forward dynamic programming and tries to fully enumerate with some restrictions. The second heuristic uses a sequential-inverse newsvendor approach using a starting solution. We conduct numerical tests, which show that both heuristics get near-optimal solutions in a quicker time than a commercial solver, CPLEX and that the second approach gives near-optimal solutions far faster than the first approach. In addition, we suggest the use of a periodic Bailey rule, which can be implemented easily in practice, and provides a close solution to the best result of both heuristics, depending upon cost parameters and service-time variances.     

The assignment-to-days problem in a school time-table,a heuristic approach

There is a lot of literature on time-tabling algorithms. In most of them the assumption is made that the weekly school time-table requirements are easily divided into daily requirements. But this is not the case when the school is large and the time-table involves complicated situations like settings and multiple periods. In this study a heuristic algorithm is proposed dealing with the assignment to individual days of the weekly requirements. Five British schools are used for a practical evaluation. Results are discussed and suggestions for further improvements are made.     

Nonsingularity,positive definiteness,and positive invertibility under fixed-point data rounding

For a real square matrix A and an integer d ? 0, let A _(d) denote the matrix formed from A by rounding off all its coefficients to d decimal places. The main problem handled in this paper is the following: assuming that A _(d) has some property, under what additional condition(s) can we be sure that the original matrix A possesses the same property? Three properties are investigated: nonsingularity, positive definiteness, and positive invertibility. In all three cases it is shown that there exists a real number α(d), computed solely from A _(d) (not from A), such that the following alternative holdsif d > α(d), then nonsingularity (positive definiteness, positive invertibility) of A _(d) implies the same property for A if d < α(d) and A _(d) is nonsingular (positive definite, positive invertible), then there exists a matrix A′ with A′_(d) = A _(d) which does not have the respective property.For nonsingularity and positive definiteness the formula for α(d) is the same and involves computation of the NP-hard norm ‖ · ‖_∞,1; for positive invertibility α(d) is given by an easily computable formula.     

Lifting,superadditivity, mixed integer rounding and single node flow sets revisited

In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for mixed integer programs. The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0–1 single node flow set. This paper appeared in 4OR, 1, 173–208 (2003). The first author is supported by the FNRS as a chercheur qualifié. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming. The scientific responsibility is assumed by the authors.     

Lifting,superadditivity, mixed integer rounding and single node flow sets revisited

In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for mixed integer programs. The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0-1 single node flow set.Received: December 2002, Revised: April 2003, AMS classification: 90C11, 90C27Laurence A. Wolsey: Corresponding author: CORE, Voie du Roman Pays 34, 1348 Louvain-la-Neuve, Belgium. The first author is supported by the FNRS as a research fellow. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Ministers Office, Science Policy Programming. The scientific responsibility is assumed by the authors.Laurence A. Wolsey: This research was also supported by the European Commission GROWTH Programme, Research Project LISCOS, Large Scale Integrated Supply Chain Optimization Software Based on Branch-and-Cut and Constraint Programming Methods, Contract No. GRDI-1999-10056, and the project TMR-DONET nr. ERB FMRX-CT98-0202.     

An optimal rounding gives a better approximation for scheduling unrelated machines

A polynomial-time algorithm is suggested for non-preemptive scheduling of n-independent jobs on m-unrelated machines to minimize the makespan. The algorithm has a worst-case performance ratio of 2−1/m. This is better than the earlier known best performance bound 2. Our approach gives the best possible approximation ratio that can be achieved using the rounding approach.     

On a primal-proximal heuristic in discrete optimization

Lagrangian relaxation is useful to bound the optimal value of a given optimization problem, and also to obtain relaxed solutions. To obtain primal solutions, it is conceivable to use a convexification procedure suggested by D.P. Bertsekas in 1979, based on the proximal algorithm in the primal space.The present paper studies the theory assessing the approach in the framework of combinatorial optimization. Our results indicate that very little can be expected in theory, even though fairly good practical results have been obtained for the unit-commitment problem.     

MIP models for minimizing total tardiness in a two-machine flow shop

We propose compact mixed-integer programming models for the Open image in new window -hard problem of minimizing tardiness in a two-machine flow shop. Also, we propose valid inequalities that aim at tightening the models’ representations. We provide empirical evidence that the linear programming relaxation of an enhanced formulation yields an excellent lower bound that consistently outperforms the best bound from the literature. We further provide the results of extensive computational experiments that attest to the efficacy of the proposed MIP models. In particular, our computational study reveals that most of the 30-job hard instances are optimally solved using the proposed MIP models. Furthermore, we found that even much larger instances, with up to 70 jobs, can be solved for several problem classes.     

A heuristic methodology for sizing a large-scale system of constrained, reusable resources

This paper proposes a methodology for sizing certain large-scale systems of reusable, capacity-constrained resources engaged in tasks of varying duration. A heuristic program schedules resources throughout a finite planning horizon using two decision variables: varying resource capacity for meeting demand and varying task duration. A model of the problem and heuristic scheduling program are presented. A sequential, iterative sizing procedure determines the number of system resources to meet demand at each stage of the problem. Results compare the methodology with heuristics used in practice to schedule resources and size a real-world, large-scale training system.     

A smoothing heuristic for a bilevel pricing problem

In this paper, we provide a heuristic procedure, that performs well from a global optimality point of view, for an important and difficult class of bilevel programs. The algorithm relies on an interior point approach that can be interpreted as a combination of smoothing and implicit programming techniques. Although the algorithm cannot guarantee global optimality, very good solutions can be obtained through the use of a suitable set of parameters. The algorithm has been tested on large-scale instances of a network pricing problem, an application that fits our modeling framework. Preliminary results show that on hard instances, our approach constitutes an alternative to solvers based on mixed 0–1 programming formulations.     

Undercover: a primal MINLP heuristic exploring a largest sub-MIP

We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programs (MINLPs) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a smallest set of variables to fix, a so-called cover, such that each constraint is linearized. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We apply domain propagation to try to avoid infeasibilities, and conflict analysis to learn additional constraints from infeasibilities that are nonetheless encountered. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and MINLPs. It turns out that the majority of these instances allows for small covers. Although general in nature, we show that the heuristic is most successful on MIQCPs. It nicely complements existing root-node heuristics in different state-of-the-art solvers and helps to significantly improve the overall performance of the MINLP solver SCIP.     

Robust portfolio optimization with a hybrid heuristic algorithm

Estimation errors in both the expected returns and the covariance matrix hamper the construction of reliable portfolios within the Markowitz framework. Robust techniques that incorporate the uncertainty about the unknown parameters are suggested in the literature. We propose a modification as well as an extension of such a technique and compare both with another robust approach. In order to eliminate oversimplifications of Markowitz’ portfolio theory, we generalize the optimization framework to better emulate a more realistic investment environment. Because the adjusted optimization problem is no longer solvable with standard algorithms, we employ a hybrid heuristic to tackle this problem. Our empirical analysis is conducted with a moving time window for returns of the German stock index DAX100. The results of all three robust approaches yield more stable portfolio compositions than those of the original Markowitz framework. Moreover, the out-of-sample risk of the robust approaches is lower and less volatile while their returns are not necessarily smaller.     

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.     

A heuristic algorithm for a dial-a-ride problem with time windows,multiple capacities,and multiple objectives

The paper describes a system for the solution of a static dial-a-ride routing and scheduling problem with time windows (DARPTW). The problem statement and initialization of the development project was made by the Copenhagen Fire-Fighting Service (CFFS). The CFFS needed a new system for scheduling elderly and disabled persons, involving about 50.000 requests per year. The problem is characterized by, among other things, multiple capacities and multiple objectives. The capacities refer to the fact that a vehicle may be equipped with e.g. normal seats, children seats or wheel chair places. The objectives relate to a number of concerns such as e.g. short driving time, high vehicle utilization or low costs. A solution algorithm REBUS based on an insertion heuristics was developed. The algorithm permits in a flexible way weighting of the various goals such that the solution reflects the user's preferences. The algorithm is implemented in a dynamic environment intended for on-line scheduling. Thus, a new request for service is treated in less than 1 second, permitting an interactive user interface.     

A heuristic approach to a weighted maxmin dispersion problem

In this paper, the nonconvex form of the weighted maxmin dispersionproblem is converted to a form involving the maximization ofconvex functions over a polytope, for which algorithms exist.A heuristic approach is given, together with associated resultson optimality and bounds on loss of optimality.     

A heuristic algorithm for a chance constrained stochastic program

A chance constrained stochastic program is considered that arises from an application to college enrollments and in which the objective function is the expectation of a linear function of the random variables. When these random variables are independent and normally distributed with mean and variance that are linear in the decision variables, the deterministic equivalent of the problem is a nonconvex nonlinear knapsack problem. The optimal solution to this problem is characterized and a greedy-type heuristic algorithm that exploits this structure is employed. Computational results show that the algorithm performs well, especially when the normal random variables are approximations of binomial random variables.