Editorial: Hierarchical and bilevel programming

Approximately twenty years ago the modern interest for hierarchical programming was initiated by J. Bracken and J.M. McGill [9], [10]. The activities in the field have ever grown lively, both in terms of theoretical developments and terms of the diversity of the applications. The collection of seven papers in this issue covers a diverse number of topics and provides a good picture of recent research activities in the field of bilevel and hierarchical programming. The papers can be roughly divided into three categories; Linear bilevel programming is addressed in the first two papers by Gendreau et al and Moshirvaziri et al; The following three papers by Nicholls, Loridan & Morgan, and Kalashnikov & Kalashnikova are concerned with nonlinear bilevel programming; and, finally, Wen & Lin and Nagase & Aiyoshi address hierarchical decision making issues relating to both biobjective and bilevel programming.     

Multicriteria integer programming: A (hybrid) dynamic programming recursive approach

Dynamic programming recursive equations are used to develop a procedure to obtain the set of efficient solutions to the multicriteria integer linear programming problem. An alternate method is produced by combining this procedure with branch and bound rules. Computational results are reported.     

A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming.Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory.Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly.Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming,l ₁ estimation, goal programming, interval programming, and nonlinear optimization.This research has been supported in part by the National Science Foundation under grant MCS-8217261.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

背包问题的两阶段动态规划算法

本文通过理论分析给出了背包问题的两阶段动态规划算法，用例题说明了其求解过程。在计算机上运用本文所述算法和背包问题的动态规划算法求解了大量例题。解题实践说明，对于大中型背包问题，两阶段动态规划算法由于只要求对少量变量进行排序而使解题时间大为缩短，是一种值得推荐的算法。     

Complexity of some parametric integer and network programming problems

Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem. This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646     

模糊线性规划问题的一种新的单纯形算法

提出求解模糊线性规划问题的一种新的思路 ,就是应用单纯形法先求解与 (FLP)相应的普通线性规划问题 ,通过模糊约束集与模糊目标集的隶属度的比较 ,获得两个集合交集的最优隶属度 ,将此最优隶属度代入最优单纯形表中 ,即可求得 (FLP)的解。本算法只需在一张适当的迭代表台上执行单纯形迭代过程 ,简捷方便适用     

Constrained integer linear fractional programming problem

An integer linear fractional programming problem, whose integer solution is required to satisfy any h out of given n sets of constraints has been discussed in this paper. Method for ranking and scanning all integer points has also been developed and a numerical illustration is included in support of theory.     

Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems. Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied. We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications. Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional programming to evaluate the efficiency of these methods have been carried out.     

Linear programming in measure spaces

This paper studies a linear programming problem in measure spaces (LPM). Several results are obtained. First, the optimal value of LPM can be equal to the optimal value of the dual problem (DLPM), but the solution of DLPM may be not exist in its feasible region. Sccond, :he relations between the optimal solution of LPM and the extreme point of the feasible region of LPM are discussed. In order to investigate the conditions under which a feasible solution becomes an extremal point, the inequality constraint of LPM is transformed to an equality constraint. Third, the LPM can be reformulated to be a general capacity problem (GCAP) or a linear semi-infinite programming problem (LSIP = SIP), and under appropriate restrictioiis, the algorithm developed by the authors in [7] and [8] are applicable for developing an approximation scheme for the optimal solution of LPM     

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.     

会议安排的线形规划模型

在这篇文章中,采用归一化,多目标规划模型,筛选出筹备组的预定房间．用三个单目标规划确定了六家宾馆的具体订房情况与会议室的租赁情况．以经济为目标函数,满足不同房问的入住需求为约束条件,通过lingo求解得出订房情况．     

Transient policies in discrete dynamic programming: Linear programming including suboptimality tests and additional constraints

This paper investigates the computation of transient-optimal policies in discrete dynamic programming. The model, is quite general: it may contain transient as well as nontransient policies. and the transition matrices are not necessarily substochastic. A functional equation for the so-called transient-value-vector is derived and the concept of superharmonicity is introduced. This concept provides the linear program to compute the transientvalue-vector and a transient-optimal policy. We also discuss the elimination of suboptimal actions, the solution of problems with additional constraints, and the computation of an efficient policy for a multiple objective dynamic programming problem.     

Linear max-min programming

Theoretical aspects of the programming problem of maximizing the minimum value of a set of linear functionals subject to linear constraints are explored. Solution strategies are discussed and an optimality condition is developed. An algorithm is also presented.This research was partially supported by the Management Research Center of the University of Wisconsin—Milwaukee.     

双目标规划问题的像集与求解

经济管理的决策目标往往与成本、收益相关,双目标规划在经济管理中具有广泛应用.然而,尚缺乏成熟的算法确定双目标规划问题的全部解.给出双目标规划问题像集的一般性确定法,以求其解,为研究目的所在.具体而言,构造一个带等式约束的单目标规划问题,以确定双目标规划问题像集之部分边界,并借助拉格朗日乘子符号判断其单调性,据此确定原问题的帕累托解与弱帕累托解.这相当于提供了一个求解双目标规划问题的一般性框架.     

Duality for minmax programming involving V-invex functions

Sufficient optimality conditions and duality results for a class of minmax programming problems are obtained under V-invexity type assumptions on objective and constraint functions. Applications of these results to certain fractional and generalized fractional programming problems are also presented     

模糊系数规划

给出了一模糊系统规划的定义,该定义与通常的模糊规划义有所不同,它容许规划中的目标函数系数和所有约束函数系数可以是模糊数,并且容许既有模糊系数不等式的束函数又有模糊和所有约束函数系数都可以提模糊数,并且容许既有模糊系数不等式的束函数又有模糊系数等式约束函数,本文还对满足一定条件的模糊系数规划,包括模糊系数线性规划和模糊系数二次规划,给出了切实可行的求解方法。     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.     

An economic interpretation of stochastic programs

The purpose of this note is to interpret a class of stochastic programming problems in economic terms. The primal stochastic program is shown to represent a certain production program of an entrepreneur. The dual program, which is also a stochastic program, represents the problem of a contractor who desires to purchase the entrepreneur's resources and sell product back to him.     

Optimal design of a membrane separation process using signomial programming

A multistage membrane separation process for hydrogen recovery is described and formulated as a signomial programming problem. Two different configurations are examined. A 3-stage and a 5-stage process design problem are solved. The optimal solution to these programs is computed from an initial point that does not satisfy the mass balance or transport constraints of the process, using a primal-based geometric programming code. Also examined is the sensitivity of the optimal solution to changes in purity requirements. In all cases, computation times are very reasonable ranging from 2 to 4 seconds of IBM 370/165 CPU time.