天然气稳态运行优化的混合整数模型及其算法

天然气稳态运行优化问题的难点在于网络结构复杂、规模大、目标函数及约束高度非线性.针对其混合整数非线性规划模型,基于网络约简和线性化技术,建立了线性近似模型,并提出一种新的求解算法.将新算法用于优化我国西部天然气管网系统,结果表明所提算法是有效的.     

Solving mixed integer nonlinear programs by outer approximation

A wide range of optimization problems arising from engineering applications can be formulated as Mixed Integer NonLinear Programming problems (MINLPs). Duran and Grossmann (1986) suggest an outer approximation scheme for solving a class of MINLPs that are linear in the integer variables by a finite sequence of relaxed MILP master programs and NLP subproblems.Their idea is generalized by treating nonlinearities in the integer variables directly, which allows a much wider class of problem to be tackled, including the case of pure INLPs. A new and more simple proof of finite termination is given and a rigorous treatment of infeasible NLP subproblems is presented which includes all the common methods for resolving infeasibility in Phase I.The worst case performance of the outer approximation algorithm is investigated and an example is given for which it visits all integer assignments. This behaviour leads us to include curvature information into the relaxed MILP master problem, giving rise to a new quadratic outer approximation algorithm.An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems. It is possible to develop the theory in an elegant way for a large class of nonsmooth MINLPs based on the use of convex composite functions and subdifferentials, although an interpretation for thel ₁ norm is also given.This work is supported by SERC grant no. SERC GR/F 07972.Corresponding author.     

Solving nonlinear integer programs with large-scale optimization software

This paper describes recent experience in tackling large nonlinear integer programming problems using the MINOS large-scale optimization software. A technique is presented for extending the constrained search approach used in MINOS to exploring integer-feasible solutions once a continuous optimal solution is obtained. Computational experience with this approach is described for two classes of problems: quadratic assignment problems and pipeline network design problems.     

Solving nonlinear integer programs with large-scale optimization software

This paper describes recent experience in tackling large nonlinear integer programming problems using the MINOS large-scale optimization software. A technique is presented for extending the constrained search approach used in MINOS to exploring integer-feasible solutions once a continuous optimal solution is obtained. Computational experience with this approach is described for two classes of problems: quadratic assignment problems and pipeline network design problems.     

Discrete global descent method for discrete global optimization and nonlinear integer programming

A novel method, entitled the discrete global descent method, is developed in this paper to solve discrete global optimization problems and nonlinear integer programming problems. This method moves from one discrete minimizer of the objective function f to another better one at each iteration with the help of an auxiliary function, entitled the discrete global descent function. The discrete global descent function guarantees that its discrete minimizers coincide with the better discrete minimizers of f under some standard assumptions. This property also ensures that a better discrete minimizer of f can be found by some classical local search methods. Numerical experiments on several test problems with up to 100 integer variables and up to 1.38 × 10¹⁰⁴ feasible points have demonstrated the applicability and efficiency of the proposed method.     

An algorithm for mixed integer optimization

This paper introduces a new algorithm for solving mixed integer programs. The core of the method is an iterative technique for changing the representation of the original mixed integer optimization problem. Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202.Mathematics Subject Classification (1991):90C11     

On a pair of nonlinear mixed integer programming problems

We consider maximin and minimax nonlinear mixed integer programming problems which are nonsymmetric in duality sense. Under weaker (pseudo-convex/pseudo-concave) assumptions, we show that the supremum infimum of the maximin problem is greater than or equal to the infimum supremum of the minimax problem. As a particular case, this result reduces to the weak duality theorem for minimax and symmetric dual nonlinear mixed integer programming problems. Further, this is used to generalize available results on minimax and symmetric duality in nonlinear mixed integer programming.     

A decomposition-based solution method for stochastic mixed integer nonlinear programs

This is a summary of the main results presented in the author’s PhD thesis, supervised by D. Conforti and P. Beraldi and defended on March 2005. The thesis, written in English, is available from the author upon request. It describes one of the very few existing implementations of a method for solving stochastic mixed integer nonlinear programming problems based on deterministic global optimization. In order to face the computational challenge involved in the solution of such multi-scenario nonconvex problems, a branch and bound approach is proposed that exploits the peculiar structure of stochastic programming problem.     

A mixed integer programming model for multistage mean–variance post-tax optimization

In this paper, we introduce a mixed integer stochastic programming approach to mean–variance post-tax portfolio management. This approach takes into account of risk in a multistage setting and allows general withdrawals from original capital. The uncertainty on asset returns is specified as a scenario tree. The risk across scenarios is addressed using the probabilistic approach of classical stochastic programming. The tax rules are used with stochastic linear and mixed integer quadratic programming models to compute an overall tax and return-risk efficient multistage portfolio. The incorporation of the risk term in the model provides robustness and leads to diversification over wrappers and assets within each wrapper. General withdrawals and risk aversion have an impact on the distribution of assets among wrappers. Computational results are presented using a study with different scenario trees in order to show the performance of these models.     

Multi-choice mixed integer goal programming optimization for real problems in a sugar and ethanol milling company

Goal Programming (GP) is an important analytical approach devised to solve many realworld problems. The first GP model is known as Weighted Goal Programming (WGP). However, Multi-Choice Aspirations Level (MCAL) problems cannot be solved by current GP techniques. In this paper, we propose a Multi-Choice Mixed Integer Goal Programming model (MCMI-GP) for the aggregate production planning of a Brazilian sugar and ethanol milling company. The MC-MIGP model was based on traditional selection and process methods for the design of lots, representing the production system of sugar, alcohol, molasses and derivatives. The research covers decisions on the agricultural and cutting stages, sugarcane loading and transportation by suppliers and, especially, energy cogeneration decisions; that is, the choice of production process, including storage stages and distribution. The MCMIGP allows decision-makers to set multiple aspiration levels for their problems in which “the more/higher, the better” and “the less/lower, the better” in the aspiration levels are addressed. An application of the proposed model for real problems in a Brazilian sugar and ethanol mill was conducted; producing interesting results that are herein reported and commented upon. Also, it was made a comparison between MCMI GP and WGP models using these real cases.     

A branch-and-bound algorithm for 0–1 parametric mixed integer programming

A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained.     

非线性整数规划的一个近似算法

利用连续总体优化填充函数法的思想，本文设计了非线性整数规划的一个近似算法．首先，给出了非线性整数规划问题离散局部极小解的定义，设计了找离散局部极小解的局部搜索算法；其次，用所设计的局部搜索算法极小化填充函数来找比当前离散局部极小解好的解．本文的近似算法是直接法，且与连续总体优化的填充函数法相比，本文填充函数中的参数易于选取．数值试验表明，本文的近似算法是有效的．     

An algorithmic framework for convex mixed integer nonlinear programs

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.     

Integrating modeling,algorithm design,and computational implementation to solve a large-scale nonlinear mixed integer programming problem

This paper describes the formulation of a nonlinear mixed integer programming model for a large-scale product development and distribution problem and the design and computational implementation of a special purpose algorithm to solve the model. The results described demonstrate that integrating the art of modeling with the sciences of solution methodology and computer implementation provides a powerful approach for attacking difficult problems. The efforts described here were successful because they capitalized on the wealth of existing modeling technology and algorithm technology, the availability of efficient and reliable optimization, matrix generation and graphics software, and the speed of large-scale computer hardware. The model permitted the combined use of decomposition, general linear programming and network optimization within a branch and bound algorithm to overcome mathematical complexity. The computer system reliably found solutions with considerably better objective function values 30 to 50 times faster than had been achieved using general purpose optimization software alone. Throughout twenty months of daily use, the system was credited with providing insights and suggesting strategies that led to very large dollar savings. This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222, by the Center for Business Decision Analysis*, by the University of Texas at Austin, and by the David Bruton, Jr., Centennial Chair in Business Decision Support Systems. Reproduction in whole or in part is permitted for any purpose of the U.S. Government. Center for Business Decision Analysis, Graduate School of Business — GSB 3.126, University of Texas, Austin, Texas 78712, USA.     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

A mixed integer programming model for advanced planning and scheduling (APS)

This paper presents a mixed integer programming (MIP) model which succeeds in a system integration of the production planning and shop floor scheduling problems. The proposed advanced planning and scheduling (APS) model explicitly considers capacity constraints, operation sequences, lead times and due dates in a multi-order environment. The objective of the model is to seek the minimum cost of both production idle time and tardiness or earliness penalty of an order. The output of the model is operation schedules with order starting time and finish time. Numerical result shows that the suggested APS model can favorably produce optimal schedules.     

A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.     

Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method

In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems.     

A nonlinear Lagrangian dual for integer programming

Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.     

Strong formulations for mixed integer programming: A survey

We attempt to motivate and survey recent research on the use of strong valid inequalities and reformulation to solve mixed integer programming problems.