Linear Programming on Microcomputers

The paper considers the problems involved in implementing linear programming software on microcomputers and the user requirements for packages on such machines.     

Programming Languages,Microcomputers and O.R.

The relationship between O.R. and computer programming is considered. The programming languages involved, and their respective roles, are reviewed. Criteria for assessing a programming language for O.R. are discussed, particularly in view of the increasing use of microcomputers within O.R.     

随机多目标规划区间交互过程及其应用

针对随机多目标规划问题中目标函数含有连续型随机变量的情形,设计一种基于概率有效性意义下的区间交互过程,将概率有效性与多目标问题理想点进行有机结合,有效辅助决策者寻求愿意承受的风险水平,并进行决策,简化了随机多目标优化问题。最后通过实例说明该交互过程的作用。     

Teaching topics in numerical linear algebra using spreadsheets

The argument is advanced that spreadsheet programs operating on microcomputers have a significant role to play in the teaching of numerical analysis. They offer a simple and direct means of programming numerical computations which is more powerful than a pocket calculator but quicker and more flexible than conventional high level language programming. In addition the spreadsheet concepts offers significant pedagogical advantages in the exploration of numerical methods. The argument is illustrated using some examples drawn from the field of numerical linear algebra.     

Checking weak optimality of the solution to linear programming with interval right-hand side

The interval linear programming (IvLP) is a method for decision making under uncertainty. A weak feasible solution to IvLP is called weakly optimal if it is optimal for some scenario of the IvLP. One of the basic and difficult tasks in IvLP is to check whether a given point is weak optimal. In this paper, we investigate linear programming problems with interval right-hand side. Some necessary and sufficient conditions for checking weak optimality of given feasible solutions are established, based on the KKT conditions of linear programming. The proposed methods are simple, easy to implement yet very effective, since they run in polynomial time.     

The application of optimal control methodology to nonlinear programming problems

Dynamic programming techniques have proven to be more successful than alternative nonlinear programming algorithms for solving many discrete-time optimal control problems. The reason for this is that, because of the stagewise decomposition which characterizes dynamic programming, the computational burden grows approximately linearly with the numbern of decision times, whereas the burden for other methods tends to grow faster (e.g.,n ³ for Newton's method). The idea motivating the present study is that the advantages of dynamic programming can be brought to bear on classical nonlinear programming problems if only they can somehow be rephrased as optimal control problems.As shown herein, it is indeed the case that many prominent problems in the nonlinear programming literature can be viewed as optimal control problems, and for these problems, modern dynamic programming methodology is competitive with respect to processing time. The mechanism behind this success is that such methodology achieves quadratic convergence without requiring solution of large systems of linear equations.     

A dynamic production planning and scheduling algorithm for two products processed on one line

This paper presents a dynamic production planning and scheduling algorithm for two products processed on one line over a fixed time horizon. Production rates are assumed fixed, and restrictions are placed or inventory levels and production run lengths. The resulting problem is a nonlinear binary program, which is solved using an implicit enumeration strategy. The algorithm focuses on the run changeover period while developing tighter bounds on the length of the upcoming run to improve computational efficiency. About 99% pf 297 randomly generated problems with varying demand patterns are solved in less than 15 seconds of CPU time on a CDC Cyber 172 Computer. A mixed integer programming formulation of the generalized multi-product case under no-backlogging of demand is also given.     

Microcomputer Software and Hardware Considerations for OR

The widespread use of microcomputers for both development in, and implementation of, operational research projects means that OR workers are increasingly faced with a range of computer hardware and software problems. This article describes the experiences of the author during a period of upgrade from 8 bit microcomputers to networked IBM-AT equipment under PC-DOS. Particular consideration is given to problems of machine compatibility, equipment upgrade, data transfer, local area networking and communications with mainframe equipment.     

Experiments with parallel algorithms for combinatorial problems

In the last decade many models for parallel computation have been proposed and many parallel algorithms have been developed. However, few of these models have been realized and most of these algorithms are supposed to run on idealized, unrealistic parallel machines.The parallel machines constructed so far all use a simple model of parallel computation. Therefore, not every existing parallel machine is equally well suited for each type of algorithm. The adaptation of a certain algorithm to a specific parallel architecture may severely increase the complexity of the algorithm or severely obscure its essence.Little is known about the performance of some standard combinatorial algorithms on existing parallel machines. In this paper we present computational results concerning the solution of knapsack, shortest paths and change-making problems by branch and bound, dynamic programming, and divide and conquer algorithms on the ICL-DAP (an SIMD computer), the Manchester dataflow machine and the CDC-CYBER-205 (a pipeline computer).     

Nonlinear goal programming using multi-objective genetic algorithms

Goal programming is a technique often used in engineering design activities primarily to find a compromised solution which will simultaneously satisfy a number of design goals. In solving goal programming problems, classical methods reduce the multiple goal-attainment problem into a single objective of minimizing a weighted sum of deviations from goals. This procedure has a number of known difficulties. First, the obtained solution to the goal programming problem is sensitive to the chosen weight vector. Second, the conversion to a single-objective optimization problem involves additional constraints. Third, since most real-world goal programming problems involve nonlinear criterion functions, the resulting single-objective optimization problem becomes a nonlinear programming problem, which is difficult to solve using classical optimization methods. In tackling nonlinear goal programming problems, although successive linearization techniques have been suggested, they are found to be sensitive to the chosen starting solution. In this paper, we pose the goal programming problem as a multi-objective optimization problem of minimizing deviations from individual goals and then suggest an evolutionary optimization algorithm to find multiple Pareto-optimal solutions of the resulting multi-objective optimization problem. The proposed approach alleviates all the above difficulties. It does not need any weight vector. It eliminates the need of having extra constraints needed with the classical formulations. The proposed approach is also suitable for solving goal programming problems having nonlinear criterion functions and having a non-convex trade-off region. The efficacy of the proposed approach is demonstrated by solving a number of nonlinear goal programming test problems and an engineering design problem. In all problems, multiple solutions (each corresponding to a different weight vector) to the goal programming problem are found in one single simulation run. The results suggest that the proposed approach is an effective and practical tool for solving real-world goal programming problems.     

Switching and impulsive control of a reflected diffusion

This paper is concerned with the optimal control of a reflected diffusion. The process is controlled by switching the control mode and by impulsing the state of the process. With Bensoussan-Lions' result on stopping time problems, two quasi-variational inequalities are solved as the dynamic programming equations for a discounted cost and a long run average cost criterions.     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

On the number of iterations of local improvement algorithms

A general model of local improvement algorithms in combinatorial optimization accurately confirms performance characteristics often observed in individual cases. The model predicts exponentially bad worst case and low order polynomial average run times for single optimum problems including some linear complementarity problems and linear programming. For problems with multiple local optima, most notably those that are NP-complete, average speed is linearly bounded but accuracy is poor.     

The Impact of Microcomputers upon O.R.

In this paper we report the results of a survey on the impact of microcomputers (micros) upon O.R. Questionnaires were mailed to 216 O.R. workers throughout the U.K. A response rate of 35% was achieved. Nearly half of the groups surveyed have a ratio of at least one micro to one user. These micros are mainly used for spreadsheets, programming, graphics and word-processing.     

Mathematical programming based heuristics for the 0–1 MIP: a survey

The 0–1 mixed integer programming problem is used for modeling many combinatorial problems, ranging from logical design to scheduling and routing as well as encompassing graph theory models for resource allocation and financial planning. This paper provides a survey of heuristics based on mathematical programming for solving 0–1 mixed integer programs (MIP). More precisely, we focus on the stand-alone heuristics for 0–1 MIP as well as those heuristics that use linear programming techniques or solve a series of linear programming models or reduced problems, deduced from the initial one, in order to produce a high quality solution of a considered problem. Our emphasis will be on how mathematical programming techniques can be used for approximate problem solving, rather than on comparing performances of heuristics.     

Fuzzy stochastic linear programming: Survey and future research directions

In many real-life problems one has to base decision on information which is both fuzzily imprecise and probabilistically uncertain. Although consistency indexes providing a union nexus between possibilistic and probabilistic representation of uncertainty exist, there are no reliable transformations between them. This calls for new paradigms for incorporating the two kinds of uncertainty into mathematical models. Fuzzy stochastic linear programming is an attempt to fulfill this need. It deals with modelling and problem solving issues related to situations where randomness and fuzziness co-occur in a linear programming framework. In this paper we provide a survey of the essential elements, methods and algorithms for this class of linear programming problems along with promising research directions. Being a survey, the paper includes many references to both give due credit to results in the field and to help readers obtain more detailed information on issues of interest.     

On the use of internal rate of return in linear and integer programming

Internal rate of return (IRR) is used as a criterion many investment decisions. For example many issuers of new municipal debt evaluate competitive bids on the basis of IRR. We incorporate IRR into mathematical programming formulations in such a way that the resulting problem becomes linear. This linearization permits linear programming and integer linear programming algorithms to be brought to bear on problems which had heretofore been solved in an iterative, time consuming fashion.     

网络路径问题及其多目标扩展形式的混合进化算法

本文就几类困难的网络路径问题及其多目标扩展形式给出相应的混合型进化算法,并在微机上予以实现,为复杂的组合优化问题提供了新的求解手段．     

A primal-dual Newton-type algorithm for geometric programs with equality constraints

An augmented Lagrangian algorithm is used to find local solutions of geometric programming problems with equality constraints (GPE). The algorithm is Newton's method for unconstrained minimization. The complexity of the algorithm is defined by the number of multiplications and divisions. By analyzing the algorithm we obtain results about the influence of each parameter in the GPE problem on the complexity of an iteration. An attempt is made to estimate the number of iterations needed for convergence. In practice, certain hypotheses are tested, such as the influence of the penalty coefficient update formula, the distance of the starting point from the optimum, and the stopping criterion. For these tests, a random problem generator was constructed, many problems were run, and the results were analyzed by statistical methods.The authors are grateful to Dr. J. Moré, Argonne National Laboratory for his valuable comments.This research was partially funded by the Fund for the Advancement of Research at the Technion and by the Applied Mathematical Sciences Research Program (KC-04-02), Office of Energy Research, US Department of Energy, Contract No. W-31-109-Eng-38.     

QUAD01: A data-structured implementation of Hansen's quadratic zero-one programming algorithm

The QUAD01 program described here implements an implicit-enumeration algorithm for quadratic zero-one programming devised by Pierre Hansen just over twenty years ago. The present author's implementation is written in the C programming language and uses an efficient linked-list structure to store and manipulate constraint and objective data. This use, together with the increased speed of modern microcomputers and improved optimisation of generated code, has led to a marked reduction in running times compared with the original implementation (in FORTRAN) by Hansen. Further reductions of running times have been obtained by incorporating dynamic ordering of constraints into QUAD01. Problems having up to 50–100 variables and 100–200 constraints have been solved; some results are reported here.