A Zero-One Goal-Programming Algorithm Using Partitioning and Constraint Aggregation

This paper offers a new approach to the solution of zero-one goal-programming problems. The number of non-zero variables required to satisfy a constraint completely is used to identify the priority levels that can be completely achieved, and also determine redundant constraints and invariant decision-variables. The priority levels that are so identified form the basis for a subprogramme of completely achievable constraints. These constraints are aggregated to form a single constraint, and a set of necessary and sufficient conditions are developed to generate the optimal solution. The algorithm has been coded in Pascal and compared with the Lee and Morris algorithm. The virtual CPU time required to solve those problems tested was less than 10 per cent of that required by the Lee and Morris algorithm. The algorithm may also be useful in solving other types of zero-one formulations.     

Stochastic Programming Applied to Human Resource Planning

This paper shows how state space models for human resource planning may be extended from linear and goal-programming formulations to cover the case where manpower demands and available resources for future periods are not known with certainty. Under reasonable assumptions, the problem can be treated as a multi-period stochastic program with simple recourse. Normal and Beta probability distributions are fitted to the right hand sides, and the equivalent determinstic programme solved using convex separable programming. An application of this methodology to a military human resource planning problem is described. Solution times for the stochastic model compare favourably with those for a goal-programming model of the same human resource system.     

The multivariate non-homogeneous Markov manpower system in a departmental mobility framework

The present paper proposes a non-homogeneous multivariate Markov manpower system in the general category of mathematical human resource planning. More specifically, we suggest a model, which takes into account the divisions existing in an organization categorizing its employees into several groups (departments). In this context, it considers not only possible transitions within the departments (intra-department transitions), but also, transfers of personnel between departments (inter-department transitions). Additionally, the proposed modeling structure is accompanied by cost and stocks (personnel) objectives which are set and in the sequel could be achieved by controlling either the recruitment policy or the allocation policy of employees transferred to other departments (or both). We use a minmax fuzzy goal-programming approach, under different operating assumptions, in order to keep the operational cost below desired aspiration levels and reach desirable stock structures in the presence of system’s constraints and regulations. The paper concludes with a numerical illustration.     

Optimal Criterion Weights in Repetitive Multicriteria Decision-Making

In repetitive judgmental discrete decision-making with multiple criteria, the decision maker usually behaves as if there is a set of appropriate criterion weights such that the decisions chosen are based on the weighted sum of all the criteria. Many different procedures for estimating these implied criterion weights have been proposed. Most of these procedures emphasize the preference trade-off among the multiple criteria of the decision maker, and thus the criterion weights obtained are not directly related to the hit ratio of matching decisions. Based on past data, statistical discriminant analysis can be used to determine the implied criterion weights that would reflect the past decisions. The most interesting performance measure is the hit ratio. In this work, we use the integer linear goal-programming technique to determine optimal criterion weights which minimize the number of misclassification of decisions. The linear goal-programming formulation has m constraints and m + k + 1 variables, where m is the number of cases and k is the number of criteria. Empirical study is done by using two different procedures on the actual past admission data of an M.B.A. programme. The hit ratios of the different procedures are compared.     

On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints

The effectiveness of projection methods for solving systems of linear inequalities is investigated. It is shown that they often have a computational advantage over alternatives that have been proposed for solving the same problem and that this makes them successful in many real-world applications. This is supported by experimental evidence provided in this paper on problems of various sizes (up to tens of thousands of unknowns satisfying up to hundreds of thousands of constraints) and by a discussion of the demonstrated efficacy of projection methods in numerous scientific publications and commercial patents (dealing with problems that can have over a billion unknowns and a similar number of constraints).     

Two improved formulations for the minimum latency problem

In network problems, latency is associated with the metric used to evaluate the length of the path from a root vertex to each vertex in the network. In this work we are dealing with two applications or variations of the minimum latency problem known as the repairman problem and the deliveryman problem. We have developed two integer formulations for the minimum latency problem and compared them with other two formulations from the literature for the time-dependent traveling salesman problem. The present work highlights the similarities and differences between the different formulations. In addition, we discuss the convenience of including a set of constraints in order to reduce the computation time needed to reach the optimal solution. We have carried out extensive computational experimentation on asymmetrical instances, since they provide the characteristics of the deliveryman and repairman problems in a better way.     

Mathematical programming techniques in majorization

In this paper, we are concerned with mathematical programs which construct nonmajorizing vectors for several specific majorization applications. In particular, we develop a linear integer program and two integer goal programs which solve the assignment majorization problem. We also develop a quadratic program for solving majorization problems which arise in probability and statistics. In the appendix, we present a general goal-programming algorithm for these, as well as others, goal programs.The authors would like to thank Professor Y. Tong for introducing them to majorization and its applications. They would also like to thank Professors Y. Tong and D. Mesner for helpful discussions.     

An efficient method for nonlinearly constrained networks

Many nonlinear network flow problems (in addition to the balance constraints in the nodes and capacity constraints on the arc flows) have nonlinear side constraints, which specify a flow relationship between several of the arcs in the network flow model. The short-term hydrothermal coordination of electric power generation is an example of this type. In this work we solve this kind of problem using an approach in which the efficiency of the well-known techniques for network flow can be preserved. It lies in relaxing the side constraints in an augmented Lagrangian function, and minimizing a sequence of these functions subject only to the network constraints for different estimates of the Lagrange multipliers of the side constraints. This method gives rise to an algorithm, which combines first- and superlinear-order multiplier methods to estimate these multipliers. When the number of free variables is very high we can obtain a superlinear-order estimate by means of the limited memory BFGS method fitted to our problem. An extensive computational comparison with other methods has been performed. The numerical results reported indicate that the algorithm described may be employed advantageously to solve large-scale network flow problems with nonlinear side constraints.     

Multicriteria order acceptance decision support in over-demanded job shops: A neural network approach

Order acceptance is an important issue in job shop production systems where demand exceeds capacity. In this paper, a neural network approach is developed for order acceptance decision support in job shops with machine and manpower capacity constraints. First, the order acceptance decision problem is formulated as a sequential multiple criteria decision problem. Then a neural network based preference model for order prioritization is described. The neural network based preference model is trained using preferential data derived from pairwise comparisons of a number of representative orders. An order acceptance decision rule based on the preference model is proposed. Finally, a numerical example is discussed to illustrate the use of the proposed neural network approach. The proposed neural network approach is shown to be a viable method for multicriteria order acceptance decision support in over-demanded job shops.     

Scope of stationary multi-objective evolutionary optimization: a case study on a hydro-thermal power dispatch problem

Many engineering design and developmental activities finally resort to an optimization task which must be solved to get an efficient and often an intelligent solution. Due to various complexities involved with objective functions, constraints, and decision variables, optimization problems are often not adequately suitable to be solved using classical point-by-point methodologies. Evolutionary optimization procedures use a population of solutions and stochastic update operators in an iteration in a manner so as to constitute a flexible search procedure thereby demonstrating promise to such difficult and practical problem-solving tasks. In this paper, we illustrate the power of evolutionary optimization algorithms in handling different kinds of optimization tasks on a hydro-thermal power dispatch optimization problem: (i) dealing with non-linear, non-differentiable objectives and constraints, (ii) dealing with more than one objectives and constraints, (iii) dealing with uncertainties in decision variables and other problem parameters, and (iv) dealing with a large number (more than 1,000) variables. The results on the static power dispatch optimization problem are compared with that reported in an existing simulated annealing based optimization procedure on a 24-variable version of the problem and new solutions are found to dominate the solutions of the existing study. Importantly, solutions found by our approach are found to satisfy theoretical Kuhn–Tucker optimality conditions by using the subdifferentials to handle non-differentiable objectives. This systematic and detail study demonstrates that evolutionary optimization procedures are not only flexible and scalable to large-scale optimization problems, but are also potentially efficient in finding theoretical optimal solutions for difficult real-world optimization problems. Kalyanmoy Deb, Deva Raj Chair Professor. Currently a Finland Distinguished Professor, Department of Business Technology, Helsinki School of Economics, 00101 Helsinki, Finland.     

An integer optimization problem with mixed algebraic and number-theoretic constraints

Two problems dealing with theory of numbers are considered. First, an unusual integer optimization problem characterized by mixed algebraic and number-theoretic constraints is studied, which has application in the sharing of secrets or sensitive resources. Next, a linear difference algorithm is proposed for generating sequences of prime numbers with accelerated growth rate in the number of digits produced.     

Extensions of Stochastic Optimization Results to Problems with System Failure Probability Functions

We derive an implementable algorithm for solving nonlinear stochastic optimization problems with failure probability constraints using sample average approximations. The paper extends prior results dealing with a failure probability expressed by a single measure to the case of failure probability expressed in terms of multiple performance measures. We also present a new formula for the failure probability gradient. A numerical example addressing the optimal design of a reinforced concrete highway bridge illustrates the algorithm. This work was sponsored by the Research Associateship Program, National Research Council. The authors are grateful for the valuable insight from Professors Alexander Shapiro, Evarist Gine, and Jon A. Wellner. The authors also thank Professor Tito Homem-de-Mello for commenting on an early draft of this paper.     

A range-space implementation for large quadratic programs with small active sets

Large and sparse convex quadratic programming problems are often generated in the course of solving large-scale optimization problems. An important class of these problems has the property that only a small number of constraints are at their bounds at a solution. We describe an implementation of a range-space method designed for efficient solution of these small-active-set problems. The implementation is oriented toward the application area of multidimensional data fitting subject to constraints. Test results are presented for several data-fitting problems.The authors are indebted to the referees for several valuable contributions     

A Dynamic Programming Approach to Determine Optimal Manpower Recruitment Policies

The manpower planning models available in the literature have dealt with how changes take place in a manpower planning system, under various operating and policy constraints. However, none of these models has identified the manpower system costs. In this paper we have identified various manpower system costs. Further, we have developed a manpower planning model with the objective of minimizing the manpower system costs. The model has been found to be analogous to the Wagner-Whitin model in production/inventory management. A numerical example has been given to illustrate the model.     

Tactical Manpower Planning via Programming Under Uncertainty

This paper presents models for different types of manpower pooling policies. A multi-grade manpower system with mutually exclusive skills is considered. The work load imposed is a random variable characterized by the known joint distribution of the number of jobs to be performed and of the time to do a job. The basic models are developed as a tool for manpower planning in the jobbing workshops of an oil company. The resulting "two-stage programmes under uncertainty" are shown to reduce to mixed-integer linear programmes. The models are then generalized to permit their use in a larger class of manpower planning problems.     

Interior point methods 25 years later

Interior point methods for optimization have been around for more than 25 years now. Their presence has shaken up the field of optimization. Interior point methods for linear and (convex) quadratic programming display several features which make them particularly attractive for very large scale optimization. Among the most impressive of them are their low-degree polynomial worst-case complexity and an unrivalled ability to deliver optimal solutions in an almost constant number of iterations which depends very little, if at all, on the problem dimension. Interior point methods are competitive when dealing with small problems of dimensions below one million constraints and variables and are beyond competition when applied to large problems of dimensions going into millions of constraints and variables.In this survey we will discuss several issues related to interior point methods including the proof of the worst-case complexity result, the reasons for their amazingly fast practical convergence and the features responsible for their ability to solve very large problems. The ever-growing sizes of optimization problems impose new requirements on optimization methods and software. In the final part of this paper we will therefore address a redesign of interior point methods to allow them to work in a matrix-free regime and to make them well-suited to solving even larger problems.     

非线性约束优化问题的混合粒子群算法

把处理约束条件的一个外点方法和改进的粒子群优化算法相结合,提出了一种求解非线性约束优化问题的混合粒子群优化算法.该方法兼顾了粒子群优化和外点法的优点,对算法迭代过程中出现不可行粒子,利用外点法处理后产生可行粒子.数值实验表明了提出的新算法具有有效性、通用性和稳健性.     

Pressure of a circular stamp on a composite layer

The method of dual integral equations is used to obtain a solution to the problem of a rigid circular stamp pressing on an elastic composite layer, with a cylindrical surface separating the materials. A large number of papers have already been published, dealing with the mechanics of multilayered media in which the surfaces separating the layers from each other do not intersect the outer boundary (see references in /1/). The formulation and methods of solution of the fundamental boundary value problems can be found for such media in the monographs /2,3/.

Considerably less attention has been given to the study of the boundary value problems for composite media in which the surfaces separating the layers do intersect the outer boundary. The authors of /4, 5/ call such media the regions with transverse (vertical) layer folding. Out of the publications dealing with the methods of solving contact problems for transversely layered regions, attention should be drawn to /4–11/.     

Simultaneous Optimization in Process Quality Control via Prediction-interval Constrained Programming

A challenging problem in process control is the selection of input levels which will produce desirable output quality. This problem is complicated by the unsure relationships of cause and effect and by the trade-offs between meeting conflicting output specifications. This paper proposes a new approach, which incorporates prediction-interval constraints into a goal-programming model. A process-control problem, originally solved by the desirability-function approach, is solved using this new model. Comparisons between the two approaches are discussed.