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

New multi-commodity flow formulations for the pooling problem

JOURNAL OF GLOBAL OPTIMIZATION 2016年第4期66卷 669-710页

作者： Boland, Natashia Kalinowski, Thomas Rigterink, Fabian Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA Univ Newcastle Sch Math & Phys Sci Newcastle NSW 2308 Australia

The pooling problem is a nonconvex nonlinear programming problem with numerous applications. The nonlinearities of the problem arise from bilinear constraints that capture the blending of raw materials. bilinear constraints are well-studied and significant progress has been made in solving large instances of the pooling problem to global optimality. This is due in no small part to reformulations of the problem. Recently, Alfaki and Haugland proposed a multi-commodity flow formulation of the pooling problem based on input commodities. The authors proved that the new formulation has a stronger linear relaxation than previously known formulations. They also provided computational results which show that the new formulation outperforms previously known formulations when used in a global optimization solver. In this paper, we generalize their ideas and propose new multi-commodity flow formulations based on output, input and output and (input, output)-commodities. We prove the equivalence of formulations, and we study the partial order of formulations with respect to the strength of their LP relaxations. In an extensive computational study, we evaluate the performance of the new formulations. We study the trade-off between disaggregating commodities and therefore increasing the size of formulations versus strengthening the relaxed linear programs and improving the computational performance of the nonlinear programs. We provide computational results which show that output commodities often outperform input commodities, and that disaggregating commodities further only marginally strengthens the linear relaxations. In fact, smaller formulations often show a significantly better performance when used in a global optimization solver.

关键词： Pooling problem bilinear programming Nonlinear programming Linear relaxation Global optimization Blending

来源：评论

学校读者我要写书评

暂无评论

Exact and heuristic solutions of the global supply chain problem with transfer pricing

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第3期202卷 864-879页

作者： Perron, Sylvain Hansen, Pierre Le Digabel, Sebastien Mladenovic, Nenad Gerad Montreal PQ H3T 2A7 Canada HEC Montreal Montreal PQ H3T 2A7 Canada Gerad Montreal PQ H3C 3A7 Canada Ecole Polytech Montreal PQ H3C 3A7 Canada Gerad Uxbridge UB8 3PH Middx England Brunel Univ Uxbridge UB8 3PH Middx England

We examine the example of a multinational corporation that attempts to maximize its global after tax profits by determining the flow of goods, the transfer prices, and the transportation cost allocation between each of its subsidiaries. Vidal and Goetschalckx [Vidal, C.J., Goetschalckx, M., 2001. A global supply chain model with transfer pricing and transportation cost allocation. European journal of Operational Research 129 (1), 134-158] proposed a bilinear model of this problem and solved it by an Alternate heuristic. We propose a reformulation of this model reducing the number of bilinear terms and accelerating considerably the exact solution. We also present three other Solution methods: an implementation of Variable Neighborhood Search (VNS) designed for any bilinear model, an implementation of VNS specifically designed for the problem considered here and an exact method based on a branch and cut algorithm. The solution methods are tested on artificial instances. These results show that our implementation of VNS outperforms the two other heuristics. The exact method found the optimal solution of all small instances and of 26% of medium instances. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Metaheuristics Alternate heuristic Supply chain management Transfer pricing bilinear programming Branch and cut

来源：评论

学校读者我要写书评

暂无评论

An improved linearization strategy for zero-one quadratic programming problems

引用

OPTIMIZATION LETTERS 2007年第1期1卷 33-47页

作者： Sherali, Hanif D. Smith, J. Cole Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Virginia Polytech Inst & State Univ Grado Dept Ind & Syst Engn 0118 Blacksburg VA 24061 USA

We present a new linearized model for the zero-one quadratic programming problem, whose size is linear in terms of the number of variables in the original nonlinear problem. Our derivation yields three alternative reformulations, each varying in model size and tightness. We show that our models are at least as tight as the one recently proposed in [7], and examine the theoretical relationship of our models to a standard linearization of the zero-one quadratic programming problem. Finally, we demonstrate the efficacy of solving each of these models on a set of randomly generated test instances.

关键词： Integer programming Quadratic programming bilinear programming Linearization Reformulation-linearization technique (RLT)

来源：评论

学校读者我要写书评

暂无评论

The inverse optimal value problem

引用

MATHEMATICAL programming 2005年第1期102卷 91-110页

作者： Ahmed, S Guan, YP Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost vectors, determine a cost vector such that the corresponding optimal objective value of the linear program is closest to the desired value. The above problem, referred here as the inverse optimal value problem, is significantly different from standard inverse optimization problems that involve determining a cost vector for a linear program such that a pre-specified solution vector is optimal. In this paper, we show that the inverse optimal value problem is NP-hard in general. We identify conditions under which the problem reduces to a concave maximization or a concave minimization problem. We provide sufficient conditions under which the associated concave minimization problem and, correspondingly, the inverse optimal value problem is polynomially solvable. For the case when the set of feasible cost vectors is polyhedral, we describe an algorithm for the inverse optimal value problem based on solving linear and bilinear programming problems. Some preliminary computational experience is reported.

关键词： inverse optimization complexity linear programming bilinear programming

来源：评论

学校读者我要写书评

暂无评论

A strong P-formulation for global optimization of industrial water-using and treatment networks

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第2期89卷 477-507页

作者： Cheng, Xin Li, Xiang Queens Univ Dept Chem Engn 19 Div St Kingston ON K7L 3N6 Canada Zhejiang Univ Coll Control Sci & Engn 866 Yuhangtang Rd Hangzhou 310058 Zhejiang Peoples R China

The problem of finding the optimal flow allocation within an industrial water-using and treatment network can be formulated into nonconvex nonlinear program or nonconvexmixedinteger nonlinear program. The efficiency of global optimization of the nonconvex program relies heavily on the strength of the problem formulation. In this paper, we propose a variant of the commonly used P-formulation, called the P*-formulation, for the water treatment network (WTN) and the total water network (TWN) that includes water-using and water treatment units. For either type of networks, we prove that the P*-formulation is at least as strong as the P-formulation under mild bound consistency conditions. We also prove for either type of networks that the P*-formulation is at least as strong as the split-fraction based formulation (called SF-formulation) under certain bound consistency conditions. The computational study shows that the P*-formulation significantly outperforms the P- and the SF-formulations. For some problem instances, the P*- formulation is faster than the other two formulations by several orders of magnitudes.

关键词： Global optimization Integrated water networks bilinear programming Pooling problem Wastewater treatment

来源：评论

学校读者我要写书评

暂无评论

Approximate solution of mp-MILP problems using piecewise affine relaxation of bilinear terms

引用

COMPUTERS & CHEMICAL ENGINEERING 2014年 61卷 136-155页

作者： Wittmann-Hohlbein, Martina Pistikopoulos, Efstratios N. Univ London Imperial Coll Sci Technol & Med Dept Chem Engn Ctr Proc Syst Engn London SW7 2BY England

We propose an approximate solution strategy for multi-parametric mixed integer linear programming (mp-MILP) problems with parameter dependency at multiple locations in the model. A two-stage solution strategy, consisting of an approximation stage and a multi-parametric programming stage, is introduced. At the approximation stage, surrogate mp-MILP models are derived by overestimating bilinear terms in the constraints over an ab initio partitioning of the domain. We then incorporate piecewise affine relaxation based models using a linear partitioning scheme and a logarithmic partitioning scheme, respectively. The models are tuned by the number of partitions chosen. Problem sizes of the varied models, and computational requirements for the algorithmic procedure are compared. The conservatism of the suboptimal solution of the mp-MILP problem for the piecewise affine relaxation based two-stage method is discussed. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Multi-parametric programming Mixed-integer programming bilinear programming

来源：评论

学校读者我要写书评

暂无评论

A discretization-based approach for the optimization of the multiperiod blend scheduling problem

引用

COMPUTERS & CHEMICAL ENGINEERING 2013年 53卷 122-142页

作者： Kolodziej, Scott P. Grossmann, Ignacio E. Furman, Kevin C. Sawaya, Nicolas W. Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA ExxonMobil Upstream Res Co Houston TX 77098 USA ExxonMobil Gas & Power Mkt Co Houston TX 77002 USA

In this paper, we introduce a new generalized multiperiod scheduling version of the pooling problem to represent time varying blending systems. A general nonconvex MINLP formulation of the problem is presented. The primary difficulties in solving this optimization problem are the presence of bilinear terms, as well as binary decision variables required to impose operational constraints. An illustrative example is presented to provide unique insight into the difficulties faced by conventional MINLP approaches to this problem, specifically in finding feasible solutions. Based on recent work, a new radix-based discretization scheme is developed with which the problem can be reformulated approximately as an MILP, which is incorporated in a heuristic procedure and in two rigorous global optimization methods, and requires much less computational time than existing global optimization solvers. Detailed computational results of each approach are presented on a set of examples, including a comparison with other global optimization solvers. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Pooling problem Mixed-integer nonlinear programming bilinear programming Global optimization Petroleum operations

来源：评论

学校读者我要写书评

暂无评论

Enumeration approach for linear complementarity problems based on a reformulation-linearization technique

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1998年第2期99卷 481-507页

作者： Sherali, HD Krishnamurthy, RS Al-Khayyal, FA Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA SABRE Technol Solut Ft Worth TX USA

In this paper, we consider the linear complementarity problem (LCP) and present a global optimization algorithm based on an application of the reformulation-linearization technique (RLT). The matrix M associated with the LCP is not assumed to possess any special structure. In this approach, the LCP is formulated first as a mixed-integer 0-1 bilinear programming problem. The RLT scheme is then used to derive a new equivalent mixed-integer linear programming formulation of the LCP. An implicit enumeration scheme is developed that uses Lagrangian relaxation, strongest surrogate and strengthened cutting planes, and a heuristic, designed to exploit the strength of the resulting linearization. Computational experience on various test problems is presented.

关键词： linear complementarity problem bilinear programming implicit enumeration Lagrangian relaxation reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2018年第1期70卷 33-59页

作者： Xu, Guanglin Burer, Samuel Univ Iowa Dept Management Sci Iowa City IA 52242 USA

We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which in turn leads to a class of tractable, semidefinite-based approximations that are at least as strong as the affine policy. We investigate several examples from the literature demonstrating that our tractable approximations significantly improve the affine policy. In particular, our approach solves exactly in polynomial time a class of instances of increasing size for which the affine policy admits an arbitrarily large gap.

关键词： Two-stage adjustable robust optimization Robust optimization bilinear programming Non-convex quadratic programming Semidefinite programming Copositive programming

来源：评论

学校读者我要写书评

暂无评论

New SOCP relaxation and branching rule for bipartite bilinear programs

引用

OPTIMIZATION AND ENGINEERING 2019年第2期20卷 307-336页

作者： Dey, Santanu S. Santana, Asteroide Wang, Yang Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Georgia Inst Technol Sch Civil & Environm Engn Atlanta GA 30332 USA

A bipartite bilinear program (BBP) is a quadratically constrained quadratic optimization problem where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second order cone representable (SOCP) relaxation for BBP, which we show is stronger than the standard SDP relaxation intersected with the boolean quadratic polytope. We then propose a new branching rule inspired by the construction of the SOCP relaxation. We describe a new application of BBP called as the finite element model updating problem, which is a fundamental problem in structural engineering. Our computational experiments on this problem class show that the new branching rule together with an polyhedral outer approximation of the SOCP relaxation outperforms a state-of-the-art commercial global solver in obtaining dual bounds.

关键词： Convex hull bilinear programming Branching rule

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：