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

A Criterion Space Search Algorithm for biobjective integer programming: The Balanced Box Method

INFORMS JOURNAL ON COMPUTING 2015年第4期27卷 735-754页

作者： Boland, Natashia Charkhgard, Hadi Savelsbergh, Martin Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Univ Newcastle Sch Math & Phys Sci Callaghan NSW 2308 Australia

We present a new criterion space search algorithm, the balanced box method, for finding all nondominated points of a biobjective integer program. The method extends the box algorithm, is easy to implement, and converges quickly to the complete set of nondominated points. Because the method maintains, at any point in time, a diverse set of nondominated points, it is ideally suited for fast approximation of the efficient frontier. In addition, we present several enhancements of the well-known. epsilon-constraint, augmented weighted Tchebycheff, and perpendicular search methods. An extensive computational study, using instances from different classes of combinatorial optimization problems, demonstrates the efficacy of the balanced box method.

关键词： biobjective integer programming criterion space search algorithm balanced box method

来源：评论

学校读者我要写书评

暂无评论

Variants of the ε-constraint method for biobjective integer programming problems: application to p-median-cover problems

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2018年第2期87卷 251-283页

作者： Saez-Aguado, Jesus Camelia Trandafir, Paula Univ Valladolid Dept Stat & Operat Res Paseo Belen 7 E-47011 Valladolid Spain Univ Publ Navarra Dept Stat & Operat Res Avda Tarazona S-N Tudela 31500 Spain

We conduct an in-depth analysis of the epsilon-constraint method (ECM) for finding the exact Pareto front for biobjective integer programming problems. We have found up to six possible different variants of the ECM. We first discuss the complexity of each of these variants and their relationship with other exact methods for solving biobjective integer programming problems. By extending some results of Neumayer and Schweigert (OR Spektrum 16: 267-276, 1994), we develop two variants of the ECM, both including an augmentation term and requiring N + 1 integer programs to be solved, where N is the number of nondominated points. In addition, we present another variant of the ECM, based on the use of elastic constraints and also including an augmentation term. This variant has the same complexity, namely N + 1, which is the minimum reached for any exact method. A comparison of the different variants is carried out on a set of biobjective location problems which we call p-median-cover problems;these include the objectives of the p-median and the maximal covering problems. As computational results show, for this class of problems, the augmented ECM with elastic constraint is the most effective variant for finding the Pareto front in an exact manner.

关键词： biobjective integer programming Epsilon-constraint method p-Median-cover problem

来源：评论

学校读者我要写书评

暂无评论

AN EXACT ALGORITHM FOR biobjective integer programming PROBLEMS

AN EXACT ALGORITHM FOR BIOBJECTIVE INTEGER PROGRAMMING PROBL...

引用

作者： Saliha Ferda Dogan Bilkent University

学位级别：硕士

We propose an exact algorithm to find all nondominated points of biobjective integer programming problems, which arise in various applications of operations research. The algorithm is based on dividing objective space into regions (boxes) and searching them by solving Pascoletti-Serafini scalarizations with fixed direction vector. We develop variants of the algorithm, where the choice of the scalarization model parameters differ; and demonstrate their performance through computational experiments both as exact algorithms and as solution approaches under time restriction. The results of our experiments show the satisfactory behaviour of our algorithm, especially with respect to the number of mixed integer programming problems solved compared to an existing approach. The experiments also demonstrate that different variants have advantages in different aspects: while some variants are quicker in finding the whole set of nondominated solutions, other variants return good-quality solutions in terms of representativeness when run under time restriction.

关键词： biobjective integer programming Pascoletti-Serafini scalarization Algorithms

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for biobjective integer programming problems

引用

COMPUTERS & OPERATIONS RESEARCH 2021年 132卷 105298-105298页

作者： Dogan, Saliha Ferda Karsu, Ozlem Ulus, Firdevs Bilkent Univ Dept Ind Engn TR-06800 Ankara Turkey

We propose an exact algorithm for solving biobjective integer programming problems, which arise in various applications of operations research. The algorithm is based on solving Pascoletti-Serafini scalarizations to search specified regions (boxes) in the objective space and returns the set of nondominated points. We implement the algorithm with different strategies, where the choices of the scalarization model parameters and splitting rule differ. We then derive bounds on the number of scalarization models solved;and demonstrate the performances of the variants through computational experiments both as exact algorithms and as solution approaches under time restriction. The experiments demonstrate that different strategies have advantages in different aspects: while some are quicker in finding the whole set of nondominated solutions, others return good-quality solutions in terms of representativeness when run under time restriction. We also compare the proposed approach with existing algorithms. The results of our experiments show the satisfactory behaviour of our algorithm, especially when run under time limit, as it achieves better coverage of the whole frontier with a smaller number of solutions compared to the existing algorithms.

关键词： biobjective integer programming Pascoletti-Serafini scalarization Algorithms

来源：评论

学校读者我要写书评

暂无评论

A new directed branching heuristic for the pq-median problem

引用

Location Science 1998年第1-4期6卷 1-23页

作者： Alminyana, M. Borrás, F. Pastor, J.T. Depto. Estadistica y Matemat. Apl. Universidad Miguel Hernández 03202-Elche (Alicante) Spain

The pq-median problem, of Serra and ReVelle seeks to locate hierarchical facilities at two levels so as to obtain a coherent structure. Coherence requires that the entire area assigned to a facility at the inferior level be assigned to one and the same facility at the next higher level of the hierarchy. Although optimal solutions can be obtained by means of solving biobjective integer linear programs, large problems are likely to require heuristics. Here we present a new heuristic that combines the generation of points, by means of a ́directed́ branching procedure with the final selection of points, using the FDH-technique. We further compare our new heuristic with the two most relevant heuristics proposed by Serra and ReVelle. © 1999 Elsevier Science Ltd. All rights reserved.

关键词： biobjective integer programming FDH Heuristics Location pq-msdian problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：