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

Towards effective exact methods for the Maximum Balanced Biclique Problem in bipartite graphs

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期269卷 834-843页

作者： Zhou, Yi Rossi, Andre Hao, Jin-Kao Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 617731 Sichuan Peoples R China Univ Angers LERIA 2 Bd Lavoisier F-49045 Angers France Inst Univ France 1 Rue Descartes F-75231 Paris France

The Maximum Balanced Biclique Problem (MBBP) is a prominent model with numerous applications. Yet. the problem is NP-hard and thus computationally challenging. We propose novel ideas for designing effective exact algorithms for MBBP in bipartite graphs. First, an Upper Bound Propagation (UBP) procedure to pre-compute an upper bound involving each vertex is introduced. Then we extend a simple Branchand-Bound (B&B) algorithm by integrating the pre-computed upper bounds. Based on UBP, we also study a new integer linear programming model of MBBP which is more compact than an existing formulation (Dawande, Keskinocak, Swaminathan, & Tayur, 2001). We introduce new valid inequalities induced from the upper bounds to tighten these mathematical formulations for MBBP. Experiments with random bipartite graphs demonstrate the efficiency of the extended B&B algorithm and the valid inequalities generated on demand. Further tests with 30 real-life instances show that, for at least three very large graphs, the new approaches improve the computational time with four orders of magnitude compared to the original B&B. (C) 2018 E(C)sevier B.V. All rights reserved.

关键词： Combinatorial optimization Clique exact algorithms Techniques for tight bounds Mathematical formulation

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms to minimize workload balancing criteria on identical parallel machines

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 93卷 123-134页

作者： Schwerdfeger, Stefan Walter, Rico Friedrich Schiller Univ Jena Chair Management Sci Carl Zeiss Str 3 D-07793 Jena Germany

In Schwerdfeger and Walter (2016), we proposed a subset sum based improvement procedure (denoted by LS) for solving the problem of minimizing the normalized sum of squared workload deviations on m identical machines. In its core, the algorithm builds on an exact procedure (denoted by WB3) for the case of m = 3 machines. Although this approach proved to be superior to existing procedures in terms of solution quality, we identified room for further improvements. Building upon our prior work, in this follow-up paper we suggest an enhanced version of WB3 that leads to a significant speed-up of several orders of magnitude and we considerably improve on the performance of LS on difficult instances where the ratio of the number of jobs to the number of machines is small. Moreover, we investigate a simple surrogate balancing measure that can also be optimized by our algorithms with only a slight modification. Results of a comprehensive computational study on a large set of benchmark as well as random test instances demonstrate the effectiveness of the improved algorithms. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Scheduling Identical parallel machines Workload balancing NSSWD-criterion exact algorithms Heuristics

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the Blocks Relocation Problem with new lower bounds

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 99卷 206-217页

作者： Yucra Quispe, Kent E. Lintzmayer, Carla N. Xavier, Eduardo C. Univ Estadual Campinas Inst Comp Campinas SP Brazil Fed Univ ABC Ctr Math Computat & Cognit Santo Andre SP Brazil

The Blocks Relocation Problem is an important problem in storage systems. An input instance for it consists of a set of blocks distributed in stacks where each block is identified by a retrieval number and each stack has a same maximum height limit. The objective is to retrieve all the blocks respecting their retrieval order and performing the minimum number of relocations. Only blocks at the top of a stack can be moved: either a block is retrieved, if it has the highest retrieval priority among the stacked blocks, or it is relocated to the top of another stack. Solving this problem is critical in storage systems because it saves operational time and resources. In this paper, we present two new lower bounds for the number of relocations of an optimal solution. We implemented an exact iterative deepening A* algorithm using these new proposed lower bounds and other well-known lower bounds from the literature. We performed several computational experiments to show that the new lower bounds improve the performance of the exact algorithm, solving to optimality more instances than when using other lower bounds when given the same amount of time. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Blocks Relocation Problem Container Relocation Problem exact algorithms Lower bounds

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Edge Domination

引用

ALGORITHMICA 2012年第4期64卷 535-563页

作者： van Rooij, Johan M. M. Bodlaender, Hans L. Univ Utrecht Inst Informat & Comp Sci NL-3508 TB Utrecht Netherlands

An edge dominating set in a graph G=(V,E) is a subset of the edges DaS dagger E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is NP-hard. We present a faster exact exponential time algorithm for this problem. Our algorithm uses O(1.3226 (n) ) time and polynomial space. The algorithm combines an enumeration approach of minimal vertex covers in the input graph with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwisely. In each of these refinement steps, the worst cases in the measure and conquer analysis of the current algorithm are reconsidered and a new branching strategy is proposed on one of these worst cases. In this way a series of algorithms appears, each one slightly faster than the previous one, ending in the O(1.3226 (n) ) time algorithm. For each algorithm in the series, we also give a lower bound on its running time. We also show that the related problems: minimum weight edge dominating set, minimum maximal matching and minimum weight maximal matching can be solved in O(1.3226 (n) ) time and polynomial space using modifications of the algorithm for edge dominating set. In addition, we consider the matrix dominating set problem which we solve in O(1.3226 (n+m) ) time and polynomial space for nxm matrices, and the parametrised minimum weight maximal matching problem for which we obtain an O (au)(2.4179 (k) ) time and space algorithm.

关键词： Edge dominating set Minimum maximal matching exact algorithms Exponential time algorithms Measure and conquer

来源：评论

学校读者我要写书评

暂无评论

Minimum tiling of a rectangle by squares

引用

ANNALS OF OPERATIONS RESEARCH 2018年第2期271卷 831-851页

作者： Monaci, Michele dos Santos, Andre Gustavo Univ Bologna DEI Viale Risorgimento 2 I-40136 Bologna Italy Univ Fed Vicosa DPI Ave PH Rolfs S-N BR-36570900 Vicosa MG Brazil

We consider a two-dimensional problem in which one is required to split a given rectangular bin into the smallest number of items. The resulting items must be squares to be packed, without overlapping, into the bin so as to cover all the given rectangle. We present a mathematical model and a heuristic algorithm that is proved to find the optimal solution in some special cases. Then, we introduce a relaxation of the problem and present different exact approaches based on this relaxation. Finally, we report computational experiments on the performances of the algorithms on a large set of randomly generated instances.

关键词： Two-dimensional packing Mathematical models exact algorithms Computational experiments

来源：评论

学校读者我要写书评

暂无评论

Synergistic team composition: A computational approach to foster diversity in teams

引用

KNOWLEDGE-BASED SYSTEMS 2019年 182卷 104799-000页

作者： Andrejczuk, Ewa Bistaffa, Filippo Blum, Christian Rodriguez-Aguilar, Juan A. Sierra, Carles IIIA CSIC Artificial Intelligence Res Inst Campus UAB Bellaterra Catalonia Spain Nanyang Technol Univ ST Engn NTU Corp Lab Singapore Singapore

Co-operative learning in heterogeneous teams refers to learning methods in which teams are organised both to accomplish academic tasks and for individuals to gain knowledge. Competencies, personality and the gender of team members are key factors that influence team performance. Here, we introduce a team composition problem, the so-called synergistic team composition problem (STCP), which incorporates such key factors when arranging teams. Thus, the goal of the STCP is to partition a set of individuals into a set of synergistic teams: teams that are diverse in personality and gender and whose members cover all required competencies to complete a task. Furthermore, the STCP requires that all teams are balanced in that they are expected to exhibit similar performances when completing the task. We propose two efficient algorithms to solve the STCP. Our first algorithm is based on a linear programming formulation and is appropriate to solve small instances of the problem. Our second algorithm is an anytime heuristic that is effective for large instances of the STCP. Finally, we thoroughly study the computational properties of both algorithms in an educational context when grouping students in a classroom into teams using actual-world data. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Team composition exact algorithms Heuristic algorithms Optimisation Coalition formation

来源：评论

学校读者我要写书评

暂无评论

Solving rank-constrained semidefinite programs in exact arithmetic

引用

JOURNAL OF SYMBOLIC COMPUTATION 2018年第Mar./Apr.期85卷 206-223页

作者： Naldi, Simone Tech Univ Dortmund Fak Math Vogelpothsweg 87 D-44227 Dortmund Germany

We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in systems control theory and combinatorial optimization, but even in more general contexts such as polynomial optimization or real algebra. While numerical algorithms exist for solving this problem, such as interior-point or Newton-like algorithms, in this paper we propose an approach based on symbolic computation. We design an exact algorithm for solving rank-constrained semidefinite programs, whose complexity is essentially quadratic on natural degree bounds associated to the given optimization problem: for subfamilies of the problem where the size of the feasible matrix, or the dimension of the affine section, is fixed, the algorithm is polynomial time. The algorithm works under assumptions on the input data: we prove that these assumptions are generically satisfied. We implement it in Maple and discuss practical experiments. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Semidefinite programming Determinantal varieties Linear matrix inequalities Rank constraints exact algorithms Computer algebra Polynomial optimization Spectrahedra Sums of squares

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Maximum Clique: A Computational Study

引用

algorithms 2012年第4期5卷 545-587页

作者： Prosser, Patrick Univ Glasgow Comp Sci Glasgow G12 8QQ Lanark Scotland

We investigate a number of recently reported exact algorithms for the maximum clique problem. The program code is presented and analyzed to show how small changes in implementation can have a drastic effect on performance. The computational study demonstrates how problem features and hardware platforms influence algorithm behaviour. The effect of vertex ordering is investigated. One of the algorithms (MCS) is broken into its constituent parts and we discover that one of these parts frequently degrades performance. It is shown that the standard procedure used for rescaling published results (i.e., adjusting run times based on the calibration of a standard program over a set of benchmarks) is unsafe and can lead to incorrect conclusions being drawn from empirical data.

关键词： maximum clique exact algorithms empirical study

来源：评论

学校读者我要写书评

暂无评论

Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks

引用

algorithms 2019年第12期12卷 250页

作者： Agnetis, Alessandro Rossi, Fabrizio Smriglio, Stefano Univ Siena Dipartimento Ingn Informaz & Sci Matemat I-53100 Siena SI Italy Univ Aquila Dipartimento Ingn & Sci Informaz & Matemat I-67100 Laquila AQ Italy

We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish-start, here the task of a job cannot start before the task preceding it has started. We give polynomial exact algorithms for the following problems: a two-machine job shop with two jobs when recirculation is allowed (i.e., jobs can visit the same machine many times), a two-machine flow shop, and an m-machine flow shop with two jobs. We also point out some special cases whose complexity status is open.

关键词： job shop flow shop s-precedence constraints exact algorithms complexity

来源：评论

学校读者我要写书评

暂无评论

Upper and Lower Bounds for Different Parameterizations of (n,3)-MAXSAT 12th

Upper and Lower Bounds for Different Parameterizations of (n...

引用

12th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Belova, Tatiana Bliznets, Ivan Russian Acad Sci St Petersburg Dept Steklov Inst Math St Petersburg Russia

ISBN: (纸本)9783030046514;9783030046507

In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in input formula each variable appears at most three times. Here, we improve previous upper bounds for (n,3)-MAXSAT in terms of n (number of variables) and in terms of k (number of clauses that we are required to satisfy). Moreover, we prove that satisfying more clauses than the simple all true assignment is an NP-hard problem.

关键词： Maximum satisfiability exact algorithms Parameterization above guarantee

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：