Search

SML is a modeling language for the structured modeling framework, which represents the semantics as well as the mathematical structure of a model. This paper uses an SML approach to improve the object based universal relation data model. By this approach, both the relational structure of a database and the objects in relations are automatically derived by the associated SML schema. The interpretation part of an SML schema allows users to easily learn the meanings of the data before performing universal relation queries; the queries are then computed by using the automatically derived objects. With a goal of making queries simpler, this paper presents theories, table naming conventions, a confirmation approach, and a unified example illustrating many different concepts. It helps lay the foundation for the eventual development of a remarkably easy user interface for ad hoc query in computer-based modeling systems. We are hopeful that the results may in the future contribute to real applications in databases as well as in management science/operations research. [ABSTRACT FROM AUTHOR]

In this paper, we address the non-permutation flowshop scheduling problem with minimal and maximal time lags between successive operations of each job. For this problem, the set of permutation schedules is not a dominant set but not all non-permutation schedules are feasible because they are not always able to satisfy all time lag constraints. We present a theoretical study, limited to the two-machine case, and related to the change on one machine of the order of two successive jobs of a permutation schedule. This study gives first the necessary conditions to make such move with regard to the feasibility of the schedule; secondly the necessary conditions to make such move interesting with regard to either the makespan or the number of tardy jobs. Through this analysis, we obtain new properties of dominance of permutation schedules. The results of the study are incorporated into a heuristic algorithm which starts the search with optimal permutation schedules and tries to improve them so as to obtain better non-permutation schedules. We also propose a mixed integer linear programming model. The objective function is to minimize lexicographically the number of tardy jobs as primary criterion and the makespan as secondary one. Computational experiments are performed to compare permutation with non-permutation schedules. [ABSTRACT FROM AUTHOR]

In this paper, we investigate new lower bounds for the P| r j, q j| Cmax scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP -hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones. [ABSTRACT FROM AUTHOR]

The employee tour scheduling problem involves the determination of both work hours of the day and workdays of the week for each employee. This problem has proven difficult to solve optimally due to its large size and pure integer nature. During the last decade, numerous approaches for modeling and solving this problem have been proposed. In this paper, employee tour scheduling literature published since 1990 is reviewed and classified. Solution techniques are classified into ten categories: (1) manual solution, (2) integer programming, (3) implicit modeling, (4) decomposition, (5) goal programming, (6) working set generation, (7) LP-based solution, (8) construction and improvement, (9) metaheuristics, and (10) other methods. The objective is to identify broad classifications, present typical mathematical models, compare the different methods, and identify future research directions. [ABSTRACT FROM AUTHOR]

The extensions, new developments and new interpretations for DEA covered in this paper include: (1) new measures of efficiency, (2) new models and (3) new ways of implementing established models with new results and interpretations presented that include treatments of ‘congestion’, ‘returns-to-scale’ and ‘mix’ and ‘technical’ inefficiencies and measures of efficiency that can be used to reflect all pertinent properties. Previously used models, such as those used to identify ‘allocative inefficiencies’, are extended by means of ‘assurance region’ approaches which are less demanding in their information requirements and underlying assumptions. New opportunities for research are identified in each section of this chapter. Sources of further developments and possible sources for further help are also suggested with references supplied to other papers that appear in this volume and which are summarily described in this introductory chapter. [ABSTRACT FROM AUTHOR]

In this paper, we consider a multi-stage multi-product production, inventory and transportation system and develop a mathematical model for a pull type ordering system based on the concept of a Just-In-Time (JIT) production system. Our model considers a manufacturing system in which the setup action is improved and can deal with the number of setups required. We also propose two approximate solution procedures to rapidly obtain a suboptimal solution of the formulated integer programming problem using a mathematical programming modeling language. The approximate procedures are realized utilizing post-optimal analysis which can be performed by the modeling language. Finally, we show a numerical example of the model applied to an actual manufacturing system of an automobile parts manufacturer in order to verify the effectiveness of the approximate procedures and to clarify the applicability of our modeling approach. [ABSTRACT FROM AUTHOR]

Time-staged mathematical programming models have a planning horizon that is divided into a sequence of consecutive time periods. For the modeling of this sequence of lime periods the use of calendars is proposed as an additional set concept for mathematical programming modeling languages. The definition of calendars is based on familiar notions such as set. ordering, interval length and functions. A calendar is an interval set and can be used to verify automatically the proper time referencing in stock balances. When a calendar is also a difference set, then backward and forward time referencing can be slated with the explicit use of lime units. For models with a rolling horizon, concise and flexible ways to specify the structure of calendars are presented. The aggregation of raw data into model parameter values is supported by linking calendars that represent different time scales. The influence of the proposed calendar concept on the human ability lo understand, maintain and verify models is analyzed throughout the paper on the basis of selected examples. [ABSTRACT FROM AUTHOR]

A Steiner tree problem on the plane is that of finding a minimum length Steiner tree connecting a given set K of terminals and lying within a given region R of the Euclidean plane; it includes as special cases the Euclidean Steiner minimal tree problem (ESMT), the rectilinear Steiner tree problem (RST), and the Steiner tree problem on graphs (STG). A Steiner hull for K in R generically refers to any subregion of R known to contain a Steiner tree. This paper gives a survey of the role of Steiner hulls in the Steiner tree problem. The significance of Steiner hulls in the efficient solution of Steiner tree problems is outlined, and then a compendium is given of the known Steiner hull constructions for ESMT, RST, and STG problems. [ABSTRACT FROM AUTHOR]

This paper presents a parallelization of the simplex method for linear programming. Current implementations of the simplex method on sequential computers are based on a triangular factorization of the inverse of the current basis. An alternative decomposition designed for parallel computation, called the quadrant interlocking factorization, has previously been proposed for solving linear systems of equations. This research presents the theoretical justification and algorithms required to implement this new factorization in a simplex-based linear programming system. [ABSTRACT FROM AUTHOR]

A multi-depot Chinese postman problem (MDCP) arises from a network (e.g. cityplan) in which several depots are located wherefrom edges (e.g. streets) have to be served. Since costs are involved with each visit to an edge, the objective is to find a minimum cost tour in the network that visits all edges of the network. Such a minimum cost tour consists of a collection of subtours such that the subtours originate from different depots, and each subtour starts and ends at the same depot. This typical OR problem turns into a multi decision maker problem if agents are assigned to the streets. In this new setting the cost of a minimum cost tour that visits all edges have to be paid by the agents. However, now each group of agents (coalition) has the opportunity to find its own minimum cost tour, i.e. a minimum cost tour that only visits the edges owned by the group of agents. Therefore, the main objective is to find allocations of the cost of a minimum tour that visits all agents in such a way that no coalition has higher costs than the costs incurred by its own minimum tour. We will use cooperative game theory to investigate whether these so-called core allocations exist. Therefore, we consider a cooperative Chinese postman (CP) game that is induced by an MDCP by associating every edge of the network with a different agent. In this paper, we characterize classes of networks that ensure the existence of core allocations, the so-called CP balanced graphs, and the existence of specific core allocations, the so-called CP submodular graphs. [ABSTRACT FROM AUTHOR]

In this paper, we address the optimal batch sizing and just-in-time scheduling problem where upper and lower bounds on the size of the batches are imposed. The objective is to find a feasible schedule that minimizes the sum of the weighted earliness and tardiness penalties as well as the setup costs, which involves the cost of creating a new batch. We present some structural properties of the optimal schedules and describe solving algorithms for the single machine problem. [ABSTRACT FROM AUTHOR]

The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now. [ABSTRACT FROM AUTHOR]

This paper presents a hybridization of a Constraint Programming (CP) model and search techniques with Local Search (LS) and some ideas borrowed from Genetic Algorithms (GA). The context is the physician rostering problem, whose instances can vary greatly and for which almost no general tool has been developed. It is hoped that the combination of the three techniques will lead to an algorithm that has sufficient flexibility to solve most instances with a small amount of customization. To achieve this goal we also introduce Generic constraints: these constraints are used to model several types of ergonomic constraints that are found amongst physician rostering problems. [ABSTRACT FROM AUTHOR]

This paper discusses the recent research on decomposition techniques in single-machine scheduling. A variety of orderings between adjacent and nonadjacent jobs in an optimal scheduling are presented. A list of decomposition rules is given that enable one to solve large size instances of six single-machine models. A partition technique is also developed to determine the optimal completion times of a general earliness-tardiness model for a given arrangement of jobs. [ABSTRACT FROM AUTHOR]

This paper is concerned with stochastic scheduling problems with several identical parallel machines, where the task durations and precedence constraints are stochastic. The stochastic precedence constraints are given by special GERT networks. At first, basic concepts and results are surveyed for GERT networks and for single-machine and parallel-machine scheduling with GERT network precedence constraints. An example shows where GERT scheduling problems occur in practice. After that, two types of heuristics for identical parallel-machine GERT scheduling problems with objective functions E(Cmax), max E(C), and E(∑C) are proposed: generalizations of algorithms for corresponding deterministic scheduling problems and so-called priority-rule methods. An empirical analysis shows the best heuristics for each of the objective functions considered. [ABSTRACT FROM AUTHOR]

This paper presents several branch and bound algorithms for a single-machine scheduling problem with batching. Jobs are partitioned into families, and a set-up time is necessary when there is a switch from processing jobs of one family to jobs of another family. The objective is to minimize the total weighted completion time. A lower bound based on Lagrangian relaxation of the machine capacity constraint is derived. Also, a multiplier adjustment method to find values of the multipliers is proposed. Computational experience with instances having up to 50 jobs shows that the lower bounds are effective in restricting the search. [ABSTRACT FROM AUTHOR]

In this paper we propose a genetic algorithm for discriminant analysis. The genetic fitness function uses duality principles of mathematical programming to solve the linear discriminant problem. The genetic method performed well in empirical testing and also provides the reasoning power behind the mathematical programming models. [ABSTRACT FROM AUTHOR]

This paper provides a survey of model management literature within the mathematical modeling domain. The first part of the survey is a review and a summary of the literature. After giving some basic definitions of modeling, modeling life cycle, and model management, two representative algebraic modeling languages followed by three approaches to modeling are introduced. These approaches are database, graph-based, and knowledge-based. The discussion is followed by a review of two specialized model management systems. The second part of the survey is a categorization of various modeling systems based on the modeling functions they provide and some of their features. These functions include life cycle support and model base administration. The degree of model independence provided by model management systems and the implemented environment systems is also summarized. The last part of the paper provides directions for future research. [ABSTRACT FROM AUTHOR]

Uncertainty in the parameters of a mathematical program may present a modeller with considerable difficulties. Most approaches in the stochastic programming literature place an apparent heavy data and computational burden on the user and as such are often intractable. Moreover, the models themselves are difficult to understand. This probably explains why one seldom sees a fundamentally stochastic model being solved using stochastic programming techniques. Instead, it is common practice to solve a deterministic model with different assumed scenarios for the random coefficient. In this paper we present a simple approach to solving a stochastic model, based on a particular method for combining such scenario solutions into a single, feasible policy. The approach is computationally simple and easy to understand. Because of its generality, it can handle multiple competing objectives, complex stochastic constraints and may be applied in contexts other than optimization. To illustrate our model, we consider two distinct, important applications: the optimal management of a hydro-thermal generating system and an application taken from portfolio optimization. [ABSTRACT FROM AUTHOR]

This paper describes a system, LPFORM, that enables users to design linear programming models interactively, using graphics. An output of the system is an algebraic statement of the model and data references that are subsequently used to generate the input for a solver in the standard MPS format. The emphasis of this paper is on the types of knowledge one has on the submodels that make up larger models and how this knowledge can be organized. [ABSTRACT FROM AUTHOR]

We present the problem of locating vehicle depots in an intercity freight transportation system with the objective of satisfying client demand for empty vehicles, while minimizing depot opening and operating costs, bidirectional client-depot transportation costs, as well as the costs of the interdepot movements necessary to counter the unbalancing of demand. We propose a class of models which has the form of a two-echelon multimode multicommodity location formulation with interdepot balancing requirements. We analyse the models and their properties to determine their underlying structure and characteristics to be used m subsequent algorithmic developments. [ABSTRACT FROM AUTHOR]

In order to solve a quadratic 0/1 problem, some techniques, consisting in deriving a linear integer formulation, are used. Those techniques, called “linearization”, usually involve a huge number of additional variables. As a consequence, the exact resolution of the linear model is, in general, very difficult. Our aim, in this paper, is to propose “economical” linear models. Starting from an existing linearization (typically the so-called “classical linearization”), we find a new linearization with fewer variables. The resulting model is called “Miniaturized” linearization. Based on this approach, we propose a new linearization scheme for which numerical tests have been performed. [ABSTRACT FROM AUTHOR]

Any sequence of legal moves leads the Towers of Hanoi puzzle to an arrangement from which the final configuration must be built up. A recursive algorithm which finishes off the puzzle is considered and, assuming a uniform distribution on the possible unfinished situations, the density function of the number of moves it takes is derived. [ABSTRACT FROM AUTHOR]

This chapter provides the formulations for the basic DEA models and the editors' introduction to the chapters which follow. [ABSTRACT FROM AUTHOR]

We study some mathematical programming formulations for the origin-destination model in airline revenue management. In particular, we focus on the traditional probabilistic model proposed in the literature. The approach we study consists of solving a sequence of two-stage stochastic programs with simple recourse, which can be viewed as an approximation to a multi-stage stochastic programming formulation to the seat allocation problem. Our theoretical results show that the proposed approximation is robust, in the sense that solving more successive two-stage programs can never worsen the expected revenue obtained with the corresponding allocation policy. Although intuitive, such a property is known not to hold for the traditional deterministic linear programming model found in the literature. We also show that this property does not hold for some bid-price policies. In addition, we propose a heuristic method to choose the re-solving points, rather than re-solving at equally-spaced times as customary. Numerical results are presented to illustrate the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

To improve the productivities of an automated container terminal, it is important to schedule different types of handling equipment in an integrated way. A mixed-integer programming model, which considers various constraints related to the integrated operations between different types of handling equipment, is formulated. A heuristic algorithm, called multi-layer genetic algorithm (MLGA) is developed with a view to overcome the computation difficulty for solving the mathematical model. A numerical experimentation is carried out in order to evaluate the performance of the algorithm. [ABSTRACT FROM AUTHOR]

We adopt the hierarchical communications model of (Bampis, Giroudeau, and König, 2000) and we present an approximation algorithm for the precedence constrained multiprocessor scheduling problem in the presence of small hierarchical communication delays (Chrétienne and Colin, 1991). Our algorithm is based on linear programming and rounding and has a performance guarantee of 12(Φ+1)/(12Φ+1) where Φ≥1 is the ratio of the smallest processing time of the tasks and of the maximum intercluster communication delay. This result generalizes the result of (Bampis, Giroudeau, and König, 2000) for the problem with unit execution times and unit intercluster communication delays. [ABSTRACT FROM AUTHOR]

When an organization solves a portfolio problem with public projects evaluated by multiple criteria, in which the economic dimension is not essential or not well characterized, the classical methods are not useful. We propose a non-linear preference model developed from normative Value Theory and using fuzzy sets to model some sources of imprecision. This model can be considered as a generalization of the classical approaches. However, the optimization problem is very complex in order to be solved with non-linear programming techniques. Therefore, the model is exploited by an evolutionary algorithm, able to achieve a strong improvement of the quality of solution. [ABSTRACT FROM AUTHOR]

The generic hoist scheduling problem is NP-hard and arises from automated manufacturing lines. In recent work using the constraint logic programming (CLP) formalism, a unified model has been developed with the problem description and solution method separated. We provide an improved model and new preprocessing stages where, as before, solutions and proof of optimality are provided by a hybrid CLP-MIP algorithm. The new algorithm is more scalable and robust. We give empirical results for a range of problem classes on benchmark problems from several sources. [ABSTRACT FROM AUTHOR]

We apply to fixed charge network flow (FCNF) problems a general hybrid solution method that combines constraint programming and linear programming. FCNF problems test the hybrid approach on problems that are already rather well suited for a classical 0-1 model. They are solved by means of a global constraint that generates specialized constraint propagation algorithms and a projected relaxation that can be rapidly solved as a minimum cost network flow problem. The hybrid approach ran about twice as fast as a commercial mixed integer programming code on fixed charge transportation problems with its advantage increasing with problem size. For general fixed charge transshipment problems, however, it has no effect because the implemented propagation methods are weak. [ABSTRACT FROM AUTHOR]

The development of mathematical programming algorithms and heuristics has traditionally been hampered by the separation of modeller and optimiser. Developers either have to sacrifice performance by switching between a modeller and optimiser and communicating through cumbersome matrix files; or they can work solely with the in-core matrix in the optimiser, where knowledge about the structured algebraic model is missing and thus difficult to exploit. We present EMOSL, a new combined modelling and optimisation subroutine library that overcomes these drawbacks. It allows the problem to be manipulated using the notation of the model language, which is of course close to the algebraic formulation of the problem. Access is provided directly to the in-core matrix of the optimiser, eliminating the need to communicate via files. Thus the scope and ease of algorithm development is greatly improved, without any degradation of performance. We substantiate these claims by describing four applications: a block structure extraction tool, and the implementations of three MIP heuristics and cutting planes techniques. [ABSTRACT FROM AUTHOR]

Preference for a set of alternatives evaluated under multiple criteria is frequently expressed in the form of pairwise comparisons. We propose a linear goal programming model for deriving the partial and overall preference values of the alternatives directly from pairwise comparisons. This model can be a useful alternative to AHP. The partial values represent the contribution of the criteria to the overall preference. Simulation experiments, which are conducted to compare the performance of the model with that of two other existing models, show that the model has good performance. [ABSTRACT FROM AUTHOR]

Although there have been several journal articles on the classificatory performance of mathematical programming approaches to the two-group discriminant problem, there has been no simulation study on the classificatory performance of mathematical programming approaches to the multiple-group problem reported in the literature. This study reports the results of a simulation experiment on the classificatory performance of a single-function and a multiple-function mathematical programming model relative to that of the standard parametric procedures for the three-group problem with small training samples. The effect of second-order terms on the classificatory performance of the mathematical programming models for the three-group problem is also investigated. Furthermore, this study theoretically examines the range of parameter values of a multiple-function mathematical programming model for which its number of misclassifications in the training sample cannot exceed that of a single-function model. [ABSTRACT FROM AUTHOR]

DEA (Data Envelopment Analysis) models and concepts are formulated here in terms of the ‘P-Models’ of Chance Constrained Programming, which are then modified to contact the ‘satisficing concepts’ of H.A. Simon. Satisficing is thereby added as a third category to the efficiency/inefficiency dichotomies that have heretofore prevailed in DEA. Formulations include cases in which inputs and outputs are stochastic, as well as cases in which only the outputs are stochastic. Attention is also devoted to situations in which variations in inputs and outputs are related through a common random variable. Extensions include new developments in goal programming with deterministic equivalents for the corresponding satisficing models under chance constraints. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We present a simple, direct proof of Hwang's characterization of rectilinear Steiner minimal trees [3]: Let S be a set of at least five terminals in the plane. If no rectilinear Steiner minimal tree for S has a terminal of degree two or more, there is a tree in which at most one of the Steiner points does not lie on a straight line l, and the tree edges incident to the Steiner points on l appear on alternate sides. This theorem has been found useful in proving other results for rectilinear Steiner minimal trees. [ABSTRACT FROM AUTHOR]