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

Design of robust, reliable sensor networks using constraint programming

COMPUTERS & CHEMICAL ENGINEERING 2008年第9期32卷 2030-2049页

作者： Kotecha, Prakash R. Bhushan, Mani Gudi, Ravindra D. Indian Inst Technol Dept Chem Engn Bombay 400076 Maharashtra India

Various criteria have been considered in the literature for selection of optimal sensor networks. Amongst these, maximization of network reliability is an important criterion. While there are several approaches for designing maximum reliability networks, uncertainty in the available sensor reliability data has not been considered in these designs. In this article we present two novel formulations that incorporate robustness to uncertainties in the reliability data. Towards this end the sensor network design problem for maximizing reliability is formulated as explicit-optimization (MINLP) problem using failure rates of sensors which have better scaling properties instead of sensor reliabilities. constraint programming (CP) has been used for solving the resulting optimization problems. Use of CP also enables easy generation of pareto front characterizing trade-offs between performance, cost and robustness for various uncertainty scenarios. The utility of the proposed approach is demonstrated on a case study taken from the literature. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： constraint programming reliability multi-objective optimization robust sensor network design

来源：评论

学校读者我要写书评

暂无评论

Solving the quorumcast routing problem by constraint programming

引用

constraintS 2012年第4期17卷 409-431页

作者： Quang Dung Pham Deville, Yves Hanoi Univ Sci & Technol Hanoi Vietnam Catholic Univ Louvain B-1348 Louvain Belgium

The quorumcast routing problem is a generalization of multicasting which arises in many distributed applications. It consists of finding a minimum cost tree that spans the source node r and at least q out of m specified nodes on a given undirected weighted graph. This paper proposes a complete and an incomplete approach, both based on the same constraint programming (CP) model, but with two different specific search heuristics based on shortest paths. Experimental results show the efficiency of the two proposed approaches. Our complete approach (CP model + complete search) is better than the state of the art complete algorithm and our incomplete approach (CP model + incomplete search) is better than the state of the art incomplete algorithm. Moreover, the proposed complete search is better than the standard First-Fail search in the same CP model.

关键词： constraint programming Quorumcast routing Constrained optimum trees Graphs Incomplete search

来源：评论

学校读者我要写书评

暂无评论

Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2020年第23期58卷 7149-7166页

作者： Polo-Mejia, Oliver Artigues, Christian Lopez, Pierre Basini, Virginie Univ Toulouse CNRS LAAS CNRS Toulouse France CEA SETC DEC DEN St Paul Les Durance France

This paper presents the results of a research project aiming to optimise the scheduling of activities within a research laboratory of the 'Commissariat a l'Energie Atomique et aux Energies Alternatives (CEA)'. To tackle this problem, we decompose every activity into a set of elementary tasks to apply standard scheduling methods. We model the problem as an extended version of the Multi-Skill Project Scheduling Problem (MSPSP). As a first approach, we propose a Multi-Skill Project Scheduling Problem with penalty for preemption, along with its mixed-integer/linear programming (MILP) formulation, where the preemption is allowed applying a penalty every time an activity is interrupted. However, the previous approach does not take into account all safety constraints at the facility, and a more accurate variant of the problem is needed. We propose then to integrate the concept of partial preemption to the MSPSP. This concept, that has not been yet studied in the scientific literature, implies that only a subset of resources is released during preemption periods. The resulting MSPSP with partial preemption (MSPSP-PP) is modelled using two methodologies: MILP and constraint programming. Regarding the industrial need of having good solutions in a short time, we also present a greedy algorithm for the MSPSP-PP.

关键词： multi-skill research project scheduling partial preemption nuclear facility mixed-integer linear programming constraint programming greedy heuristic

来源：评论

学校读者我要写书评

暂无评论

Using constraint programming for solving RCPSP/max-cal

引用

constraintS 2017年第3期22卷 432-462页

作者： Kreter, Stefan Schutt, Andreas Stuckey, Peter J. Tech Univ Clausthal Inst Management & Econ Operat Res Grp D-38678 Clausthal Zellerfeld Germany CSIRO Data61 Decis Sci Melbourne Vic Australia Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia

Resource-constrained project scheduling with the objective of minimizing project duration (RCPSP) is one of the most studied scheduling problems. In this paper we consider the RCPSP with general temporal constraints and calendar constraints. Calendar constraints make some resources unavailable on certain days in the scheduling period and force activity execution to be delayed while resources are unavailable. They arise in practice from, e.g., unavailabilities of staff during public holidays and weekends. The resulting problems are challenging optimization problems. We develop not only six different constraint programming (CP) models to tackle the problem, but also a specialized propagator for the cumulative resource constraints taking the calendar constraints into account. This propagator includes the ability to explain its inferences so it can be used in a lazy clause generation solver. We compare these models, and different search strategies on a challenging set of benchmarks using the lazy clause generation solver chuffed and IBM CPLEX CP Optimizer, respectively. We close all but 8 of the open problems of the benchmark set, extend the benchmark set by instances with up to 500 activities, and show that CP solutions are highly competitive with existing Mip models of the problem.

关键词： RCPSP/max-cal constraint programming Lazy clause generation Calendars General temporal constraints

来源：评论

学校读者我要写书评

暂无评论

Balancing bike sharing systems with constraint programming

引用

constraintS 2016年第2期21卷 318-348页

作者： Di Gaspero, Luca Rendl, Andrea Urli, Tommaso Univ Udine DIEGM Via Sci 206 I-33100 Udine Italy NICTA 878 Dandenong Rd Caulfield Vic 3145 Australia Monash Univ Sch IT 878 Dandenong Rd Caulfield Vic 3145 Australia Austrian Inst Technol Dynam Transportat Syst Giefinggasse 2 A-1210 Vienna Austria

Bike sharing systems need to be properly rebalanced to meet the demand of users and to operate successfully. However, the problem of Balancing Bike Sharing Systems (BBSS) is a demanding task: it requires the design of optimal tours and operating instructions for relocating bikes among stations to maximally comply with the expected future bike demands. In this paper, we tackle the BBSS problem by means of constraint programming (CP). First, we introduce two different CP models for the BBSS problem including two custom branching strategies that focus on the most promising routes. Second, we incorporate both models in a Large Neighborhood Search (LNS) approach that is adapted to the respective CP model. Third, we perform an experimental evaluation of our approaches on three different benchmark sets of instances derived from real-world bike sharing systems. We show that our CP models can be easily adapted to the different benchmark problem setups, demonstrating the benefit of using constraint programming to address the BBSS problem. Furthermore, in our experimental evaluation, we see that the pure CP (branch & bound) approach outperforms the state-of-the-art MILP on large instances and that the LNS approach is competitive with other existing approaches.

关键词： Applications constraint programming Hybrid meta-heuristics Large neighborhood search Optimization Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

How constraint programming can help chemists to generate Benzenoid structures and assess the local Aromaticity of Benzenoids

引用

constraintS 2022年第3期27卷 192-248页

作者： Carissan, Yannick Hagebaum-Reignier, Denis Prcovic, Nicolas Terrioux, Cyril Varet, Adrien Aix Marseille Univ ISM2 Cent Marseille CNRS Marseille France Aix Marseille Univ Univ Toulon LIS CNRS Marseille France

Benzenoids are a subfamily of hydrocarbons (molecules that are only made of hydrogen and carbon atoms) whose carbon atoms form hexagons. These molecules are widely studied in theoretical chemistry and have a lot of concrete applications. Then, there is a lot of problems relative to this subject, like the enumeration of all its Kekule structures (i.e. all valid configurations of double bonds). In this article, we focus our attention on two issues: the generation of benzenoid structures and the assessment of the local aromaticity. On the one hand, generating benzenoids that have certain structural and/or chemical properties (e.g. having a given number of hexagons or a particular structure from a graph viewpoint) is an interesting and important problem. It constitutes a preliminary step for studying their chemical properties. In this paper, we show that modeling this problem in Choco Solver and just letting its search engine generate the solutions is a fast enough and very flexible approach. It can allow to generate many different kinds of benzenoids with predefined structural properties by posting new constraints, saving the efforts of developing bespoke algorithmic methods for each kind of benzenoids. On the other hand, we want to assess the local aromaticity of a given benzenoid. This is a central issue in theoretical chemistry since aromaticity cannot be measured. Nowadays, computing aromaticity requires quantum chemistry calculations that are too expensive to be used on medium to large-sized molecules. In this article, we describe how constraint programming can be useful in order to assess the aromaticity of benzenoids. Moreover, we show that our method is much faster than the reference one, namely NICS.

关键词： constraint programming Graph variables and constraints Modeling Theoretical chemistry

来源：评论

学校读者我要写书评

暂无评论

"I Want It That Way": Enabling Interactive Decision Support Using Large Language Models and constraint programming

引用

ACM TRANSACTIONS ON INTERACTIVE INTELLIGENT SYSTEMS 2024年第3期14卷 1-33页

作者： Lawless, Connor Schoeffer, Jakob Le, Lindyi Rowan, Kael Sen, Shilao Hill, Cristina St. Suh, Jina Sarrafzadeh, Bahareh Cornell Univ Ithaca NY 14850 USA Univ Texas Austin Austin TX USA Microsoft Redmond WA USA Microsoft Res Redmond WA USA Macalester Coll St Paul MN USA

A critical factor in the success of many decision support systems is the accurate modeling of user preferences. Psychology research has demonstrated that users often develop their preferences during the elicitation process, highlighting the pivotal role of system-user interaction in developing personalized systems. This paper introduces a novel approach, combining Large Language Models (LLMs) with constraint programming to facilitate interactive decision support. We study this hybrid framework through the lens of meeting scheduling, a time-consuming daily activity faced by a multitude of information workers. We conduct three studies to evaluate the novel framework, including a diary study to characterize contextual scheduling preferences, a quantitative evaluation of the system's performance, and a user study to elicit insights with a technology probe that encapsulates our framework. Our work highlights the potential for a hybrid LLM and optimization approach for iterative preference elicitation, and suggests design considerations for building systems that support human-system collaborative decision-making processes.

关键词： Decision support large language models constraint programming preference elicitation meeting scheduling

来源：评论

学校读者我要写书评

暂无评论

Fleet design optimisation from historical data using constraint programming and large neighbourhood search

引用

constraintS 2016年第1期21卷 2-21页

作者： Kilby, Philip Urli, Tommaso NICTA Canberra Res Lab Optimisat Res Grp Canberra ACT 2601 Australia

We present an original approach to compute efficient mid-term fleet configurations, at the request of a Queensland-based long-haul trucking carrier. Our approach considers one year's worth of demand data, and employs a constraint programming (CP) model and an adaptive large neighbourhood search (LNS) scheme to solve the underlying multi-day multi-commodity split delivery capacitated vehicle routing problem. Our solver is able to provide the decision maker with a set of Pareto-equivalent fleet setups trading off fleet efficiency against the likelihood of requiring on-hire vehicles and drivers. Moreover, the same solver can be used to solve the daily loading and routing problem. We carry out an extensive experimental analysis, comparing our approach with an equivalent mixed integer programming (MIP) formulation, and we show that our approach is a sound methodology to provide decision support for the mid- and short-term decisions of a long-haul carrier.

关键词： Vehicle routing problem Fleet size and mix Large neighbourhood search Mixed integer programming constraint programming Pre-processing

来源：评论

学校读者我要写书评

暂无评论

Production scheduling and lot streaming at flexible job-shops environments using constraint programming

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2019年 136卷 252-264页

作者： Novas, Juan M. Univ Nacl Cordoba CIEM CONICET Medina Allende S-N RA-5000 Cordoba Argentina Univ Tecnol Nacl CIDS Fac Cordoba RA-5000 Cordoba Argentina

In this contribution, the scheduling at flexible job-shops and the lot streaming problem are simultaneously addressed, by means of a novel constraint programming (CP) approach. The proposed CP model can efficiently tackle both the (i) lots splitting, deciding the number of sublots for each lot and the number of parts that belongs to each sublot, and (ii) the scheduling of production tasks, assigning the operations on sublots to machines and defining the start and completion times of those activities. The novelty of the proposal relies on a formulation that (i) can easily be adapted to cope with different operational policies, such as no-wait or wait schedules, idling or intermitted idling, sequence-dependent setup times, among other alternatives, (ii) introduce to new features that impact on the feasibility of the schedules, such as an extension to the inter-operation waiting policy, to consider whether a sublot can wait an unlimited or a limited period of time, as well as an intermediate storage policy, to indicate if the area to hold work-in-progress is constrained or not. Moreover, a set of operational modes found in real industrial settings are addressed. A framework to classify scenarios based on different problem characteristics is also introduced. Different case studies were solved, and good quality solutions were found when minimizing makespan.

关键词： Lot streaming Scheduling Flexible job-shop constraint programming

来源：评论

学校读者我要写书评

暂无评论

Rule-based modeling and constraint programming based solution of the assembly line balancing problem

引用

EXPERT SYSTEMS WITH APPLICATIONS 2012年第3期39卷 3484-3493页

作者： Topaloglu, Seyda Salum, Latif Supciller, Aliye Ayca Dokuz Eylul Univ Dept Ind Engn TR-35160 Izmir Turkey

The assembly line balancing problem employs traditional precedence graphs to model precedence relations among assembly tasks. Yet they cannot address alternative ways of assembling a product. That is, they only model conjunctions, not disjunctions. Moreover, some additional constraints need also to be considered, but these constraints cannot be modeled effectively through precedence graphs, e.g., constraints indicating certain tasks cannot be assigned into the same station. To address these issues, this paper proposes to model assembly constraints through the well known If-then rules, and to solve the rule-based model through constraint programming (CP), as CP naturally models logical assertions. The paper also shows how to map a rule-based model to a CP or an integer programming (IP) model. Finally, a computational experiment is carried out to analyze the performances of CP and IP models with respect to modeling capability, solution quality and time. The results reveal that CP is more effective and efficient than IP. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Assembly line balancing Precedence graphs Rule-based modeling constraint programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：