Search

We consider the patient-to-bed assignment problem that arises in hospitals. Both emergency patients who require hospital admission and elective patients who have had surgery need to be found a bed in the most appropriate ward. The patient-to-bed assignment problem arises when a bed request is made, but a bed in the most appropriate ward is unavailable. In this case, the next-best decision out of a many alternatives has to be made, according to some suitable decision making algorithm. We construct a Markov chain to model this problem in which we consider the effect on the length of stay of a patient whose treatment and recovery consists of several stages, and can be affected by stays in or transfers to less suitable wards. We formulate a dynamic program recursion to optimise an objective function and calculate the optimal decision variables, and discuss simulation techniques that are useful when the size of the problem is too large. We illustrate the theory with some numerical examples.

In this paper, we develop a new bi-objective model for dynamic weapon-target assignment problem. We consider that the initial weapon assignment plan of defense is disrupted during engagement because of a destroyed air target, breakdown of a weapon system or a new incoming air target. The objective functions are defined as the maximization of probability of no-leaker and the maximization of stability in engagement order of weapon systems. Stability is defined as assigning same air target in sequence in engagement order of a weapon system so that reacquisition and re-tracking of air target are not required by sensors. We propose a new solution procedure to generate updated assignment plans by maximizing efficiency of defense while maximizing stability through swapping weapon engagement orders. The proposed solution procedure generates non-dominated solutions from which defense can quickly choose the most-favored course of action. We solve a set of representative problems with different sizes and present computational results to evaluate effectiveness of the proposed approach.

The berth allocation and quay crane assignment problem (BACAP) is a complex port operation planning problem susceptible to uncertainties, such as vessel arrival time fluctuation to its estimated time of arrival and maritime markets. For promoting reliability and sustainability of container terminals, this paper addresses the optimization of BACAP under the uncertain vessels’ arrival times and fluctuation of loading and unloading volumes. We propose a proactive BACAP strategy considering minimum recovery cost under uncertainty using a reactive strategy. A stochastic programming model is formulated to minimize the basic cost in the baseline schedule, and the recovery cost in real uncertain scenarios. A two-stage meta-heuristic framework based on GA is developed for solving this problem. Numerical experiments and scenario analysis are conducted to validate the effectiveness of the proposed model and the proposed solution approaches.

In this article, we investigate the vehicle assignment problem with demand uncertainty in a hybrid hub-and-spoke network with a single hub. The problem is deciding both the transportation routes and the number and types of vehicles to be deployed to minimize the sum of costs to transport all quantities in a hybrid hub-and-spoke network which allows direct transportation between spokes. Daily changes in quantities are reflected with a finite number of scenarios. Regularly scheduled vehicles and temporarily scheduled vehicles are considered to meet the demand variation. We propose a Dantzig–Wolfe decomposition approach which yields a strong LP relaxation bound by introducing a set of feasible direct route patterns. We develop an algorithm which incorporates a column generation procedure at the root node and repeats iteratively a variable fixing and column generation procedure at the non-root nodes until an integral solution is found. Finally, we present computational results using the well-known CAB data sets and real-life data from the Korea Post. The results show that our algorithm can find near optimal solutions very efficiently.

A two-phase approach was adopted to solve the problem given during the ROADEF/EURO Challenge 2014 competition. The problem focuses on rolling stock management at railway sites, as defined by French Railways (SNCF). In the first phase, a train assignment problem is solved by combining a greedy heuristic procedure with integer programming. The objective is to maximize the number of assigned departures while meeting technical constraints. The second phase consists of scheduling train movements inside the station while minimizing the number of cancelled (uncovered) arrivals and departures. This schedule has to comply with resource constraints such as capacity, length, order of trains, etc. A constructive heuristic is used to build a feasible schedule, which is subject to improvement by an iterative procedure based on a local search. Experiment results, that demonstrate the effectiveness of our approach on the large scale instances provided by SNCF, are presented hereafter.

We consider a bilevel extension of the classical linear assignment problem motivated by network interdiction applications. Specifically, given a bipartite graph with two different (namely, the leader’s and the follower’s) edge costs, the follower solves a linear assignment problem maximizing his/her own profit, whereas the leader is allowed to affect the follower’s decisions by eliminating some of the vertices from the graph. The leader’s objective is to minimize the total cost given by the cost of the interdiction actions plus the cost of the assignments made by the follower. The considered problem is strongly $${ NP}$$ -hard. First, we formulate this problem as a linear mixed integer program (MIP), which can be solved by commercial MIP solvers. More importantly, we also describe a greedy-based construction heuristic, which provides (under some mild conditions) an optimal solution for the case, where the leader’s and the follower’s edge costs are equal to one. Finally, we present the results of our computational experiments comparing the proposed heuristic against an MIP solver.

Semidefinite optimization is a strong tool in the study of NP-hard combinatorial optimization problems. On the one hand, semidefinite optimization problems are in principle solvable in polynomial time (with fixed precision), on the other hand, their modeling power allows to naturally handle quadratic constraints. Contrary to linear optimization with the efficiency of the Simplex method, the algorithmic treatment of semidefinite problems is much more subtle and also practically quite expensive. This survey-type article is meant as an introduction for a non-expert to this exciting area. The basic concepts are explained on a mostly intuitive level, and pointers to advanced topics are given. We provide a variety of semidefinite optimization models on a selection of graph optimization problems and give a flavour of their practical impact.

Population growth and the massive production of automotive vehicles have lead to the increase of traffic congestion problems. Traffic congestion today is not limited to large metropolitan areas, but is observed even in medium-sized cities and highways. Traffic engineering can contribute to lessen these problems. One possibility, explored in this paper, is to assign tolls to streets and roads, with the objective of inducing drivers to take alternative routes, and thus better distribute traffic across the road network. This assignment problem is often referred to as the tollbooth problem and it is NP-hard. In this paper, we propose mathematical formulations for two versions of the tollbooth problem that use piecewise-linear functions to approximate congestion cost. We also apply a biased random-key genetic algorithm on a set of real-world instances, analyzing solutions when computing shortest paths according to two different weight functions. Experimental results show that the proposed piecewise-linear functions approximate the original convex function quite well and that the biased random-key genetic algorithm produces high-quality solutions.

Evacuations are massive operations that create heavy travel demand on road networks some of which are experiencing major congestions even with regular traffic demand. Congestion in traffic networks during evacuations, can be eased either by supply or demand management actions. This study focuses on modeling demand management strategies of optimal departure time, optimal destination choice and optimal zone evacuation scheduling (also known as staggered evacuation) under a given fixed evacuation time assumption. The analytical models are developed for a system optimal dynamic traffic assignment problem, so that their characteristics can be studied to produce insights to be used for large-scale solution algorithms. While the first two strategies were represented in a linear programming (LP) model, evacuation zone scheduling problem inevitable included integers and resulted in a mixed integer LP (MILP) one. The dual of the LP produced an optimal assignment principle, and the nature of the MILP formulations revealed clues about more efficient heuristics. The discussed properties of the models are also supported via numerical results from a hypothetical network example.

This paper considers the component assignment problem (CAP) of finding the optimal assignment of n available components to n positions in a system such that the system reliability is maximized. To solve the CAP, an important type of problems in reliability, we propose a Birnbaum-importance based genetic local search (BIGLS) algorithm in which a local search using the Birnbaum importance is embedded into the genetic algorithm. This paper presents comprehensive numerical tests to compare the performance of the BIGLS with a general genetic algorithm and a Birnbaum-importance based two-stage heuristic. The testing results show that the BIGLS is robust (with respect to its random operations) and effective, and outperforms two benchmark methods in terms of solution quality. It demonstrates the effectiveness of embedding the Birnbaum importance in the local search under the genetic evolutionary mechanism.

In this paper, a multiobjective scatter search procedure for a bi-objective territory design problem is proposed. A territory design problem consists of partitioning a set of basic units into larger groups that are suitable with respect to some specific planning criteria. These groups must be compact, connected, and balanced with respect to the number of customers and sales volume. The bi-objective commercial territory design problem belongs to the class of NP-hard problems. Previous work showed that large instances of the problem addressed in this work are practically intractable even for the single-objective version. Therefore, the use of heuristic methods is the best alternative for obtaining approximate efficient solutions for relatively large instances. The proposed scatter search-based framework contains a diversification generation module based on a greedy randomized adaptive search procedure, an improvement module based on a relinked local search strategy, and a combination module based on a solution to an assignment problem.

We consider the bilevel road pricing problem. In contrary to the Karush-Kuhn-Tucker (one level) reformulation, the optimal value reformulation is globally and locally equivalent to the initial problem. Moreover, in the process of deriving optimality conditions, the optimal value reformulation helps to preserve some essential data involved in the traffic assignment problem that may disappear with the Karush-Kuhn-Tucker (KKT) one. Hence, we consider in this work the optimal value reformulation of the bilevel road pricing problem; using some recent developments in nonsmooth analysis, we derive implementable KKT type optimality conditions for the problem containing all the necessary information. The issue of estimating the (fixed) demand required for the road pricing problem is a quite difficult problem which has been also addressed in recent years using bilevel programming. We also show how the ideas used in designing KKT type optimality conditions for the road pricing problem can be applied to derive optimality conditions for the origin-destination (O-D) matrix estimation problem. Many other theoretical aspects of the bilevel road pricing and O-D matrix estimation problems are also studied in this paper.

The weakest link principle applies to many real-life situations where a system is as productive as its bottleneck. The purpose of this paper is to show how the efficiency of a manufacturing or service process (i.e., the strength of a chain) may be maximized by optimal allocation of resources to improve the performance of the bottleneck (i.e., strengthen the weakest link) in an uncertain environment. Specifically, we consider two different versions of the stochastic bottleneck assignment problem (SBAP), which is a variation of the classic assignment problem (AP), with respective goals of minimizing the expected longest processing time and maximizing the expected lowest production rate. It is proven that each of the two intrinsically difficult SBAPs is reducible to an efficiently solvable AP provided that the processing times or the production rates are independent random variables following some families of probability distributions.

I consider the problem of weekly assignment of shifts to operators. The shifts are to be assigned by seniority (or by any other employee hierarchy), but every employee is guaranteed to receive at least one shift. I propose a practical solution method to this problem that guarantees a feasible solution. As an application, the solution method is applied to the data provided in the literature on weekly shift assignment of the operators of the New Brunswick Telephone company. The solution method is also applied to 100 randomly generated problems. The results show that the solution method produces close-to-optimal solutions.

Recently, crossdocking techniques have been successfully applied in responsive supply chain management. However, most researches focused on physical layout of a crossdock, or scheduling operations within a crossdock. In this paper, we study a multi-crossdock transshipment service problem with both soft and hard time windows. The flows from suppliers to customers via the crossdocks are constrained by fixed transportation schedules. Cargos can be delayed and consolidated in crossdocks, and both suppliers and customers have specific hard time windows. In addition to hard time windows, customers also have less-restrictive time windows, called soft time windows. The problem to minimize the total cost of the multi-crossdock distribution network, including transportation cost, inventory handling cost and penalty cost, can be proved to be NP-hard in the strong sense and hence efficient heuristics are desired. We propose two types of meta-heuristic algorithms, called Adaptive Tabu Search and Adaptive Genetic Algorithm, respectively, to solve the problem efficiently. We conduct extensive experiments and the results show that both of them outperform CPLEX solver and provide fairly good solutions within realistic timescales. We also perform sensitivity analysis and obtain a number of managerial insights.

The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP.We describe improvements of a LAP-algorithm for the rectangular problem, in general and slightly adapted for these variants, based on the structure of the corresponding cost matrices. For these problem instances, we compared the best special codes from literature to our codes, which are more general and easier to implement. The improvements lead to more efficient and robust codes, making them competitive on all problem instances and often showing much shorter computing times.

We consider some variant models, having changeover cost, of the assignment problem. In these models, multiple assignments to an operator are allowed. In addition to assignment costs, a changeover cost is incurred if an operator does one job after another is completed. Two different types of changeover costs and related two models are considered. Mathematical programming formulations are given for the models. When changeover costs are dependent on the operator but independent of the jobs and are non-negative, a linear programming model is obtained. For the case when changeover costs are dependent on the jobs, a linear integer programming formulation is obtained. We also show that, this problem is strongly NP-hard. A heuristic solution method is suggested for it. Numerical findings on the performance of the method are given.

Two metaheuristic methods based on Tabu search are introduced to assign judges to individual competitions in a tournament. The complexity of the mathematical formulation accounting for the assignment rules, leads us to use such an approach. The first metaheuristic includes two different Tabu searches that are combined with a diversification strategy. The second metaheuristic is applied to a penalized version of the original model formulated as an assignment problem. This metaheuristic is also based on a Tabu search procedure including a diversification strategy driven by the constraints violated. Numerical results are provided to indicate the efficiency of the methods to generate very good solutions.

The Multi-Story Space Assignment Problem (MSAP) is an innovative formulation of the multi-story facility assignment problem that allows one to model the location of departments of unequal size within multi-story facilities as a Generalized Quadratic 3-dimensional Assignment Problem (GQ3AP). Not only can the MSAP generate the design of the location of the departments in the facility, the MSAP also includes the evacuation planning for the facility. The formulation, background mathematical development, and computational experience with a branch and bound algorithm for the MSAP are also presented.

Within the area of short term airline operational planning, Tail Assignment is the problem of assigning flight legs to individual identified aircraft while satisfying all operational constraints, and optimizing some objective function. In this article, we propose that Tail Assignment should be solved as part of both the short and the long term airline planning. We further present a hybrid column generation and constraint programming solution approach. This approach can be used to quickly produce solutions for operations management, and also to produce close-to-optimal solutions for long and mid term planning scenarios. We present computational results which illustrate the practical usefulness of the approach.

The considered assignment problem generalizes its classical counterpart by the existence of some incompatibility constraints limiting the assignment of tasks to processing units within groups of mutually exclusive tasks. The groups are defined for each processing unit and the constraints allow at most one task from each group to be assigned to the corresponding processing unit. The processing units can normally process a certain number of tasks without any cost; this capacity can be extended, however, at some extra marginal cost that is non-decreasing with the number of additional tasks. Each task has to be assigned to exactly one processing unit and has some preference for the assignment; it is expressed for each pair ‘task-processing unit’ by a dissatisfaction degree. The quality of feasible assignments is evaluated by three criteria: g1-the maximum dissatisfaction of tasks, g2-the total dissatisfaction of tasks, g3-the total cost of processing units. If there is no feasible assignment, tasks and processing units creating a blocking configuration are identified and all actions of unblocking are proposed. Formal properties of blocking configurations and unblocking actions are proven, and an interactive procedure for exploring the set of non-dominated assignments is described together with illustrative examples processed by special software.

The data association problem consists of associating pieces of information emanating from different sources in order to obtain a better description of the situation under study. This problem arises, in particular, when, considering several sensors, we aim at associating the measures corresponding to a same target. This problem, widely studied in the literature, is often stated as a multidimensional assignment problem where a state criterion is optimized. While this approach seems satisfactory in simple situations where the risk of confusing targets is relatively low, it is much more difficult to get a correct description in denser situations. This is why, we propose, for the first time to our knowledge, to address this problem in a multiple criteria framework using a second complementary criterion, based on the identification of the targets. Due to the specificities of the problem, simple and efficient approaches can be used to generate non-dominated solutions. Moreover, we show that the accuracy of the proposed solutions is greatly increased when considering a second criterion. A bi-criteria interactive procedure is also introduced to assist an operator in solving conflicting situations.

We apply Algorithm Robust to various problems in multiple objective discrete optimization. Algorithm Robust is a general procedure that is designed to solve bicriteria optimization problems. The algorithm performs a weight space search in which the weights are utilized in min-max type subproblems. In this paper, we experiment with Algorithm Robust on the bicriteria knapsack problem, the bicriteria assignment problem, and the bicriteria minimum cost network flow problem. We look at a heuristic variation that is based on controlling the weight space search and has an indirect control on the sample of efficient solutions generated. We then study another heuristic variation which generates samples of the efficient set with quality guarantees. We report results of computational experiments.

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.

In previous work the authors consider the dynamic assignment problem, which involves solving sequences of assignment problems over time in the presence of uncertain information about the future. The algorithm proposed by the authors provides generally high-quality but non-optimal solutions. In this work, though, the authors prove that if the optimal solution to a dynamic assignment problem in one of two problem classes is unique, then the optimal solution is a fixed point under the algorithm.

The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for European airline companies, complex constraints defining the feasibility of a line of work have to be respected. We developed two different algorithms to tackle the large scale optimization problem of Airline Crew Assignment. The first is an application of the Constraint Programming (CP) based Column Generation Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from Constraint Programming and Operations Research. Numerical results show the superiority of the hybrid algorithm in comparison to CP based tree search and column generation alone.

This paper presents a surrogate constraint tabu thresholding (SCTT) implementationfor solving the frequency assignment problem. The frequency assignment problem is animportant combinatorial optimisation problem that arises in telecommunications. The mainobjective is to assign radio frequencies to a number of communication links such that interferenceis minimised. Interference is minimised by satisfying a number of problem specificconstraints. The surrogate constraint is created by taking a weighted sum of the constraintsnot satisfied. SCTT is compared with a tabu thresholding method from the literature on a setof simulated but realistic test problems with respect to quality of the solution in a given timeperiod. Computational results show that SCTT is more efficient and effective for all the testproblems.

The Best‐First Search strategy (BeFS) and the Depth‐First Search strategy (DFS) areregarded as the prime strategies when solving combinatorial optimization problems by parallelBranch‐and‐Bound (B&B) ‐ BeFS because of efficiency with respect to the number of nodesexplored, and DFS for reasons of space efficiency.

The purpose of this study is to develop an efficient heuristic for the process selection and part cell assignment problem. The study assumes a production environment where each part has several process plans, each manifested by a required set of tools. These tools can be assigned to different machines based on a tool-machine compatibility matrix. An additional assumption is that all relevant data such as periodic demand, processing time, processing cost, tool magazine capacity, tool changing time, tool life and tool cost are fixed and known. A mixed integer linear program which takes all relevant data into account is developed to minimize the production cost. The suggested solution approach to solve this model makes use of Genetic Algorithms: a class of heuristic search and optimization techniques that imitate the natural selection and evolutionary process. First, the encoding of the solutions into integer strings is presented, as well as the genetic operators used by the algorithm. Next, the efficiency and robustness of the solution procedure is demonstrated through several different examples.

The combined distribution and assignment problem is the problem of the simultaneousdetermination of the distribution of trips between origins and destinations in a transportationnetwork and the assignment of trips to routes in each origin - destination pair. In the modelmost widely used, the distribution is assumed to follow a gravity model with a negativeexponential deterrence function and the assignment is made according to the deterministicuser equilibrium principle. In this paper, we describe an extension of this model in whichthe allocation of trips to routes is made according to the principle of stochastic user equilibrium.We discuss the behavioural foundations of trip assignment and combined modelsassuming deterministic or stochastic route choice. In particular, we describe how they can bederived using the efficiency principle from discrete choice theory; the combined distributionand stochastic assignment model is obtained as the continuous approximation of the discreteproblem of finding the most probable flow pattern under the assumption of efficient tripmaking behaviour. We outline an algorithm for the solution of the model which is based onroute (column) generation, disaggregate simplicial decomposition, and partial linearization.

An Augmented Makespan Assignment Problem (AMAP), which is a variation of theGeneralised Assignment Problem (GAP), is analysed in this paper. In this problem, weminimise the makespan for producing several products with each on one of several machines.The data instances are such that some of the available machines are identical, which in turnleads to mixed integer programming problems that have many optimal integer solutions.Most commercial software for mathematical programming therefore has problems provingthat the solution they find is an optimal one. Even optimisation software that does someinteger preprocessing on the system of linear relations has problems in solving a straightforwardformulation of the model. Darby-Dowman et al. investigated this model and foundit difficult to solve as an IP. We show that if more of the model structure is highlighted at themodelling stage, and these are exploited in preprocessing the formulation before the problemmatrix is produced, then we get easily solvable integer programs for the data instances underconsideration. We give computational results for five different commercial codes with andwithout our preprocessing at the modelling stage.

The assignment of M unique machines to M locations with the objective of minimizing the total machine-to-machine material transportation cost in a flow line may be formulated as a quadratic assignment problem (QAP). Instead of having M unique machines, if an application involves one or more sets of identical machines, the location problem becomes a tertiary assignment problem (TAP). Solving a large problem of this kind is extremely difficult because of its combinatorial nature. When machine-to-machine flow is fixed, the TAP may be specialized to a QAP for which the unique machine problem is a special case. Obtaining an optimum solution to this problem when M is large is also computationally intractable. However, this problem may be solved by identifying sets of identical machines which may be partitioned into individual, "unique" machines. Properties of a special type of matrix called the amoebic matrix are used in the partitioned problems to provide approximate solutions, which are relabeled to prescribe a solution to the original problem. Results are demonstrated along with suggestions for further research.

A static deterministic single machine scheduling problem with a common due window is considered. Job processing times are controllable to the extent that they can be reduced, up to a certain limit, at a cost proportional to the reduction. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, its size, processing time reduction as well as job earliness and tardiness. We show that the problem can be formulated as an assignment problem and thus can be solved with well-known algorithms.

This paper presents the application of a tabu search algorithm for solving the frequency assignment problem. This problem, known to be NP-hard, is to find an assignment of frequencies for a number of communication links, which satisfy various constraints. We report on our computational experiments in terms of computational efficiency and quality of the solutions obtained for realistic, computer-generated problem instances. The method is efficient, robust and stable and gives solutions which compare more favourably than ones obtained using a genetic algorithm.

Suppose that a road network model is given, together with some given demand for travel by (say) car and that the demand for travel varies with time of day but not from day to day. Suppose that this demand is given in the form of specified total outflow rates from each origin headed towards each destination, for each origin-destination pair and for each time of day, and that some initial time-dependent routeinflow rates, meeting the given demand, are given. Finally, suppose that within-day time is represented by a continuous variable. This paper specifies a natural smooth day-to-day route-swapping procedure wherein drivers swap toward less expensive routes as day succeeds day, and shows that under reasonable conditions there is an equilibrium state of this dynamical system. If such a collection of route-inflows has arisen today, say, then there is no incentive for any route-inflow to change tomorrow, in the sense that at each moment of today each of today's route-inflows isalready on a route which today yielded the smallest travel cost. Such a set of “no-incentive-to-change” route-inflows is called adynamic equilibrium, or adynamic user-equilibrium, and may be regarded as a solution of the dynamic equilibrium traffic assignment problem. Thus, the paper introduces a smooth day-to-day dynamic assignment model and, using this model, shows that there is a dynamic user-equilibrium in a continuous time setting. The paper briefly considers the day-to-day stability of the route-swapping process, also in a continuous setting. Finally, the paper gives a simple dynamical example illustrating the stability of the route-swapping process in a simple two-route network when there is deterministic queueing at bottlenecks.

Research on how to model the dynamic behaviour of traffic flows efficiently and the development of algorithms to handle such models numerically has become a key activity in recent years as a consequence of the emerging applications of advanced technologies to transport. This paper offers a critical review of some of the most relevant formulations of the dynamic assignment problem and algorithms arising from both discrete and continuous models, emphasizing the underlying modelling hypothesis. Comments are made on the crucial underlying discussion on the basic implicit or explicit hypothesis and extensions to Wardrop's principle and the corresponding equilibrium concept. Properties and shortcomings are described and commented on and in some cases illustrated with simple examples. The paper ends with a description of a recent continuous modelling proposal that seems to overcome one of the reported major shortcomings: the FIFO discipline observance of traffic flows. A set of concluding remarks and a comprehensive bibliography close the paper.

Latin hypercube sampling is often used to estimate the distribution function of a complicated function of many random variables. In so doing, it is typically necessary to choose a permutation matrix which minimizes the correlation among the cells in the hypercube layout. This problem can be formulated as a generalized, multi-dimensional assignment problem. For the two-dimensional case, we provide a polynomial algorithm. For higher dimensions, we offer effective heuristic and bounding procedures.

We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.

The Generalized Assignment Problem, in the class of NP-hard problems, occurs in a wide range of applications — vehicle packing, computers, and logistics, to name only a few. Previous research has been concentrated on optimization methodologies for the GAP. Because the Generalized Assignment Problem is NP-hard, optimization methods tend to require larger computation times for large-scale problems. This paper presents a new heuristic,Variable-Depth-Search Heuristic (VDSH). We show that on the sets of large test problems, the quality of the solution found by VDSH exceeds that of the leading heuristic by an average of over twenty percent, while maintaining acceptable solution times. On difficult problem instances, VDSH provides solutions having costs 140% less than those found by the leading heuristic. A duality gap analysis of VDSH demonstrates the robustness of our heuristics.

We describe an implementation of tabu search that solves the path assignment problem, which is the problem of routing video data through an undercapacitated telecommunications network. Two versions of the tabu search were studied. Our results compare very favourably with those from other methods.

A transit equilibrium assignment problem assigns the passenger flows on to a congested transit (public transportation) network with asymmetric cost functions and a fixed origin-destination matrix. This problem which may be formulated in the space of hyperpath flows, is transformed into an equivalent problem in the space of total arc flows and an auxiliary variable. A simplicial decomposition algorithm is developed and its convergence is proved under the usual assumptions on the cost functions. The algorithm requires relatively little memory and its efficiency is demonstrated with computational results.

The plant layout problem is usually formulated as a quadratic assignment problem (QAP). In this paper, we incorporate the throughput related aspects of the automated manufacturing system into the layout problem. We modify the QAP formulation by explicitly considering the throughput requirements of automated manufacturing systems. Our formulation also incorporates the cost of keeping a certain number of pallet-fixtures in the system. The resulting modified quadratice assignment problem (MQAP) is presented. An optimal solution method for MQAP is developed and its computational performance is evaluated.

The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasiassignment problem. The algorithm is a variation of the primal-dual algorithm, and its computational complexity isO(n3).

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.

In this paper we discuss the shortest augmenting path method for solving assignment problems in the following respect: we introduce this basic concept using matching theory we present several efficient labeling techniques for constructing shortest augmenting paths we show the relationship of this approach to several classical assignment algorithms we present extensive computational experience for complete problems, and we show how postoptimal analysis can be performed using this approach and naturally leads to a new, highly efficient hybrid approach for solving large-scale dense assignment problems