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

Graph matching problems and the NP-hardness of sortedness constraints

THEORETICAL COMPUTER SCIENCE 2017年 695卷 16-27页

作者： Rusu, Irena Univ Nantes LS2N UMR 6004 2 Rue HoussiniereBP 92208 F-44322 Nantes France

In constraint programming, global constraints allow to model and solve many combinatorial problems. Among these constraints, three sortedness constraints have been proposed, which define interesting and not so easy graph matching problems. In this paper, we formulate one of these problems as a marriage scheduling problem, which is a special perfect matching problem in a bipartite graph. We show that the marriage scheduling problem is NP-complete, and we explain the relationships between this graph problem and the sortedness constraints. As a consequence, we deduce that the sort(U, V) constraint (Older et al., 1995), the sort(U, V, P) constraint (Zhou, 1996) and the recently introduced keysorting(U, V, Keys, P) constraint (Carlsson et al., 2014) are intractable (assuming P not equal NP) for integer variables whose domains are not limited to intervals. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Computational complexity Graph matching Bipartite graph constraint programming Sortedness constraints

来源：评论

学校读者我要写书评

暂无评论

Online control of enumeration strategies via bat algorithm and black hole optimization

引用

NATURAL COMPUTING 2017年第2期16卷 241-257页

作者： Soto, Ricardo Crawford, Broderick Olivares, Rodrigo Niklander, Stefanie Johnson, Franklin Paredes, Fernando Olguin, Eduardo Pontificia Univ Catolica Valparaiso Valparaiso Chile Univ Valparaiso Valparaiso Chile Univ Autonoma Chile Santiago Chile Univ Espiritu Santo Guayaquil Ecuador Univ Playa Ancha Valparaiso Chile Univ Diego Portales Escuela Ingn Ind Santiago Chile Univ San Sebastian Santiago Chile

constraint programming is an efficient and powerful paradigm for solving constraint satisfaction and optimization problems. Under this paradigm, problems are modeled as a sequence of variables and a set of constraints. The variables have a non-empty domain of candidate values and constraints restrict the values that variables can adopt. The solving process operates by assigning values to variables in order to produce potential solutions which are then evaluated. A main component in this process is the enumeration strategy, which decides the order in which variables and values are chosen to produce such potential solutions. There exist different ways to perform this selection, and depending on the quality of this decision, the efficiency of the solving process may dramatically vary. Unfortunately, selecting the proper strategy is known to be a hard task, as its behavior during search is generally unpredictable and certainly depends on the problem at hand. A recent trend to handle this concern, is to interleave a set of different strategies instead of using a single one during the whole process. The strategies are evaluated according to process indicators in order to use the most promising one on each part of the search process. This process is known as online control of enumeration strategies and its correct configuration can be seen itself as an optimization problem. In this paper, we present two new systems for online control of enumeration strategies based on recent nature-inspired metaheuristics: bat algorithm and black hole optimization. The bat algorithm mimics the location capabilities of bats that employ echoes to identify the objects in their surrounding areas, while black hole optimization inspires its behavior on the gravitational pull of black holes in space. We perform different experimental results by using different enumeration strategies and well-known benchmarks, where the proposed approaches are able to noticeably outperform previous work on online

关键词： constraint programming Autonomous search Bio-inspired Metaheuristics Bat algorithm Black hole

来源：评论

学校读者我要写书评

暂无评论

Rule-based optimization and multicriteria decision support for packaging a truck chassis

引用

ENGINEERING OPTIMIZATION 2017年第6期49卷 1057-1077页

作者： Berger, Martin Lindroth, Peter Welke, Richard Fraunhofer Inst Ind Math ITWM Kaiserslautern Germany Volvo Grp Trucks Technol Chassis & Vehicle Dynam Gothenburg Sweden

Trucks are highly individualized products where exchangeable parts are flexibly combined to suit different customer requirements, this leading to a great complexity in product development. Therefore, an optimization approach based on constraint programming is proposed for automatically packaging parts of a truck chassis by following packaging rules expressed as constraints. A multicriteria decision support system is developed where a database of truck layouts is computed, among which interactive navigation then can be performed. The work has been performed in cooperation with Volvo Group Trucks Technology (GTT), from which specific rules have been used. Several scenarios are described where the methods developed can be successfully applied and lead to less time-consuming manual work, fewer mistakes, and greater flexibility in configuring trucks. A numerical evaluation is also presented showing the efficiency and practical relevance of the methods, which are implemented in a software tool.

关键词： truck chassis packaging rule-based optimization constraint programming multicriteria decision support

来源：评论

学校读者我要写书评

暂无评论

Feasibility check for the distance geometry problem: an application to molecular conformations

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2017年第5期24卷 1023-1040页

作者： Agra, Agostinho Figueiredo, Rosa Lavor, Carlile Maculan, Nelson Pereira, Antonio Requejo, Cristina Univ Aveiro Dept Math P-3810193 Aveiro Portugal Univ Avignon LIA F-84911 Avignon France Univ Estadual Campinas Dept Appl Math BR-13081970 Campinas SP Brazil Univ Fed Rio de Janeiro COPPE POB 68511 BR-21941972 Rio De Janeiro Brazil Univ Fed Rio de Janeiro Inst Math POB 68511 BR-21941972 Rio De Janeiro Brazil

The distance geometry problem (DGP) consists in finding an embedding in a metric space of a given weighted undirected graph such that for each edge in the graph, the corresponding distance in the embedding belongs to a given distance interval. We discuss the relationship between the existence of a graph embedding in a Euclidean space and the existence of a graph embedding in a lattice. Different approaches, including two integer programming (IP) models and a constraint programming (CP) approach, are presented to test the feasibility of the DGP. The two IP models are improved with the inclusion of valid inequalities, and the CP approach is improved using an algorithm to perform a domain reduction. The main motivation for this work is to derive new pruning devices within branch-and-prune algorithms for instances occurring in real applications related to determination of molecular conformations, which is a particular case of the DGP. A computational study based on a set of small-sized instances from molecular conformations is reported. This study compares the running times of the different approaches to check feasibility.

关键词： distance geometry problem graph embedding integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

Hybrid optimization methods for time-dependent sequencing problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第3期259卷 887-897页

作者： Kinable, Joris Cire, Andre A. van Hoeve, Willem-Jan Carnegie Mellon Univ Inst Robot 5000 Forbes Ave Pittsburgh PA 15213 USA Carnegie Mellon Univ Tepper Sch Business 5000 Forbes Ave Pittsburgh PA 15213 USA Univ Toronto Scarborough Dept Management 1265 Mil Trail Toronto ON M1C 1A4 Canada

In this paper, we introduce novel optimization methods for sequencing problems in which the setup times between a pair of tasks depend on the relative position of the tasks in the ordering. Our proposed methods rely on a hybrid approach where a constraint programming model is enhanced with two distinct relaxations: One discrete relaxation based on multivalued decision diagrams, and one continuous relaxation based on linear programming. Both relaxations are used to generate bounds and enhance constraint propagation. Experiments conducted on three variants of the time-dependent traveling salesman problem indicate that our techniques substantially outperform general-purpose methods, such as mixed integer linear programming and constraint programming models. (C)2016 Elsevier B.V. All rights reserved.

关键词： constraint programming Sequencing Decision diagrams Additive bounding

来源：评论

学校读者我要写书评

暂无评论

Itemset mining: A constraint programming perspective

引用

ARTIFICIAL INTELLIGENCE 2011年第12-13期175卷 1951-1983页

作者： Guns, Tias Nijssen, Siegfried De Raedt, Luc Katholieke Univ Leuven B-3001 Louvain Belgium

The field of data mining has become accustomed to specifying constraints on patterns of interest. A large number of systems and techniques has been developed for solving such constraint-based mining problems, especially for mining itemsets. The approach taken in the field of data mining contrasts with the constraint programming principles developed within the artificial intelligence community. While most data mining research focuses on algorithmic issues and aims at developing highly optimized and scalable implementations that are tailored towards specific tasks, constraint programming employs a more declarative approach. The emphasis lies on developing high-level modeling languages and general solvers that specify what the problem is, rather than outlining how a solution should be computed, yet are powerful enough to be used across a wide variety of applications and application domains. This paper contributes a declarative constraint programming approach to data mining. More specifically, we show that it is possible to employ off-the-shelf constraint programming techniques for modeling and solving a wide variety of constraint-based itemset mining tasks, such as frequent, closed, discriminative, and cost-based itemset mining. In particular, we develop a basic constraint programming model for specifying frequent itemsets and show that this model can easily be extended to realize the other settings. This contrasts with typical procedural data mining systems where the underlying procedures need to be modified in order to accommodate new types of constraint, or novel combinations thereof. Even though the performance of state-of-the-art data mining systems outperforms that of the constraint programming approach on some standard tasks, we also show that there exist problems where the constraint programming approach leads to significant performance improvements over state-of-the-art methods in data mining and as well as to new insights into the underlying data mining probl

关键词： Data mining Itemset mining constraint programming

来源：评论

学校读者我要写书评

暂无评论

Planning inland vessel operations in large seaports using a two-phase approach

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2017年 106卷 41-57页

作者： Li, Shijie Negenborn, Rudy R. Lodewijks, Gabriel Delft Univ Technol Dept Maritime & Transport Technol Mekelweg 2 NL-2628 CD Delft Netherlands Wuhan Univ Technol Sch Logist Engn 1178 Heping Rd Wuhan Hunan Peoples R China

Inland vessels are often used to transport containers between large seaports and the hinterland. Each time a vessel arrives in such a port, it typically visits several terminals to load and unload containers. In the Port of Rotterdam, the largest port in Europe, there are 77,000 inland vessels that have moored in the port in 2014 for transporting cargo. With the significant growth of containerized cargo transportation over the last decade, large seaports are under pressure to ensure high handling efficiency. Due to this development and the limited capacity at terminals, the inland vessels usually spend longer time in the port that originally planned. This leads to low utilization of terminal resources and congestion in the port. This paper proposes a novel two-phase planning approach that could improve this, taking into account several practical constraints. Specifically, we take into account the restricted opening times of terminals, the priority of sea-going vessels, and the different terminal capacities and sizes. In addition, we also consider the option for inland vessels to carry out additional inter-terminal transport tasks. Our approach is based on the integration of mixed-integer programming (MIP) and constraint programming (CP) to generate rotation plans for inland vessels. In the first phase, a single vessel optimization problem is solved using MIP. In the second phase, a multiple vessel coordination problem is formulated using CP;three large neighborhood search (LNS)-based heuristics are proposed to solve the problem. Simulation experiments show that the proposed INS-based heuristic outperforms the performance obtained with a state-of-the-art commercial CP solvers both regarding the solution quality and the computation time. Moreover, the simulation results indicate significant improvements with shorter departure times, sojourn times and waiting times. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Vessel rotation planning Mixed-integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint-directed search for all-interval series

引用

constraintS 2017年第3期22卷 403-431页

作者： Polash, Md Masbaul Alam Newton, M. A. Hakim Sattar, Abdul Griffith Univ Inst Integrated & Intelligent Syst Brisbane Qld Australia

All-interval series is a standard benchmark problem for constraint satisfaction search. An all-interval series of size n is a permutation of integers [0, n) such that the differences between adjacent integers are a permutation of [1, n). Generating each such all-interval series of size n is an interesting challenge for constraint community. The problem is very difficult in terms of the size of the search space. Different approaches have been used to date to generate all the solutions of AIS but the search space that must be explored still remains huge. In this paper, we present a constraint-directed backtracking-based tree search algorithm that performs efficient lazy checking rather than immediate constraint propagation. Moreover, we prove several key properties of all-interval series that help prune the search space significantly. The reduced search space essentially results into fewer backtracking. We also present scalable parallel versions of our algorithm that can exploit the advantage of having multi-core processors and even multiple computer systems. Our new algorithm generates all the solutions of size up to 27 while a satisfiability-based state-of-the-art approach generates all solutions up to size 24.

关键词： All-interval series Backtracking search constraint programming Lazy constraint propagation

来源：评论

学校读者我要写书评

暂无评论

Anticipating anonymity in screening program databases

引用

INTERNATIONAL JOURNAL OF MEDICAL INFORMATICS 2017年第Jul.期103卷 20-31页

作者： Caballero, Rafael Sen, Sagar Nygard, Jan F. Univ Complutense Madrid Madrid Spain Certus SFI Lysaker Norway Canc Registry Norway Kreftregisteret Oslo Norway

In this paper, we propose a technique for improving anonymity in screening program databases to increase the privacy for the participants in these programs. The data generated by the invitation process (screening centre, appointment date) is often made available to researchers for medical research and for evaluation and improvement of the screening program. This information, combined with other personal quasi-identifiers such as the ZIP code, gender or age, can pose a risk of disclosing the identity of the individuals participating in the program, and eventually their test results. We present two algorithms that produce a set of screening appointments that aim to increase anonymity of the resulting dataset. The first one, based on the constraint programming paradigm, defines the optimal appointments, while the second one is a suboptimal heuristic algorithm that can be used with real size datasets. The level of anonymity is measured using the new concept of generalized k-anonymity, which allows us to show the utility of the proposal by means of experiments, both using random data and data based on screening invitations from the Norwegian Cancer Registry.

关键词： Anonymity Screening programs constraint programming

来源：评论

学校读者我要写书评

暂无评论

MRCP-RM: A Technique for Resource Allocation and Scheduling of MapReduce Jobs with Deadlines

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第5期28卷 1375-1389页

作者： Lim, Norman Majumdar, Shikharesh Ashwood-Smith, Peter Carleton Univ Dept Syst & Comp Engn Ottawa ON K1S 5B6 Canada Huawei Technol Canada Suite 400303 Terry Fox Dr Kanata ON K2K 3J1 Canada

Resource allocation and scheduling on clouds are required to harness the power of the underlying resource pool such that the service provider can meet the quality of service requirements of users, which are often captured in service level agreements (SLAs). This paper focuses on resource allocation and scheduling on clouds and clusters that process MapReduce jobs with SLAs. The resource allocation and scheduling problem is modelled as an optimization problem using constraint programming, and a novel MapReduce constraint programming based Resource Management algorithm (MRCP-RM) is devised that can effectively process an open stream of MapReduce jobs where each job is characterized by an SLA comprising an earliest start time, a required execution time, and an end-to-end deadline. A detailed performance evaluation of MRCP-RM is conducted for an open system subjected to a stream of job arrivals using both simulation and experimentation on a real system. The experiments on a real system are performed on a Hadoop cluster (deployed on Amazon EC2) that runs our new Hadoop constraint programming based Resource Management algorithm (HCP-RM) that incorporates a technique for handling data locality. The results of the performance evaluation demonstrate the effectiveness of MRCP-RM/HCP-RM in generating a schedule that leads to a low proportion of jobs missing their deadlines (P) and also provide insights into system behaviour and performance. In the simulation experiments, it is observed that MRCP-RM achieves on average an 82 percent lower P compared to a technique from the existing literature when processing a synthetic workload from Facebook. Furthermore, in the experiments performed on a Hadoop cluster deployed on Amazon EC2, it is observed that HCP-RM achieved on average a 63 percent lower P compared to an EDF-Scheduler for a wide variety of workload and system parameters experimented with.

关键词： Resource allocation and scheduling on clusters and clouds hadoop scheduler constraint programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：