A Bayesian approach to continuous type principal-agent problems

Singham (2019) proposed an important advance in the numerical solution of continuous type principal-agent problems using Monte Carlo simulations from the distribution of agent “types” followed by bootstrapping. In this paper, we propose a Bayesian approach to the problem which produces nearly the same results without the need to rely on optimization or lower and upper bounds for the optimal value of the objective function. Specifically, we cast the problem in terms of maximizing the posterior expectation with respect to a suitable posterior measure. In turn, we use efficient Markov Chain Monte Carlo techniques to perform the computations.     

An Exact Solution Method for Reliability Optimization in Complex Systems

Systems reliability plays an important role in systems design, operation and management. Systems reliability can be improved by adding redundant components or increasing the reliability levels of subsystems. Determination of the optimal amount of redundancy and reliability levels among various subsystems under limited resource constraints leads to a mixed-integer nonlinear programming problem. The continuous relaxation of this problem in a complex system is a nonconvex nonseparable optimization problem with certain monotone properties. In this paper, we propose a convexification method to solve this class of continuous relaxation problems. Combined with a branch-and-bound method, our solution scheme provides an efficient way to find an exact optimal solution to integer reliability optimization in complex systems. This research was partially supported by the Research Grants Council of Hong Kong, grants CUHK4056/98E, CUHK4214/01E and 2050252, and the National Natural Science Foundation of China under Grants 79970107 and 10271073.     

Monte Carlo simulation via a numerical algorithm for solving a nonlinear inverse problem

This paper is intended to provide a numerical algorithm involving the combined use of the finite differences scheme and Monte Carlo method for estimating the diffusion coefficient in a one-dimensional nonlinear parabolic inverse problem. In the present study, the functional form of the diffusion coefficient is unknown a priori. The unknown diffusion coefficient is approximated by the polynomial form and the present numerical algorithm is employed to find the solution. To modify the values of estimated coefficients of this polynomial form, we introduce a random search algorithm in Monte Carlo method for global optimization. A numerical test is performed in order to show the efficiency and accuracy of the present work.     

The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps.We present a detailed computational study of the application of the SAA method to solve three classes of stochastic routing problems. These stochastic problems involve an extremely large number of scenarios and first-stage integer variables. For each of the three problem classes, we use decomposition and branch-and-cut to solve the approximating problem within the SAA scheme. Our computational results indicate that the proposed method is successful in solving problems with up to 2¹⁶⁹⁴ scenarios to within an estimated 1.0% of optimality. Furthermore, a surprising observation is that the number of optimality cuts required to solve the approximating problem to optimality does not significantly increase with the size of the sample. Therefore, the observed computation times needed to find optimal solutions to the approximating problems grow only linearly with the sample size. As a result, we are able to find provably near-optimal solutions to these difficult stochastic programs using only a moderate amount of computation time.     

Computing Aviation Sparing Policies: Solving a Large Nonlinear Integer Program

Deployed US Navy aircraft carriers must stock a large number of spare parts to support the various types of aircraft embarked on the ship. The sparing policy determines the spares that will be stocked on the ship to keep the embarked aircraft ready to fly. Given a fleet of ten or more aircraft carriers and a cost of approximately 50 million dollars per carrier plus the cost of spares maintained in warehouses in the United States, the sparing problem constitutes a significant portion of the Navy’s resources. The objective of this work is to find a minimum-cost sparing policy that meets the readiness requirements of the embarked aircraft. This is a very large, nonlinear, integer optimization problem. The cost function is piecewise linear and convex while the constraint mapping is highly nonlinear. The distinguishing characteristics of this problem from an optimization viewpoint are that a large number of decision variables are required to be integer and that the nonlinear constraint functions are essentially “black box” functions; that is, they are very difficult (and expensive) to evaluate and their derivatives are not available. Moreover, they are not convex. Integer programming problems with a large number of variables are difficult to solve in general and most successful approaches to solving nonlinear integer problems have involved linear approximation and relaxation techniques that, because of the complexity of the constraint functions, are inappropriate for attacking this problem. We instead employ a pattern search method to each iteration of an interior point-type algorithm to solve the relaxed version of the problem. From the solution found by the pattern search on each interior point iteration, we begin another pattern search on the integer lattice to find a good integer solution. The best integer solution found across all interations is returned as the optimal solution. The pattern searches are distributed across a local area network of non-dedicated, heterogeneous computers in an office environment, thus, drastically reducing the time required to find the solution.     

Simulation-based parametric optimization for long-term asset allocation using behavioral utilities

This article presents a simulation-based methodology for finding optimal investment strategy for long-term financial planning. The problem becomes intractable due to its size or the properties of the utility function of the investors. One approach is to make simplifying assumptions regarding the states of the world and/or utility functions in order to obtain a solution. These simplifications lead to the true solution of an approximate problem. Our approach is to find a good approximate solution to the true problem. We approximate the optimal decision in each period with a low dimensional parameterization, thus reformulating the problem as a non-linear, simulation-based optimization in the parameter space. The dimension of the reformulated optimization problem becomes linear in the number of periods. The approach is extendable to other problems where similar solution characteristics are known.     

高校教育成本测算及其优化管理模型

在高校成本层次分类的基础上,建立了生均成本测算的一般模型,针对教育成本投入过程中因学生人数随机变化而存在的风险,引进教学质量函数,提出了办学效益和教学质量的双目标优化模型.利用凸分析和优化原理得到优化问题解的存在性,全部正解的β取值范围以及最优解满足的充要条件,对最优解的定量计算给出了基于Monte Carlo模拟的遗传算法设计,并进行了相应的经济意义分析.     

Global optimization of signomial mixed-integer nonlinear programming problems with free variables

Mixed-integer nonlinear programming (MINLP) problems involving general constraints and objective functions with continuous and integer variables occur frequently in engineering design, chemical process industry and management. Although many optimization approaches have been developed for MINLP problems, these methods can only handle signomial terms with positive variables or find a local solution. Therefore, this study proposes a novel method for solving a signomial MINLP problem with free variables to obtain a global optimal solution. The signomial MINLP problem is first transformed into another one containing only positive variables. Then the transformed problem is reformulated as a convex mixed-integer program by the convexification strategies and piecewise linearization techniques. A global optimum of the signomial MINLP problem can finally be found within the tolerable error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method.     

在Newton-PCG方法中的一个一维整数最优化问题

本文研究在Newton-PCG方法中出现的一个一维整数最优化问题．通过引入和研究几个连续变量的辅助问题，我们建立了一个简单而有效的算法．这一算法的主要计算量是求解两次非线形方程zlnz—c=0，因此是非常小的．另外，我们还对这一问题的最优值进行了估计．     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

On the optimal design of the randomized unbiased Monte Carlo estimators

We consider a class of unbiased Monte Carlo estimators and develop an efficient algorithm to produce the distribution of the optimal random truncation level. We establish the convergence and optimality results of the associated algorithm and also derive its exact complexity. We find this algorithm has a much lower complexity as compared to the existing one in the literature. The proposed algorithm is also applicable to optimization problems arising in supply chain management, such as economic reorder interval problem.     

Nonnormal deterministic equivalents and a transformation in stochastic mathematical programming

This paper considers random variables of the continuous type in a stochastic programming problem and presents (1) a general approach to the development of deterministic equivalents of constraints to be satisfied within certain probability limits, and (2) a deterministic transformation of a stochastic programming problem with random variables in the objective function. Deterministic equivalents are developed for constraints containing uniform random variables, but the approach used can be applied to other types of continuous random variables, as well. When the random variables appear in the objective function, a deterministic transformation of the stochastic programming problem is obtained to yield a closed-form solution without resort to a Monte Carlo computer simulation. Extension of this approach to stochastic problems with discrete random variables and integer decision variables is discussed briefly. A numerical example is presented.     

Reduction of the bilevel stochastic optimization problem with quantile objective function to a mixed‐integer problem

The paper is devoted to the stochastic optimistic bilevel optimization problem with quantile criterion in the upper level problem. If the probability distribution is finite, the problem can be transformed into a mixed‐integer nonlinear optimization problem. We formulate assumptions guaranteeing that an optimal solution exists. A production planning problem is used to illustrate usefulness of the model. Copyright © 2017 John Wiley & Sons, Ltd.     

Robustness analysis in Multi-Objective Mathematical Programming using Monte Carlo simulation

In most multi-objective optimization problems we aim at selecting the most preferred among the generated Pareto optimal solutions (a subjective selection among objectively determined solutions). In this paper we consider the robustness of the selected Pareto optimal solution in relation to perturbations within weights of the objective functions. For this task we design an integrated approach that can be used in multi-objective discrete and continuous problems using a combination of Monte Carlo simulation and optimization. In the proposed method we introduce measures of robustness for Pareto optimal solutions. In this way we can compare them according to their robustness, introducing one more characteristic for the Pareto optimal solution quality. In addition, especially in multi-objective discrete problems, we can detect the most robust Pareto optimal solution among neighboring ones. A computational experiment is designed in order to illustrate the method and its advantages. It is noteworthy that the Augmented Weighted Tchebycheff proved to be much more reliable than the conventional weighted sum method in discrete problems, due to the existence of unsupported Pareto optimal solutions.     

Assessing solution quality in stochastic programs

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.     

用Mathematica解一个系统的优化设计问题

Mathem atica软件 [1 ] 拥有符号运算、数值计算、和图形演示等广泛的数学计算功能 .本文用Mathematica解决了一个系统的优化设计问题 .通过对各容差搭配方案下目标值 y的方差估计和计算机随机模拟两种方法 ,得到了该系统的最优设计方案 .这两种方法也适用于一般的系统最优设计问题     

The Efficient Allocation of Private Contractors to Public Works

A large, publicly owned corporation has a yearly problem of allocating work to private contractors. The current heuristic procedure used to do this economically on a minicomputer is described. This quick procedure generally does not lead to an optimal solution. The formulation and solution of the problem as an optimization model (an integer programme) is then described. It is then pointed out that this model can be regarded as a minimum cost network flow model showing the optimization problem to be much easier than it at first appeared. Regarding the problem in this manner has the advantage of (i) showing it is possible to optimize very quickly on a minicomputer; (ii) demonstrating that meaningful shadow prices can be derived.     

A constraint generation scheme to probabilistic linear problems with an application to power system expansion planning

In this paper, we first describe a constraint generation scheme for probabilistic mixed integer programming problems. Next, we present a decomposition approach to the peak capacity expansion planning of interconnected hydrothermal generating systems, with bounds on the transmission capacity between the regions. The objective is to minimize investments in generating units and interconnection links, subject to constraints on supply reliability. The problem is formulated as a stochastic integer program. The constraint generation scheme, which is similar to Benders decomposition, is applied in the solution of the peak capacity expansion problem. The master problem in this decomposition scheme is an integer program, solved by implicit enumeration. The operating subproblem corresponds to a stochastic network flow problem, and is solved by a maximum flow algorithm and Monte Carlo simulation. The approach is illustrated through a case study involving the expansion of the system of the Brazilian Southeastern region.     

A stochastic model for operating room planning with elective and emergency demand for surgery

This paper describes a stochastic model for Operating Room (OR) planning with two types of demand for surgery: elective surgery and emergency surgery. Elective cases can be planned ahead and have a patient-related cost depending on the surgery date. Emergency cases arrive randomly and have to be performed on the day of arrival. The planning problem consists in assigning elective cases to different periods over a planning horizon in order to minimize the sum of elective patient related costs and overtime costs of operating rooms. A new stochastic mathematical programming model is first proposed. We then propose a Monte Carlo optimization method combining Monte Carlo simulation and Mixed Integer Programming. The solution of this method is proved to converge to a real optimum as the computation budget increases. Numerical results show that important gains can be realized by using a stochastic OR planning model.     

多周期公用工程系统运行的模型,优化方法与应用

针对多周期公用工程系统的运行优化问题，考虑了设备的启停费用的情况下。建立了混合整数非线性规划模型并证明了最优解的存在性。针对该运行优化问题本将其分解成若干子问题，然后利用改进的Hooke-Jeeves优化算法求解每个子问题。应用于具体实例，其数值结果与其它方法得到的相比。运行时间短，且更适合多周期公用工程问题的求解。