检索结果-内蒙古大学图书馆

Solving linear optimization over arithmetic constraint formula

JOURNAL OF GLOBAL OPTIMIZATION 2017年第1期69卷 69-102页

作者： Chen, Li Lyu, Yinrun Wang, Chong Wu, Jingzheng Zhang, Changyou Min-Allah, Nasro Alhiyafi, Jamal Wang, Yongji Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100190 Peoples R China Chinese Acad Sci Inst Software Lab Parallel Software & Computat Sci Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Univ Dammam CCSIT Dammam Saudi Arabia Chinese Acad Sci Inst Software Natl Engn Res Ctr Fundamental Software Beijing 100190 Peoples R China

Since Balas extended the classical linear programming problem to the disjunctive programming (DP) problem where the constraints are combinations of both logic AND and OR, many researchers explored this optimization problem under various theoretical or application scenarios such as generalized disjunctive programming (GDP), optimization modulo theories (OMT), robot path planning, real-time systems, etc. However, the possibility of combining these differently-described but form-equivalent problems into a single expression remains overlooked. The contribution of this paper is two folded. First, we convert the linear DP/GDP model, linear-arithmetic OMT problem and related application problems into an equivalent form, referred to as the linear optimization over arithmetic constraint formula (LOACF). Second, a tree-search-based algorithm named RS-LPT is proposed to solve LOACF. RS-LPT exploits the techniques of interval analysis and nonparametric estimation for reducing the search tree and lowering the number of visited nodes. Also, RS-LPT alleviates bad construction of search tree by backtracking and pruning dynamically. We evaluate RS-LPT against two most common DP/GDP methods, three state-of-the-art OMT solvers and the disjunctive transformation based method on optimization benchmarks with different types and scales. Our results favor RS-LPT as compared to existing competing methods, especially for large scale cases.

关键词： Linear programming disjunctive programming Optimization modulo theories Search algorithm

来源：评论

学校读者我要写书评

暂无评论

Computational implementation of non-linear convex hull reformulation

引用

COMPUTERS & CHEMICAL ENGINEERING 2007年第7期31卷 856-866页

作者： Sawaya, Nicolas W. Grossmann, Ignacio E. Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA

Lee and Grossmann [Lee, S., & Grossmann, I. E. (2000). New algorithms for nonlinear generalized disjunctive programming. Computers and Chemical Engineering, 24, 2125-2141] have developed a reformulation for nonlinear Generalized disjunctive programming (GDP) problems that obtains from the intersection of the convex hulls of every disjunction. In order to computationally implement this method, it is necessary to reformulate the problem in such a way so as to avoid division by zero in the nonlinear inequalities present amongst the convex bull constraints, while preserving the convex nature of the problem. To accomplish this, we propose to replace the original set of nonlinear constraints by two different sets of convex constraints that circumvent the aforementioned problem and that approximate the original set of constraints exactly at their limit. Furthermore, we compare the two sets of approximating constraints against each other and give rigorous theoretical conditions under which one is superior to the other. Finally, we illustrate the efficiency of both approximations on a variety of numerical examples draw from the Chemical Engineering and Operations Research literature. (C) 2006 Elsevier Ltd. All rights reserved.

关键词： disjunctive programming convex hull mixed-integer non-linear programming

来源：评论

学校读者我要写书评

暂无评论

A decomposition method for distributionally-robust two-stage stochastic mixed-integer conic programs

引用

MATHEMATICAL programming 2022年第1-2期196卷 673-717页

作者： Luo, Fengqiao Mehrotra, Sanjay Northwestern Univ Dept Ind Engn & Management Sci Evanston IL 60208 USA

We develop a decomposition algorithm for distributionally-robust two-stage stochastic mixed-integer convex conic programs, and its important special case of distributionally-robust two-stage stochastic mixed-integer second order conic programs. This generalizes the algorithm proposed by Sen and Sherali [Mathematical programming 106(2): 203-223, 2006]. We show that the proposed algorithm is finitely convergent if the second-stage problems are solved to optimality at incumbent first stage solutions, and solution to an optimization problem to identify worst-case probability distribution is available. The second stage problems can be solved using a branch and cut algorithm, or a parametric cuts based algorithm presented in this paper. The decomposition algorithm is illustrated with an example. Computational results on a stochastic programming generalization of a facility location problem show significant solution time improvements from the proposed approach. Solutions for many models that are intractable for an extensive form formulation become possible. Computational results also show that for the same amount of computational effort the optimality gaps for distributionally robust instances and their stochastic programming counterpart are similar.

关键词： Distributionally robust optimization Two-stage stochastic mixed-integer second-order-cone programming Two-stage stochastic mixed-integer conic programming disjunctive programming Stochastic facility location

来源：评论

学校读者我要写书评

暂无评论

A Mathematical programming Approach for the Optimal Synthesis of Nanofibers through an Electrospinning Process

引用

ACS SUSTAINABLE CHEMISTRY & ENGINEERING 2014年第3期2卷 454-464页

作者： Hernandez-Vargas, Julia Betzabe Gonzalez-Campos, J. Lara-Romero, Javier Maria Ponce-Ortega, Jose Univ Michoacana Chem Engn Dept Morelia 58060 Michoacan Mexico Univ Michoacana Inst Chem & Biol Res Morelia 58060 Michoacan Mexico

This paper presents a general mathematical programming formulation to determine the optimal operating conditions to synthesize nanofibers through an electrospinning process at minimum cost. Several relationships based on experimental data for different polymers to determine the nanofiber diameter and costs are proposed. Also, a general optimization approach is proposed to trade off the relationships between cost and nanofiber diameter. A case study including the specific relationships for three polymers and five operating conditions is presented. The proposed approach is general, and it can be applied to different cases.

关键词： Optimization Elect rospinning Nanofibers Minimum cost and diameter disjunctive programming

来源：评论

学校读者我要写书评

暂无评论

Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems

引用

OPTIMIZATION AND ENGINEERING 2022年第2期23卷 717-747页

作者： Castro, Pedro M. Liao, Qi Liang, Yongtu Univ Lisbon Fac Ciencias Ctr Matemat Aplicacoes Fundamentais & Invest Oper P-1749016 Lisbon Portugal China Univ Petr Beijing Key Lab Urban Oil & Gas Distribut Technol Fuxue Rd 18 Beijing 102249 Peoples R China

Piecewise relaxations are powerful techniques to compute strong dual bounds for (mixed-integer) quadratically constrained problems and provide starting points that can be used by local nonlinear solvers to generate high-quality primal solutions. They work by first partitioning the domain of one of the variables in every quadratic or bilinear term and then selecting the optimal interval in the partition through binary variables. A variety of formulations have been proposed that can be distinguished based on how the number of binary variables scales with the number of intervals. In this paper, we compare linear and logarithmic partitioning schemes that can be derived from the piecewise McCormick relaxation (PCM) or the multiparametric disaggregation technique (MDT). Specifically, we propose MDT for a generic numeric representation system, showing that it becomes a linear partitioning scheme when considering a single digit and varying the basis, and a logarithmic partitioning scheme when fixing the basis and varying the number of digits. Through the solution of 25 benchmark instances for the pooling problem, considering relaxations for the p-, q- and tp-formulations, we show that it is better to rely on the linear scheme from PCM for a small number of intervals and on the logarithmic scheme from base-2 MDT when the number is large. The results also show that significantly stronger dual bounds can be obtained compared to commercial global optimization solvers BARON and GloMIQO.

关键词： Bilinear program Discretization disjunctive programming Quadratic optimization Global optimization Pooling problem

来源：评论

学校读者我要写书评

暂无评论

Strengthening of lower bounds in the global optimization of Bilinear and Concave Generalized disjunctive Programs

引用

COMPUTERS & CHEMICAL ENGINEERING 2010年第6期34卷 914-930页

作者： Ruiz, Juan P. Grossmann, Ignacio E. Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA

This paper is concerned with global optimization of Bilinear and Concave Generalized disjunctive Programs. A major objective is to propose a procedure to find relaxations that yield strong lower bounds. We first present a general framework for obtaining a hierarchy of linear relaxations for nonconvex Generalized disjunctive Programs (GDP). This framework combines linear relaxation strategies proposed in the literature for nonconvex MINLPs with the results of the work by Sawaya and Grossmann (2009) for Linear GDPs. We further exploit the theory behind disjunctive programming by proposing several rules to guide more efficiently the generation of relaxations by considering the particular structure of the problems. Finally, we show through a set of numerical examples that these new relaxations can substantially strengthen the lower bounds for the global optimum, often leading to a significant reduction of the number of nodes when used within a spatial branch and bound framework. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： disjunctive programming Mixed-integer nonlinear programming Global optimization Relaxations

来源：评论

学校读者我要写书评

暂无评论

FACET INEQUALITIES FROM SIMPLE DISJUNCTIONS IN CUTTING PLANE THEORY

引用

MATHEMATICAL programming 1986年第1期34卷 72-83页

作者： SEN, S SHERALI, HD VIRGINIA POLYTECH INST & STATE UNIV DEPT IEORBLACKSBURGVA 24061

The duality between facets of the convex hull of disjunctive sets and the extreme points of reverse polars of these sets is utilized to establish simple rules for the derivation of all facet cuts for simple disjunctions, namely, elementary disjunctions in nonnegative variables. These rules generalize the cut generation procedure underlying polyhedral convexity cuts with negative edge extensions. The latter are also shown to possess some interesting properties with respect to a biextremal problem that maximizes the distance, from the origin, of the nearest point feasible to the cut. A computationally inexpensive procedure is given to generate facet cuts for simple disjunctions which are dominant with respect to any specified preemptive ordering of variables.

关键词： Cutting Planes disjunctive programming

来源：评论

学校读者我要写书评

暂无评论

Optimal constrained control allocation in marine surface vessels with rudders

引用

CONTROL ENGINEERING PRACTICE 2008年第4期16卷 457-464页

作者： Johansen, Tor A. Fugseth, Thomas P. Tondel, Petter Fossen, Thor I. Norwegian Univ Sci & Technol Dept Engn Cybernet NO-7491 Trondheim Norway

A propeller with a rudder can produce a thrust vector within a range of directions and magnitudes in the horizontal plane for low-speed maneuvering and dynamic positioning. The set of attainable thrust vectors is non-convex because significant lift can be produced by the rudder only with forward thrust. It is suggested to decompose the attainable thrust region into a finite union of convex polyhedral sets and a mixed-integer-like convex quadratic programming formulation of the optimal control allocation problem for marine vessels with any number of rudders as well as thrusters and other propulsion devices is derived. Actuator rate and position constraints are explicitly taken into account. Using multi-parametric quadratic programming software, an explicit piecewise linear representation of the least-squares optimal control allocation law is pre-computed. It can therefore be implemented with low computational complexity and high software reliability without the use of real-time optimization. The method is illustrated using a scale model ship in a basin. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： ship control multi-parametric programming disjunctive programming quadratic programming constrained control control allocation

来源：评论

学校读者我要写书评

暂无评论

Global optimization of bilinear programs with a multiparametric disaggregation technique

引用

JOURNAL OF GLOBAL OPTIMIZATION 2013年第4期57卷 1039-1063页

作者： Kolodziej, Scott Castro, Pedro M. Grossmann, Ignacio E. Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA Unidade Modelacaoe Otimizacao Sistemas Lab Nacl Energia & Geol P-1649038 Lisbon Portugal

In this paper, we present the derivation of the multiparametric disaggregation technique (MDT) by Teles et al. (J. Glob. Optim., 2011) for solving nonconvex bilinear programs. Both upper and lower bounding formulations corresponding to mixed-integer linear programs are derived using disjunctive programming and exact linearizations, and incorporated into two global optimization algorithms that are used to solve bilinear programming problems. The relaxation derived using the MDT is shown to scale much more favorably than the relaxation that relies on piecewise McCormick envelopes, yielding smaller mixed-integer problems and faster solution times for similar optimality gaps. The proposed relaxation also compares well with general global optimization solvers on large problems.

关键词： Global optimization Mixed integer linear programming Mixed integer nonlinear programming Quadratic optimization disjunctive programming

来源：评论

学校读者我要写书评

暂无评论

Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2016年第4期64卷 765-784页

作者： Castro, Pedro M. Univ Lisbon Fac Ciencias CMAF CIO P-1749016 Lisbon Portugal

A key element for the global optimization of non-convex mixed-integer bilinear problems is the computation of a tight lower bound for the objective function being minimized. Multiparametric disaggregation is a technique for generating a mixed-integer linear relaxation of a bilinear problem that works by discretizing the domain of one of the variables in every bilinear term according to a numeric representation system. This can be done up to a certain accuracy level that can be different for each discretized variable so as to adjust the number of significant digits to their range of values and give all variables the same importance. We now propose a normalized formulation (NMDT) that achieves the same goal using a common setting for all variables, which is equivalent to the number of uniform partitions in a closely related, piecewise McCormick (PCM) approach. Through the solution of several benchmark problems from the literature involving four distinct problem classes, we show that the computational performance of NMDT is already better than PCM for ten partitions, with the difference rising quickly due to the logarithmic versus linear growth in the number of binary variables with the number of partitions. The results also show that a global optimization solver based on the proposed relaxation compares favorably with commercial solvers BARON and GloMIQO.

关键词： Mixed-integer nonlinear programming Quadratic optimization disjunctive programming Algorithm Process networks

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：