Modeling formulation and a new heuristic for the railroad blocking problem

The railroad blocking problem is an important issue at the tactical level of railroad freight transportation. This problem consists of determining paths between the origins and destinations of each shipment to minimize the operating and user costs while satisfying the railroad supply and demand restrictions. A mixed-integer program (MIP) is developed to find the optimal paths, and a new heuristic is developed to solve the proposed model. This heuristic decomposes the model into two sub-problems of manageable size and then provides feasible solutions. We discuss the performance of the proposed heuristic for a set of instances with up to 90 stations. A comparison with the CPLEX MIP solver shows that the heuristic gives the exact solution for 10 out of 15 instances. For the remaining instances, the heuristic obtained solutions within a tolerance of 0.03–0.84%. Furthermore, compared with the CPLEX MIP solver, the heuristic reduced the run time by an average of 85% for all 15 instances. Finally, we present the computational results of the heuristic applied to Iranian railroads.     

Mixed Integer Programming Approaches to Treatment Planning for Brachytherapy – Application to Permanent Prostate Implants

Mixed integer programming models and computational strategies developed for treatment planning optimization in brachytherapy are described. The problem involves the designation of optimal placement of radioactive sources (seeds) inside a tumor site. Two MIP models are described. The resulting MIP instances are difficult to solve, due in large part to dense constraint matrices with large disparities in the magnitudes of the nonzero entries. A matrix reduction and approximation scheme is presented as a computational strategy for dealing with the dense matrices. Penalty-based primal heuristic and branching strategies to assist in the solution process are also described. Numerical results are presented for 20 MIP instances associated with prostate cancer cases. Compared to currently used computer-aided planning methods, plans derived via the MIP approach use fewer seeds (20–30 fewer) and needles, and provide better coverage and conformity – measures commonly used to assess the quality of treatment plans. Good treatment plans are returned in 15 CPU minutes, suggesting that incorporation of this MIP-based optimization module into a real-time comprehensive treatment planning system is feasible.     

Flexible job shop scheduling problem for parallel batch processing machine with compatible job families

Flexible Job-Shop Scheduling Problem (FJSP) with Parallel Batch processing Machine (PBM) is studied. First, a Mixed Integer Programming (MIP) formulation is proposed for the first time. In order to address an NP-hard structure of this problem, the formulation is modified to selectively schedule jobs. Although there are many jobs on a given floor, semiconductor manufacturing is most challenged by priority jobs that promise a significant amount of financial compensation in exchange for an expedited delivery. This modification could leave some non-priority jobs unscheduled. However, it vastly expedites the discovery of improving solutions by first branching on integer variables with higher priority jobs. This study then turns job-dependent processing times into job-independent ones by assuming a machine has an equal processing time on different jobs. This assumption is roughly true or acceptable for the sake of the reduced computational time in the industry. These changes significantly reduce computational time compared to the original model when tested on a set of common problem instances from the literature. Computational results show that this proposed model can generate an effective schedule for large problems. Author encourages other researchers to propose an improved MIP model.     

A MIP-based framework and its application on a lot sizing problem with setup carryover

In this paper we present a framework to tackle mixed integer programming problems based upon a “constrained” black box approach. Given a MIP formulation, a black-box solver, and a set of incumbent solutions, we iteratively build corridors around such solutions by adding exogenous constraints to the original MIP formulation. Such corridors, or neighborhoods, are then explored, possibly to optimality, with a standard MIP solver. An iterative approach in the spirit of a hill climbing scheme is thus used to explore subportions of the solution space. While the exploration of the corridor relies on a standard MIP solver, the way in which such corridors are built around the incumbent solutions is influenced by a set of factors, such as the distance metric adopted, or the type of method used to explore the neighborhood. The proposed framework has been tested on a challenging variation of the lot sizing problem, the multi-level lot sizing problem with setups and carryovers. When tested on 1920 benchmark instances of such problem, the algorithm was able to solve to near optimality every instance of the benchmark library and, on the most challenging instances, was able to find high quality solutions very early in the search process. The algorithm was effective, in terms of solution quality as well as computational time, when compared with a commercial MIP solver and the best algorithm from the literature.     

Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time

This study considers a hybrid assembly-differentiation flowshop scheduling problem (HADFSP), in which there are three production stages, including components manufacturing, assembly, and differentiation. All the components of a job are processed on different machines at the first stage. Subsequently, they are assembled together on a common single machine at the second stage. At the third stage, each job of a particular type is processed on a dedicated machine. The objective is to find a job schedule to minimize total flow time (TFT). At first, a mixed integer programming (MIP) model is formulated and then some properties of the optimal solution are presented. Since the NP-hardness of the problem, two fast heuristics (SPT-based heuristic and NEH-based heuristic) and three hybrid meta-heuristics (HGA-VNS, HDDE-VNS and HEDA-VNS) are developed for solving medium- and large-size problems. In order to evaluate the performances of the proposed algorithms, a lower bound for the HADFSP with TFT criteria (HADFSP-TFT) is established. The MIP model and the proposed algorithms are compared on randomly generated problems. Computational results show the effectiveness of the MIP model and the proposed algorithms. The computational analysis indicates that, in average, the HDDE-VNS performs better and more robustly than the other two meta-heuristics, whereas the NEH heuristic consume little time and could reach reasonable solutions.     

Exploring relaxation induced neighborhoods to improve MIP solutions

Given a feasible solution to a Mixed Integer Programming (MIP) model, a natural question is whether that solution can be improved using local search techniques. Local search has been applied very successfully in a variety of other combinatorial optimization domains. Unfortunately, local search relies extensively on the notion of a solution neighborhood, and this neighborhood is almost always tailored to the structure of the particular problem being solved. A MIP model typically conveys little information about the underlying problem structure. This paper considers two new approaches to exploring interesting, domain-independent neighborhoods in MIP. The more effective of the two, which we call Relaxation Induced Neighborhood Search (RINS), constructs a promising neighborhood using information contained in the continuous relaxation of the MIP model. Neighborhood exploration is then formulated as a MIP model itself and solved recursively. The second, which we call guided dives, is a simple modification of the MIP tree traversal order. Loosely speaking, it guides the search towards nodes that are close neighbors of the best known feasible solution. Extensive computational experiments on very difficult MIP models show that both approaches outperform default CPLEX MIP and a previously described approach for exploring MIP neighborhoods (local branching) with respect to several different metrics. The metrics we consider are quality of the best integer solution produced within a time limit, ability to improve a given integer solution (of both good and poor quality), and time required to diversify the search in order to find a new solution.Mathematics Subject Classification (2000):20E28, 20G40, 20C20Acknowledgement We wish to thank the two anonymous referees for their helpful comments.     

SAPI: Statistical Analysis of Propagation of Incidents. A new approach for rescheduling trains after disruptions

In this paper, we present a new approach to solve the railway rescheduling problem. This problem deals with the reparation of a disturbed railway timetable after incidents in such a way to minimize the difference between the original plan and the new provisional plan. We use a mixed integer linear programming (MIP) formulation that models this problem correctly. However, the large number of variables and constraints denies the possibility to solve this problem efficiently using a standard MIP solver. A new approach called SAPI (Statistical Analysis of Propagation of Incidents) has been developed to tackle the problem. The key point of SAPI is to estimate the probability that an event, one step of the itinerary of a train, is affected by a set of incidents. Using these probabilities, the search space is reduced, obtaining very good solutions in a short time. The method has been tested with two different networks located in France and Chile. The numerical results show that our procedure is viable in practice.     

An infinite horizon mathematical programming model of a multicohort single species fishery

Fishery policy evaluation should take account of the initial state of the fishery and the population dynamics of the fish stock. Although multicohort bioeconomic fishery policy evaluation models have been developed, the results from these models depend on the choice of planning period and the desired state of the stock at the end of this period. In this paper it is noted that these limitations can be overcome by evaluating fishery policy over an infinite time horizon, and a mixed integer programming (MIP) model is developed for carrying out this form of analysis in a multicohort single species fishery. This new MIP model allows policies to be evaluated over an infinite horizon by incorporating results from a steady state fishery model into a multiperiod framework. The use of this MIP model in determining policies for reaching and maintaining a steady state is illustrated.     

A mixed integer programming approach for allocating operating room capacity

We have developed a methodology for allocating operating room capacity to specialties. Our methodology consists of a finite-horizon mixed integer programming (MIP) model which determines a weekly operating room allocation template that minimizes inpatients' cost measured as their length of stay. A number of patient type priority (eg emergency over non-emergency patient) and clinical constraints (eg maximum number of hours allocated to each specialty, surgeon, and staff availability) are included in the formulation. The optimal solution from the analytical model is inputted into a simulation model that captures some of the randomness of the processes (eg surgery time, demand, arrival time, and no-show rate of the outpatients) and non-linearities (eg the MIP assumes proportional allocation of demand satisfaction (output) with room allocation (input)). The simulation model outputs the average length of stay for each specialty and the room utilization. On a case example of a Los Angeles County Hospital, we show how the hospital length of stay pertaining to surgery can be reduced.     

The mathematical model and optimistic algorithm of two protein structures alignment

Protein structure alignment is one of the most important computational problems in molecular biology. From the viewpoint of computational complexity, a pairwise structure alignment is a NP-hard problem. In this paper, based on the discrepancy of two proteins, we define the structure alignment as a mixed integer-programming (MIP) problem with the simpler form and prove the existence of optimal solution. The optimal alignment is achieved by incorporating improved complete information set method used to modify the score matrix into iterative double dynamic programming algorithm. Convergence of algorithm is proved. A number of benchmark examples are tested. The results show that our model and approach are general and improve computational efficiency as well as quality of the structure alignment.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

A hybrid optimization approach for multi-level capacitated lot-sizing problems

Solving multi-level capacitated lot-sizing problems is still a challenging task, in spite of increasing computational power and faster algorithms. In this paper a new approach combining an ant-based algorithm with an exact solver for (mixed-integer) linear programs is presented. A MAX–MIN ant system is developed to determine the principal production decisions, a LP/MIP solver is used to calculate the corresponding production quantities and inventory levels. Two different local search methods and an improvement strategy based on reduced mixed-integer problems are developed and integrated into the ant algorithm. This hybrid approach provides superior results for small and medium-sized problems in comparison to the existing approaches in the literature. For large-scale problems the performance of this method is among the best.     

Product allocation to different types of distribution center in retail logistics networks

We consider the problem of assigning stockkeeping units to distribution centers (DCs) belonging to different DC types of a retail network, e.g., central, regional, and local DCs. The problem is motivated by the real situation of a retail company and solved by an MIP solution approach. The MIP model reflects the interdependencies between inbound transportation, outbound transportation and instore logistics as well as capital tied up in inventories and differences in picking costs between the warehouses. A novel solution approach is developed and applied to a real-life case of a leading European grocery retail chain. The application of the new approach results in cost savings of 6% of total operational costs compared to the present assignment. These savings amount to several million euros per year. In-depth analyses of the results and sensitivity analyses provide insights into the solution structure and the major related issues.     

Dynamically similar control systems and a globally minimum gain control technique: IMSC

The concept of dynamically similar control systems is introduced. The necessary and sufficient conditions to minimize a quadratic modal gain measure are given for dynamically similar closed-loop control systems. The globally minimum modal gain is obtained when the independent modal space control (IMSC) is used. Corollaries of the results for the control of infinite-dimensional structural distributed parameter systems (DPS) are given. Based on the results, a modal interaction parameter (MIP) is defined for all control systems. The minimum value of MIP is zero and uniquely corresponds to the IMSC. A nonzero value of MIP corresponds to all other coupled control (CC) designs and implies suboptimality relative to the IMSC design. The relative optimality of the real-space gain matrices of the IMSC and the CC designs depends on the actuator locations for the IMSC. Based on this, a real-space interaction parameter (RIP) is defined. A positive value of RIP renders IMSC optimal in its real-space gain matrix. The MIP and RIP are indications of suboptimality of a particular control technique and can be used to tune-up the control design via actuator locations. Actuator distribution criteria are suggested for both CC and IMSC designs, based on the values of MIP and RIP, respectively.This work was supported by the National Science Foundation, Grant No. MEA-82-04920.     

An efficient strategy for the activation of MIP relaxations in a multicore global MINLP solver

Solving mixed-integer nonlinear programming (MINLP) problems to optimality is a NP-hard problem, for which many deterministic global optimization algorithms and solvers have been recently developed. MINLPs can be relaxed in various ways, including via mixed-integer linear programming (MIP), nonlinear programming, and linear programming. There is a tradeoff between the quality of the bounds and CPU time requirements of these relaxations. Unfortunately, these tradeoffs are problem-dependent and cannot be predicted beforehand. This paper proposes a new dynamic strategy for activating and deactivating MIP relaxations in various stages of a branch-and-bound algorithm. The primary contribution of the proposed strategy is that it does not use meta-parameters, thus avoiding parameter tuning. Additionally, this paper proposes a strategy that capitalizes on the availability of parallel MIP solver technology to exploit multicore computing hardware while solving MINLPs. Computational tests for various benchmark libraries reveal that our MIP activation strategy works efficiently in single-core and multicore environments.     

Selecting appropriate machine learning methods for digital soil mapping

Digital soil mapping (DSM) increasingly makes use of machine learning algorithms to identify relationships between soil properties and multiple covariates that can be detected across landscapes. Selecting the appropriate algorithm for model building is critical for optimizing results in the context of the available data. Over the past decade, many studies have tested different machine learning (ML) approaches on a variety of soil data sets. Here, we review the application of some of the most popular ML algorithms for digital soil mapping. Specifically, we compare the strengths and weaknesses of multiple linear regression (MLR), k-nearest neighbors (KNN), support vector regression (SVR), Cubist, random forest (RF), and artificial neural networks (ANN) for DSM. These algorithms were compared on the basis of five factors: (1) quantity of hyperparameters, (2) sample size, (3) covariate selection, (4) learning time, and (5) interpretability of the resulting model. If training time is a limitation, then algorithms that have fewer model parameters and hyperparameters should be considered, e.g., MLR, KNN, SVR, and Cubist. If the data set is large (thousands of samples) and computation time is not an issue, ANN would likely produce the best results. If the data set is small (<100), then Cubist, KNN, RF, and SVR are likely to perform better than ANN and MLR. The uncertainty in predictions produced by Cubist, KNN, RF, and SVR may not decrease with large datasets. When interpretability of the resulting model is important to the user, Cubist, MLR, and RF are more appropriate algorithms as they do not function as “black boxes.” There is no one correct approach to produce models for predicting the spatial distribution of soil properties. Nonetheless, some algorithms are more appropriate than others considering the nature of the data and purpose of mapping activity.     

A hierarchy of relaxations for linear generalized disjunctive programming

Generalized disjunctive programming (GDP), originally developed by Raman and Grossmann (1994), is an extension of the well-known disjunctive programming paradigm developed by Balas in the mid 70s in his seminal technical report (Balas, 1974). This mathematical representation of discrete-continuous optimization problems, which represents an alternative to the mixed-integer program (MIP), led to the development of customized algorithms that successfully exploited the underlying logical structure of the problem. The underlying theory of these methods, however, borrowed only in a limited way from the theories of disjunctive programming, and the unique insights from Balas’ work have not been fully exploited.In this paper, we establish new connections between the fields of disjunctive programming and generalized disjunctive programming for the linear case. We then propose a novel hierarchy of relaxations to the original linear GDP model that subsumes known relaxations for this model, and show that a subset of these relaxations are tighter than the latter. We discuss the usefulness of these relaxations within the context of MIP and illustrate these results on the classic strip-packing problem.     

A fractional programming approach for retail category price optimization

We present a new mixed-integer programming (MIP) approach to study certain retail category pricing problems that arise in practice. The motivation for this research arises from the need to design innovative analytic retail optimization techniques at Oracle Corporation to not only predict the empirical effect of price changes on the overall sales and revenue of a category, but also to prescribe optimal dynamic pricing recommendations across a category or demand group. A multinomial logit nonlinear optimization model is developed, which is recast as a discrete, nonlinear fractional program (DNFP). The DNFP model employs a bi-level, predictive modeling framework to manage the empirical effects of price elasticity and competition on sales and revenue, and to maximize the gross-margin of the demand group, while satisfying certain practical side-constraints. This model is then transformed by using the Reformulation–Linearization Technique in tandem with a sequential bound-tightening scheme to recover an MIP formulation having a relatively tight underlying linear programming relaxation, which can be effectively solved by any commercial optimization software package. We present sample computational results using randomly generated instances of DNFP having different constraint settings and price range restrictions that are representative of common business requirements, and analyze the empirical effects of certain key modeling parameters. Our results indicate that the proposed retail price optimization methodology can be effectively deployed within practical retail category management applications for solving DNFP instances that typically occur in practice.     

A MIP approach for some practical packing problems: Balancing constraints and tetris-like items

This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach is proposed. The three-dimensional single bin packing problem is considered. It consists of orthogonally placing, with possibility of rotation, the maximum number of parallelepipeds into a given parallelepiped. A MIP formulation of the problem is reported together with a MIP-based heuristic approach. Balancing conditions are furthermore examined, as well as the orthogonal placement (with rotation) of tetris-like items into a rectangular domain.Received: September 2003, Revised: February 2004, AMS classification: 90B99, 05B40, 90C90, 90C59Thanks are due to T. A. Ciriani for the important suggestions given for the whole paper and to S. Gliozzi (IBM, Business Consulting Services) for the significant support offered, in particular in discussing the topics presented in Sect. 2.1.     

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.