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

Some cut-generating functions for second-order conic sets

DISCRETE OPTIMIZATION 2017年 24卷 51-65页

作者： Santana, Asteroide Dey, Santanu S. Georgia Inst Technol ISyE 765 Ferst Dr NW Atlanta GA 30332 USA

In this paper, we study cut generating functions for conic sets. Our first main result shows that if the conic set is bounded, then cut generating functions for integer linear programs can easily be adapted to give the integer hull of the conic integer program. Then we introduce a new class of cut generating functions which are non decreasing with respect to second-order cone. We show that, under some minor technical conditions, these functions together with integer linear programming-based functions are sufficient to yield the integer hull of intersections of conic sections in R-2. (C) 2016 Elsevier B.V. All rights reserved.

关键词： integer conic programming integer hull of conic set Cut generating function Subadditive function Second-order cone

来源：评论

学校读者我要写书评

暂无评论

Strong convex relaxations for quadratically constrained quadratic programs

Strong convex relaxations for quadratically constrained quad...

引用

作者： Santana, Asteroide Georgia Institute of Technology

学位级别：博士

Many classes of mixed integer nonlinear programs (MINLPs) are challenging to solve. A common approach to solve a MINLP is to use a combination of a branch-and-bound algorithm together with convexification and/or cutting-planes. In this thesis, we develop new convexification/cutting-plane techniques for two classes of MINLPs: mixed integer conic programs and (non-convex) quadratically constrained quadratic programs. We begin by generalizing a number of important well known results in mixed inte- ger linear programming to the context of mixed integer conic programming. In particu- lar, we introduce a new class of cut generating functions and show that, under some mi- nor technical conditions, these functions, together with integer linear programming-based functions, are sufficient to yield the integer hull of intersections of conic sections in the two-dimensional space. We then focus on the representability of the convex hull of various sets derived from studying substructures of quadratically constrained quadratic programs. One of our main results shows that the convex hull of a single quadratic constraint intersected with a bounded polyhedron is second-order cone representable. For the bipartite bilinear program, a special case of the quadratically constrained quadratic program, we even design and implement an algorithm to obtain this convex hull. In addition, we introduce a new application of the bipartite bilinear program from civil engineering and report very successful computational results for this instance class. Finally, we look at the quadratically constrained quadratic program from a rank-1 per- spective, i. e., casting the non-convexity of the problem using rank-1 constraints. This ap- proach leads us to identify important substructures from which we derive and convexify several classes of sets. We then apply our results to the well-known pooling problem to obtain successful computational results.

关键词： Convex hull Rank-1 constraints Pooling problem Quadratically constrained quadratic programs Bilinear programming Branching rule integer conic programming integer hull of conic set Cut generating function Subadditive function Second-order cone

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：