David G. Luenberger,Linear and nonlinear programming, 2nd edition,Addison-Wesley,Reading (1984), xv + 492 pages, $35.50

This paper considers a stochastic version of the linear continuous type knapsack problem in which the cost coefficients are random variables. The problem is to find an optimal solution and an optimal probability level of the chance constraint. This problem P₀ is first transformed into a deterministic equivalent problem P. Then a subproblem with a positive parameter is introduced and a close relation between P and its subproblem is shown. Further, an auxiliary problem of the subproblem is introduced and a direct relation between P and the auxiliary problem is derived through a relation connecting the subproblem and its auxiliary problem. Fully utilizing these relations, an efficient algorithm is proposed that finds an optimal solution of P in at most O(n⁴) computational time where n is the number of decision variables. Finally, further research problems are discussed.     

Approximate solution of nonlinear problems of optimal control of oscillatory processes using the method of canonical separation of motions : PMM vol.40, n 6, 1976, pp. 1024–1033

An asymptotic method of solving certain problems of optimal control of motion of the standard type systems with rotating phase is developed. It is assumed that the controls enter only the small perturbing terms, and that the fixed time interval over which the process is being considered is long enough to ensure that the slow variables change essentially. Assuming also that the system and the controls satisfy the necessary requirements of smoothness, the method of canonical averaging [1] is used to construct a scheme for deriving a simplified boundary value problem of the maximum principle. The structure of the set of solutions of the boundary value problem is investigated and a scheme for choosing the optimal solution with the given degree of accuracy in the small parameter is worked out. The validity of the approximate method of solving the boundary value problem is proved. The method suggested in [2] for constructing a solution in the first approximation for similar problems of optimal control is developed.     

101 Activities for Teaching Creativity and Problem Solving,Arthur B. VanGundy,Pfeiffer, J. Wiley,CA, USA (2004), p. xi + 391, £41.95, ISBN: 0-7879-7402-1

Many web sites (e.g. Hotmail, Yahoo) provide free services to the users while generating revenues from advertising. Advertising revenue is, therefore, critical for these sites. This in turn raises the question, how should advertisements at a web site be scheduled in a planning horizon to maximize revenue. Advertisements on the web are specified by geometry and display frequency and both of these factors need to be considered in developing a solution to the advertisement scheduling problem. Since this problem belongs to the class of NP-hard problems, we first develop a heuristic called LSMF to solve the problem. This heuristic is then combined with a genetic algorithm (GA) to develop a hybrid GA. The hybrid GA solution is first compared with the upper bound obtained by running CPLEX for the integer programming formulation of the problem. It is then also compared with an existing algorithm proposed in the literature. Our computational results show that the hybrid GA performs exceptionally well in the sense that it provides optimal or near optimal solution for a wide range of problem instances of realistic sizes and the improvements over existing algorithm are substantial. Finally we present a case study to illustrate how revenue could be significantly increased with a small improvement in the advertisement schedule. It is the first such study in this setup.     

The game problem on the dolichobrachistochrone : PMM vol.40, n 6, 1976, pp. 1003–1013

The capture and evasion sets, the players' optimal strategies and the game value determined for the game problem on the dolichobrachistochrone, analysed within the framework of a position formalism similar to [1]. Singularities inherent in the game of the minimax-maximin time to contact [1, 2] become apparent; they are determined in the given problem by the specific behavior of the optimal paths close to the target set. Isaacs [4] examined the game problem on the dolichobrachistochrone, being the game analog of the classical variational problem on the brachistochrone [3]. However, as was shown in [5], the solution proposed by Isaacs contains erroneous statements.     

On the game theory approach to problems of optimization of elastic bodies : PMM vol. 37, n6, 1973, pp. 1098–1108

Problems of optimization of elastic bodies are considered usually in deterministic formulation, and for their solution the methods of variational calculus and the theory of optimal control are applicable (c.f., e.g., [1] and [2–4]). In the present paper there are considered those cases when either the complete information concerning the applied loads is not available,or it is known that the structure may be subjected subsequently to various loads of a certain class. The formulation is given of the problem of the determination of the shape of the elastic body, optimal for a class of loads, and there is indicated a general scheme for its solution based on the “minimax” approach used in the theory of games. Problems of optimization of elastic beams are considered and as a result of their solution certain features of optimal shapes are exhibited.     

Dual gradient method for linearly constrained,strongly convex,separable mathematical programming problems

A new dual gradient method is given to solve linearly constrained, strongly convex, separable mathematical programming problems. The dual problem can be decomposed into one-dimensional problems whose solutions can be computed extremely easily. The dual objective function is shown to have a Lipschitz continuous gradient, and therefore a gradient-type algorithm can be used for solving the dual problem. The primal optimal solution can be obtained from the dual optimal solution in a straightforward way. Convergence proofs and computational results are given.     

The EOQ problem with decidable warehouse capacity: Analysis, solution approaches and applications

The Economic Order Quantity (EOQ) problem is a fundamental problem in supply and inventory management. In its classical setting, solutions are not affected by the warehouse capacity. We study a type of EOQ problem where the (maximum) warehouse capacity is a decision variable. Furthermore, we assume that the warehouse cost dominates all the other inventory holding costs. We call this the EOQ-Max problem and the D-EOQ-Max problem, if the product is continuously divisible and discrete, respectively. The EOQ-Max problem admits a closed form optimal solution, while the D-EOQ-Max problem does not because its objective function may have several local minima. We present an optimal polynomial time algorithm for the discrete problem. Construction of this algorithm is supported by the fact that continuous relaxation of the D-EOQ-Max problem provides a solution that can be up to 50% worse than the optimal solution, and this worst-case error bound is tight. Applications of the D-EOQ-Max problem include supply and inventory management, logistics and scheduling.     

可修复人机储备系统稳态解的最优控制

针对可修复人机储备系统的模型,以范数指标泛函作为衡量系统可控性的标准,利用Banach空间理论讨论系统稳态解达到预期概率分布的最优控制问题,给出了其最优解存在唯一性.     

Least-Squares Mirrorsymmetric Solution for Matrix Equations （AX=B, XC=D）

In this paper, least-squaxes mirrorsymmetric solution for matrix equations (AX = B, XC = D) and its optimal approximation is considered. With special expression of mirrorsymmetric matrices, a general representation of solution for the least-squares problem is obtained. In addition, the optimal approximate solution and some algorithms to obtain the optimal approximation are provided.     

Optimal control for N-Person stochastic inclusions. II

The existence of a solution of a large class of nonlinear stochastic inclusions is shown. The existence of an open loop problem for those stochastic inclusions, is established. Application to an optimal strategy problem arising in the fight against drugs is given.     

An optimal control problem for a pest, predator, and plant system

The paper is devoted to an optimal control problem for a system of three nonlinear parabolic equations from population dynamics. The equations model a trophic chain consisting of a predator, a pest and a plant species. The existence and uniqueness of the positive solution for the system are proved. The control variable is connected with the action of a pesticide. Our goal is to minimize the density of the pest and to maximize the plant density. The existence of the optimal solution is proved. The first and second order optimality conditions are established.     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

Value-Estimation Function Method for Constrained Global Optimization

A novel value-estimation function method for global optimization problems with inequality constraints is proposed in this paper. The value-estimation function formulation is an auxiliary unconstrained optimization problem with a univariate parameter that represents an estimated optimal value of the objective function of the original optimization problem. A solution is optimal to the original problem if and only if it is also optimal to the auxiliary unconstrained optimization with the parameter set at the optimal objective value of the original problem, which turns out to be the unique root of a basic value-estimation function. A logarithmic-exponential value-estimation function formulation is further developed to acquire computational tractability and efficiency. The optimal objective value of the original problem as well as the optimal solution are sought iteratively by applying either a generalized Newton method or a bisection method to the logarithmic-exponential value-estimation function formulation. The convergence properties of the solution algorithms guarantee the identification of an approximate optimal solution of the original problem, up to any predetermined degree of accuracy, within a finite number of iterations.     

分布参数最优控制的边界元共轭梯度算法

研究了一类线性椭圆型分布参数最优控制问题的数值解算法.得到最优控制对应的最优性方程组,在凸性条件下,证明了最优控制的唯一存在性问题.将最优控制问题化为以控制函数和状态函数为局中人的递阶式(Stackelberg)非合作对策问题,其平衡点是最优控制的解.进一步得到求平衡点的边界元共轭梯度算法.最后,研究算法中边界元离散的误差估计,以算例验证该算法.     

An exact method for scheduling a yard crane

This paper studies an operational problem arising at a container terminal, consisting of scheduling a yard crane to carry out a set of container storage and retrieval requests in a single container block. The objective is to minimize the total travel time of the crane to carry out all requests. The block has multiple input and output (I/O) points located at both the seaside and the landside. The crane must move retrieval containers from the block to the I/O points, and must move storage containers from the I/O points to the block. The problem is modeled as a continuous time integer programming model and the complexity is proven. We use intrinsic properties of the problem to propose a two-phase solution method to optimally solve the problem. In the first phase, we develop a merging algorithm which tries to patch subtours of an optimal solution of an assignment problem relaxation of the problem and obtain a complete crane tour without adding extra travel time to the optimal objective value of the relaxed problem. The algorithm requires common I/O points to patch subtours. This is efficient and often results in obtaining an optimal solution of the problem. If an optimal solution has not been obtained, the solution of the first phase is embedded in the second phase where a branch-and-bound algorithm is used to find an optimal solution. The numerical results show that the proposed method can quickly obtain an optimal solution of the problem. Compared to the random and Nearest Neighbor heuristics, the total travel time is on average reduced by more than 30% and 14%, respectively. We also validate the solution method at a terminal.     

Advertising Budgeting,Wearout and Copy Replacement

In this paper we offer a formulation for the "Copy Life Cycle" phenomenon. In particular, we introduce simultaneously three decision variables, the optimal advertising expenditures during a given planning horizon, the optimal times for copy replacements and the optimal investments in the new copies. The analysis and the solution of the problem is carried out by a mixed optimization technique based on dynamic programming and optimal control theory.     

Active Constraint Set Invariancy Sensitivity Analysis in Linear Optimization

Active constraint set invariancy sensitivity analysis is concerned with finding the range of parameter variation so that the perturbed problem has still an optimal solution with the same support set that the given optimal solution of the unperturbed problem has. However, in an optimization problem with inequality constraints, active constraint set invariancy sensitivity analysis aims to find the range of parameter variation, where the active constraints in a given optimal solution remains invariant.For the sake of simplicity, we consider the primal problem in standard form and consequently its dual may have an optimal solution with some active constraints. In this paper, the following question is answered: “what is the range of the parameter, where for each parameter value in this range, a dual optimal solution exists with exactly the same set of positive slack variables as for the current dual optimal solution?”. The differences of the results between the linear and convex quadratic optimization problems are highlighted too.     

分派问题的灵敏度分析及其应用

讨论分派问题的效率矩阵的元素发生变化时,对最优解的影响;在保持分派问题最优解不变的情况下,效率矩阵的元素的变化范围;及当分派问题的最优解发生变化后,如何用简单的方法求得新的最优解等.     

On the terminal control problem

A minimum-time problem is considered, where the final point is locally controllable. It is shown that it is possible to construct a suboptimal control with a transfer time close to the optimal transfer time of the relaxed system. The resulting trajectory will satisfy initial and final conditions. Furthermore, it is shown that, if an optimal solution exists for the problem, then this optimal solution is also an optimal solution of the relaxed problem. In this case, the relaxed problem need not be solved.The authors wish to thank Dr. D. Hazan, Scientific Department, Ministry of Defense, Israel, for a fruitful discussion of this problem.     

A Common Regularization for Three Reservoir Optimal Control Problems

Four optimal control problems of reservoir release are investigated. The first problem is to minimize the peak release in order to prevent flood and to reduce the flood height. The second problem is to maximize the lowest release in order to ensure irrigation, water supply, shipping and environment downstream. The third problem is to minimize the flooding duration in order to reduce damage to goods, possessions, plants, levees, etc. It is shown that these three problems may possess infinitely many different optimal solutions, but they all have a common optimal solution, which is the unique optimal solution of the fourth problem. Since this unique optimal solution depends continuously on the input data, the fourth problem is well-posed and it can be considered as a common regularization of the three ill-posed problems.