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

Decomposition approach for the global minimization of biconcave functions over polytopes

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1996年第3期88卷 561-583页

作者： Horst, R Thoai, NV INST MATH HANOI 10000VIETNAM

A decomposition approach is proposed for minimizing biconcave functions over polytopes. Important special cases include concave minimization, bilinear and indefinite quadratic programming for which new algorithms result. The approach introduces a new polyhedral partition and combines branch-and-bound techniques, outer approximation, and projection of polytopes in a suitable way.

关键词： global optimization biconcave programming concave minimization bilinear and quadratic programming branch-and-bound algorithms outer approximations

来源：评论

学校读者我要写书评

暂无评论

Utility function programs and optimization over the efficient set in multiple-objective decision making

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1997年第3期92卷 605-631页

作者： Horst, R Thoai, NV INST MATH HANOI 10000VIETNAM

Natural basic concepts in multiple-objective optimization lead to difficult multiextremal global optimization problems. Examples include detection of efficient points when nonconvexities occur, and optimization of a linear function over the efficient set in the convex (even linear) case. Assuming that a utility function exists allows one to replace in general the multiple-objective program by a single, nonconvex optimization problem, which amounts to a minimization over the efficient set when the utility function is increasing. A new algorithm is discussed for this utility function program which, under natural mild conditions, converges to an E-approximate global solution in a finite number of iterations. Applications include linear, convex, indefinite quadratic, Lipschitz, and d.c. objectives and constraints.

关键词： multiple-objective optimization utility function programs global optimization branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

ADAPTIVE PARTITIONED RANDOM SEARCH TO GLOBAL OPTIMIZATION

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 1994年第11期39卷 2235-2244页

作者： TANG, ZB HARVARD UNIV DIV APPL SCICAMBRIDGEMA

This paper considers global optimization (maximization) problems. It emphasizes that for a generic function, it is inherently difficult to find the global optimum within a finite number of function evaluations. Therefore, it is more realistic to talk about maximizing the expectation of the largest function value that can be obtained for a given number of function evaluations. Based on decision theoretic argument, we propose that the search region of the objective function be partitioned into certain number of subregions. Using the sampled function values from each subregion, estimators are derived to determine how ''promising'' each subregion is. The most promising subregion is then further partitioned. In some sense, the adaptive partitioned random search (APRS) proposed in this paper is a tree search type of algorithms like branch-and-bound algorithms. The APRS, however, abandons the idea of finding the subregion where the global maximum is likely located in the first place. Instead it seeks the subregion where the largest improvement of the performance is most likely to be obtained if more function evaluations are taken. The APRS in general can provide a much better-than-average solution within a modest number of function evaluations. In fact, our various numerical experiments have shown that in comparison with the crude random search (CRS) in terms of number of function evaluations, the APRS can be at least hundreds of times more efficient. The simplicity and robustness of the APRS in terms of easy implementation and minimum assumptions on the objective function are also demonstrated.

关键词： adaptive systems optimisation search problems adaptive partitioned random search branch-and-bound algorithms decision theory expectation maximization function evaluations global maximization global optimization sampled function values search region parti subregion Adaptive systems branch and bound algorithms tabu search Global optimization Function evaluation Decision Theory

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第2期279卷 308-319页

作者： Chassein, Andre Goerigk, Marc Kurtz, Jannis Poss, Michael Deutsch Post DHL Grp Data Analyt Ctr Excellence Bonn Germany Univ Siegen Network & Data Sci Management Siegen Germany Rhein Westfal TH Aachen Dept Math Aachen Germany Univ Montpellier LIRMM CNRS Montpellier France

We consider robust combinatorial optimization problems where the decision maker can react to a scenario by choosing from a finite set of k solutions. This approach is appropriate for decision problems under uncertainty where the implementation of decisions requires preparing the ground. We focus on the case that the set of possible scenarios is described through a budgeted uncertainty set and provide three algorithms for the problem. The first algorithm solves heuristically the dualized problem, a non convex mixed-integer non-linear program (MINLP), via an alternating optimization approach. The second algorithm solves the MINLP exactly for k = 2 through a dedicated spatial branch-and-bound algorithm. The third approach enumerates k-tuples, relying on strong bounds to avoid a complete enumeration. We test our methods on shortest path instances that were used in the previous literature and on randomly generated knapsack instances, and find that our methods considerably outperform previous approaches. Many instances that were previously not solved within hours can now be solved within few minutes, often even faster. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Robust optimization k-adaptability Budgeted uncertainty branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving a class of multiplicative programs with 0-1 knapsack constraints

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1999年第1期103卷 121-135页

作者： Kuno, T Univ Tsukuba Inst Informat Sci & Elect Ibaraki Osaka Japan

We develop a branch-and-bound algorithm to solve a nonlinear class of 0-1 knapsack problems. The objective function is a product of m greater than or equal to 2 affine functions, whose variables are mutually exclusive. The branching procedure in the proposed algorithm is the usual one, but the bounding procedure exploits the special structure of the problem and is implemented through two stages: the first stage is based on linear programming relaxation;the second stage is based on Lagrangian relaxation. Computational results indicate that the algorithm is promising.

关键词： multiplicative programming 0-1 knapsack problems concave minimization branch-and-bound algorithms Lagrangian relaxation

来源：评论

学校读者我要写书评

暂无评论

Duality bound method for the general quadratic programming problem with quadratic constraints

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2000年第2期107卷 331-354页

作者： Thoai, NV Univ Trier Dept Math Trier Germany

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs;(ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope;(iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.

关键词： general quadratic programming problem with quadratic constraints global optimization branch-and-bound algorithms duality bounds

来源：评论

学校读者我要写书评

暂无评论

Solving large Steiner Triple Covering Problems

引用

OPERATIONS RESEARCH LETTERS 2011年第2期39卷 127-131页

作者： Ostrowski, James Linderoth, Jeff Rossi, Fabrizio Smriglio, Stefano Univ Aquila Dipartimento Informat I-67010 Coppito AQ Italy Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Waterloo Dept Management Sci Waterloo ON N2L 3G1 Canada

Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to highly symmetric and computationally challenging set covering problems. The largest instance solved so far corresponds to a Steiner Tripe System of order 81. We present optimal solutions for systems of orders 135 and 243. These are computed by a tailored implementation of constraint orbital branching, a method designed to exploit symmetry in integer programs. (c) 2011 Elsevier B.V. All rights reserved.

关键词： Integer programming Symmetry branch-and-bound algorithms Steiner Triple Systems

来源：评论

学校读者我要写书评

暂无评论

Orbital branching

引用

MATHEMATICAL PROGRAMMING 2011年第1期126卷 147-178页

作者： Ostrowski, James Linderoth, Jeff Rossi, Fabrizio Smriglio, Stefano Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18015 USA Univ Aquila Dipartimento Informat I-67100 Laquila Italy

We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry that is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard integer programming software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as isomorphism pruning and significantly better than a state-of-the-art commercial solver on symmetric integer programs.

关键词： Integer programming Symmetry branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

On linear programming relaxations for solving polynomial programming problems

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 99卷 67-77页

作者： Dalkiran, Evrim Ghalami, Laleh Wayne State Univ Ind & Syst Engn 4815 Fourth St Detroit MI 48202 USA

This paper studies linear programming (LP) relaxations for solving polynomial programming problems. A polynomial programming problem can be equivalently formulated as a quadratically constrained quadratic program (QCQP) by introducing new variables that represent nonlinear monomials and substituting them within the original formulation. Whereas Reformulation-Linearization Technique (RLT)-based LP relaxations constructed for the original formulation are tight, the relaxations generated using the equivalent lower degree formulations are smaller and require less computational effort to optimize in comparison to the effort the former requires. In this study, we analyze the strength and tractability of the standard RLT, the J-set, and recursive McCormick relaxations for polynomial programming problems, and identify the superior relaxation depending on the problem characteristics. Extensive computational results are provided to demonstrate the relative effectiveness of the standard RLT, J-set, and recursive McCormick algorithms using problems from the literature and randomly generated test instances. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Reformulation-Linearization Technique (RLT) J-set relaxation McCormick inequalities Polynomial programming problems Linear programming relaxations branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Multi-way distance join queries in spatial databases

引用

GEOINFORMATICA 2004年第4期8卷 373-402页

作者： Corral, A Manolopoulos, Y Theodoridis, Y Vassilakopoulos, M Univ Almeria Dept Languages & Computat Almeria 04120 Spain Aristotle Univ Thessaloniki Dept Informat GR-54006 Thessaloniki Greece Univ Piraeus Dept Informat GR-18534 Piraeus Greece TEI Thessaloniki Dept Informat GR-54101 Thessaloniki Greece

Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The D-distance-value- of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the K n-tuples between n spatial datasets that have the smallest D-distance-values, the so-called K-multi-way distance join query (K-MWDJQ), where each set is indexed by an R-tree-based structure. This query can be viewed as an extension of K-closest-pairs query (K-CPQ) [8] for n inputs. In addition, a recursive non-incremental branch-and-bound algorithm following a depth-first search for processing synchronously all inputs without producing any intermediate result is proposed. Enhanced pruning techniques are also applied to n R-trees nodes in order to reduce the total response time and the number of distance computations of the query. Due to the exponential nature of the problem, we also propose a time-based approximate version of the recursive algorithm that combines approximation techniques to adjust the quality of the result and the global processing time. Finally, we give a detailed experimental study of the proposed algorithms using real spatial datasets, highlighting their performance and the quality of the approximate results.

关键词： spatial databases branch-and-bound algorithms distance join queries R-trees approximate techniques

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：