Constrained mixture distributions

The problem of estimating the weights associated with mixture distributions subject to several constraints, such as the percentile and/or moment constraints, is analyzed using the general theory of polyhedral convex cones and systems of inequalities. We address three problems associated with constrained mixture distributions: (a) Compatibility: a set of inequalities is obtained to check whether or not any given set of constraints lead to a feasible solution for the weights, (b) Feasible solutions: a general expression for building feasible solutions for the weights associated with the given constraints is obtained, and (c) Equivalence: the set of all feasible weights is obtained. In addition, the problem is shown to lead to a new mixture distribution, without extra constraints. This new mixture distribution can then be easily used for the statistical analysis (e.g. estimation and hypotheses testing) instead of the original mixture distribution with extra constraints. The proposed methods are illustrated by numerical examples.     

Polyhedral Combinatorics in Combinatorial Optimization

Polyhedral combinatorics is a subarea of combinatorial optimization of increasing practical importance. It deals with the application of the theory of linear systems and linear algebra to combinatorial problems. The paper is not intended as a survey on polyhedral combinatorics but it reviews some of the main concepts and proof techniques.     

基于运筹优化的物流与设施规划课程教学研究

在传统教学中,物流与设施规划课程的物流分析、设施布局等内容的一些经典问题采用启发式方法或试验法来解决。为了更精确地解决这些问题,采用数学规划方法提供解决方案。主要围绕建模技巧、应用软件教学和解决物流与设施规划专业案例等方面培养学生运用优化原理与方法构建运筹优化模型的能力以及运用ILOG OPL优化软件解决实际优化问题的能力。以二次分配问题和多产品工艺过程图优化问题为案例阐述了数学规划建模和编程求解的过程。     

用混合蚁群算法求解多工序订单生产计划

多工序订单生产排序问题,是一类典型的组合优化问题。采用混合蚁群算法,对一种多工序订单模型进行建模求解,并给出了详细的算法步骤。通过用不同数量的订单、工序组合的数据进行模拟计算与结果比较,证明了混合蚁群算法在求解此类的问题的有效性以及良好的鲁棒性。     

差异演化算法求解集合划分问题

集合划分问题是组合优化中典型的NP难题,建立了集合划分问题模型,采用差异演化算法对其进行求解。通过对其它文献中仿真实例的计算和结果对比,表明了算法对求解集合划分问题的可行性和有效性。     

Stochastic programming in production planning: a case with none-simple recourse

Abstract  In modeling real world planning problems as optimization programs the assumption that all parameters are known with certainty is often more seriously violated than the assumption that the objective function and the constraints can be approximated sufficiently accurate by lineair functions. In this paper we discuss the concrete application of stochastic programming to a multiperiod production planning problem in which the demand for the products during the various periods is assumed stochastic with known probability distribution. Since the resulting stochastic program does not possess the property of "simple" recourse no direct use can be made of existing methods that have been proposed in literature for solving problems of this type.     

Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem

The introduction of Karmarkar's polynomial algorithm for linear programming (LP) in 1984 has influenced wide areas in the field of optimization. While in the 1980s emphasis was on developing and implementing efficient variants of interior point methods for LP, the 1990s have shown applicability to certain structured nonlinear programming and combinatorial problems. We will give a historical account of the developments and illustrate the typical results by analyzing a new method for computing the smallest eigenvalue of a matrix. We formulate this latter problem as a so-called semidefinite optimization problem. Semidefinite optimization has recently gained much attention since it has a lot of applications in various fields (like control and system theory, combinatorial optimization, algebra, statistics, structural design) and semidefinite problems can be efficiently solved with interior point methods.     

A genetic algorithm for the partial binary constraint satisfaction problem: an application to a frequency assignment problem

We describe a genetic algorithm for the partial constraint satisfaction problem. The typical elements of a genetic algorithm, selection, mutation and cross-over, are filled in with combinatorial ideas. For instance, cross-over of two solutions is performed by taking the one or two domain elements in the solutions of each of the variables as the complete domain of the variable. Then a branch-and-bound method is used for solving this small instance. When tested on a class of frequency assignment problems this genetic algorithm produced the best known solutions for all test problems. This feeds the idea that combinatorial ideas may well be useful in genetic algorithms.     

Alternative algorithms for the macRae OLCV strategy

Using dynamic programming MacRae obtained a linear feedback law for her open loop constrained variance (OLCV) strategy. To compute the control law requires solving a two point boundary value problem. The dynamic programming formulation does not admit gradient related algorithms. This paper presents an alternative augmented Lagrangian formulation which can be solved as a deterministic constrained optimization problem. The new approach is superior because it admits gradient related algorithms plus all the algorithms which could be employed using the original approach. Three examples demonstrate the superiority of the new approach.     

JIT环境下多工序订单生产排序模型及改进蚁群算法应用研究

订单排序问题是一类典型的组合优化问题,采用改进蚁群算法对一种具有多生产工序和JIT交货的订单模型进行建模求解,给出了详细的算法步骤,通过仿真计算和结果分析,与模拟退火算法和基本蚁群算法进行对比,证明了本算法的有效性。     

Commentary on facility location in the presence of congested regions with the rectilinear distance metric

This paper is a commentary on the work of Butt and Cavalier (Socio-Econ. Plann. Sci. 31(2) (1997) 103), a paper that was published in an earlier issue of this journal. With the aid of an example problem, we demonstrate that the set of gridlines proposed by them to find the rectilinear least cost path between two points in the presence of convex polygonal congested regions is inadequate. We proceed to prove its adequacy for the case of rectangular congested regions in which the edges of the rectangles are parallel to the travel directions. In wake of the difficulties of the general problem, we consider a specific example of a convex quadrilateral congestion region and a pair of external origin and destination points. Finally, we revisit the example shown in Butt and Cavalier's paper and present a mixed integer linear programming formulation that determines the optimal locations of the entry and exit points for this example.     

Planning for education in the health services: a multicriterion approach.

Administrators are often confronted with problems for which there exist several distinct measures of success. Such problems can be expressed in terms of linear programming models with several linear “criterion” functions instead of a single objective function. Although a variety of techniques are available for the solution of multicriterion problems, there exists a need for one which does not assume technical sophistication on the part of the decision maker and which provides valid solutions with minimum effort. “Efficient Manifold Presentation”, the approach used here, is based on the concept that the ideal solution must be a Pareto optimal solution. A method for finding an expression for the finite set of all Pareto optimal solutions to a linear program with multiple linear criteria is presented. Two processes are involved; first, the discovery of all Pareto optimal vertices of the feasible region, and secondly a grouping of these into sets each of which defines a convex polyhedron of Pareto optimal possibilities. Alternate versions of the second process are suggested for use under varying circumstances. An example of the applicability of the method for modeling enrollment and staffing policy in an educational institution is provided.     

A nonlinear approach to a class of combinatorial optimization problems

A special class of combinatorial optimization problems is considered. We develop a compact nonconvex quadratic model for these problems that incorporates all inequality constraints in the objective function, and discuss two approximation algorithms for solving this model. One is inspired by Karmarkar's potential reduction algorithm for solving combinatorial optimization problems; the other is a variant of the reduced gradient method. The paper concludes with computational experiences with both real-life and randomly generated instances of the frequency assignment problem. Large problems are satisfactorily solved in reasonable computation times.     

STOCHASTIC INTEGER PROGRAMMING BY DYNAMIC PROGRAMMING

Stochastic integer programming is a suitable tool for modeling hierarchical decision situations with combinatorial features. In continuation of our work on the design and analysis of heuristics for such problems, we now try to find optimal solutions. Dynamic programming techniques can be used to exploit the structure of two–stage scheduling, bin packing and multiknapsack problems. Numerical results for small instances of these problems are presented.     

A multiobjective optimization approach to smart growth in land development

In this paper we apply a multiobjective optimization model of Smart Growth to land development. The term Smart Growth is meant to describe development strategies—that do not promote urban sprawl. However, the term is somewhat open to interpretation. The multiobjective aspects arise when considering the conflicting interests of the various stakeholders involved in land development decisions: the government planner, the environmentalist, the conservationist, and the land developer. We present a formulation—employing linear and convex quadratic objective functions subject to polyhedral and binary constraints for the stakeholders. The resulting optimization problems are convex, quadratic mixed integer programs that are NP-complete. We report numerical results with this model for Montgomery County, Maryland, and present them using a geographic information system (GIS).     

Currently practiced formulations for the assembly line balance problem

New formulations for the assembly line balance problem are proposed based on interviews and surveys of practicing engineers. These formulations are the basis for a model in goal programming form. A branch-and-bound algorithm is developed which can solve the model for an optimum solution. Computational studies show that computer run time is very modest for moderate size problems.Interviews and a survey of practicing engineers were used to develop a list of goals or constraints germane to the assembly line balance problem. These included minimizing working areas or employees, making sure tasks assigned to a station do not exceed the cycle time, and adhering to sequence constraints. These constraints are included in most traditional models. However, additional goals were mentioned. These included avoiding changes in workload assigned to a work area, adhering to layout requirements of the plant, making combinations of tasks interesting, avoiding the combination of physiologically demanding tasks, etc.The additional goals above are incorporated in a new formulation for the assembly line balance problem. This formulation is in goal programming form. The goal programming model attempts to minimize deviations from goals. If deviations are necessary, lowest ranked goals are violated first. The objective function of the model is based on an ordinal ranking of goals only. The survey mentioned above showed that engineers did not find it difficult to rank the importance of goals.The proposed goal programming model is a mixed integer linear program. Previous studies have shown that cutting plane and implicit enumeration techniques are inferior to branch-and-bound algorithms. A branch-and-bound method, called GoalOriented Algorithm for Line Balance (GOAL), is developed to solve the formulations proposed in the paper.GOAL was computationally tested with 50 problems. These problems varied in size from 4 to 35 tasks. One of the problems was an engine cradle assembly problem encountered by an automobile manufacturer. Computer run times appeared reasonable. For example, the engine cradle problem 35 tasks) required only 16.3 seconds CPU on the DEC PDF at California State University, Northridge. GOAL's execution time appeared linearly proportional to the number of tasks required for most problems.     

A volume and material handling cost based heuristic for designing cellular manufacturing cells

One of the major problems in a group technology or cellular manufacturing environment is the formation of part groups and machine cells. Because of the combinatorial nature of the cell formation problem, it is difficult to solve the problem optimally. Most of the procedures related to cell design in cellular manufacturing operate on the part-machine incidence matrix in an attempt to identify block diagonality. If complete block diagonality does not exist, the decision about cell configuration is left to the subjective judgement of the designer. These procedures are also generally based on part routing only, and do not consider part volume and material handling costs.In this paper we develop an integer programming model, as well as a heuristic to effectively assign machines to cells. In these procedures we consider component volumes, costs related to movement of components between and within cells, and penalty for not using all machines in a cell visited by a component. Since the integer programming formulation becomes large even for small problems, an efficient heuristic is developed to solve larger problems. The heuristic solutions to 180 randomly generated small problems were compared against the optimal solutions obtained by the integer programming model. The heuristic has been found to identify optimal solutions in all 180 cases.This heuristic is also compared to several well known algorithms on 900 larger test problems. These problems were generated to cover a wide range of environmental situations such as varying levels of block diagonality in the part-machine incidence matrix, and diversity in the component volumes and material handling costs. In 99% of the problems our heuristic generated solutions which are better or as good as the best solution obtained by other algorithms. Further, in situations where complete block diagonality in the part-machine incidence matrix did not exist, our heuristic produced even better results. Since the maximum number of iterations required in our heuristic is the number of machines in the problem, the heuristic is computationally efficient.     

改进的蚁群算法在TSP中的应用

介绍了蚁群算法的特点,提出了基于蚁群算法的TSP问题的求解方法,并分别建立基本蚁群算法及MAX-MIN蚁群算法模型,并引入“三步走”法确定模型参数的最优组合,还结合了交叉局部优化相关的求凸壳顶点的算法进行预处理,进行仿真分析比较。实验结果表明基于MMAS模型相对于基本蚁群算法模型,有比较好最短路径选择能力及良好的可扩展性能,能够较好地适应物流配送系统的要求。