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

A constraint programming approach to extract the maximum number of non-overlapping test forms

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2006年第2-3期33卷 319-332页

作者： Belov, DI Armstrong, RD Law Sch Admiss Council Psychometr Res Newtown PA 18940 USA Rutgers State Univ Newark NJ 07102 USA

This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented.

关键词： combinatorial optimization constraint programming branch-and-bound set packing test assembly

来源：评论

学校读者我要写书评

暂无评论

Checking the Feasibility of Dial-a-Ride Instances Using constraint programming

引用

TRANSPORTATION SCIENCE 2011年第3期45卷 399-412页

作者： Berbeglia, Gerardo Pesant, Gilles Rousseau, Louis-Martin HEC Montreal Montreal PQ H3T 2A7 Canada Ecole Polytech Dept Genie Informat & Genie Logiciel Montreal PQ H3C 3A7 Canada Ecole Polytech Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada

In the dial-a-ride problem (DARP), a fleet of vehicles must serve transportation requests made by users that need to be transported from an origin to a destination. In this paper we develop the first exact algorithm which is able to either efficiently prove the infeasibility or to provide a feasible solution. Such an algorithm could be used in a dynamic setting for determining whether it is possible or not to accept an incoming request. The algorithm includes solution space reduction procedures, and filtering algorithms for some DARP relaxations. Computational results show that the filtering algorithms are effective and that the resulting algorithm is advantageous on the more constrained instances.

关键词： dial-a-ride problem algorithms partial routes scheduling dynamic programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach for the team orienteering problem with time windows

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2017年 107卷 178-195页

作者： Gedik, Ridvan Kirac, Emre Milburn, Ashlea Bennet Rainwater, Chase Univ New Haven Dept Mech & Ind Engn 300 Boston Post Rd West Haven CT 06516 USA Univ Houston Clear Lake Dept Engn 2700 Bay Area Blvd Houston TX 77058 USA Univ Arkansas Dept Ind Engn 4207 Bell Engn Ctr1 Univ Arkansas Fayetteville AR 72701 USA

The team orienteering problem with time windows (TOPTW) is a NP-hard combinatorial optimization problem. It has many real-world applications, for example, routing technicians and disaster relief routing. In the TOPTW, a set of locations is given. For each, the profit, service time and time window are known. A fleet of homogenous vehicles are available for visiting locations and collecting their associated profits. Each vehicle is constrained by a maximum tour duration. The problem is to plan a set of vehicle routes that begin and end at a depot, visit each location no more than once by incorporating time window constraints. The objective is to maximize the profit collected. In this study we discuss how to use constraint programming (CP) to formulate and solve TOPTW by applying interval variables, global constraints and domain filtering algorithms. We propose a CP model and two branching strategies for the TOPTW. The approach finds 119 of the best-known solutions for 304 TOPTW benchmark instances from the literature. Moreover, the proposed method finds one new best-known solution for TOPTW benchmark instances and proves the optimality of the best-known solutions for two additional instances. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Team orienteering problem Time windows Vehicle routing constraint programming Interval variable

来源：评论

学校读者我要写书评

暂无评论

A unified framework for partial and hybrid search methods in constraint programming

引用

COMPUTERS & OPERATIONS RESEARCH 2006年第10期33卷 2805-2833页

作者： de Givry, S Jeannin, L INRA Unite Biometrie & Intelligence Artificielle F-31326 Castanet Tolosan France Thales Res & Technol F-91404 Orsay France

We present a library called ToOLS for the design of complex tree search algorithms in constraint programming (CP). We separate the description of a search algorithm into three parts: a refinement-based search scheme that defines a complete search tree, a set of conditions for visiting nodes that specifies a parameterized partial exploration, and a strategy for combining several partial explorations. This library allows the expression of most of the partial, i.e. nonsystematic backtracking, search methods, and also a specific class of hybrid local/global search methods called large neighborhood search, which are very naturally suited to CP. Variants of these methods are easy to implement with the ToOLS primitives. We demonstrate the expressiveness and efficiency of the library by solving a satellite mission management benchmark that is a mix between a traveling salesman problem with time windows and a Knapsack problem. Several partial and hybrid search methods are compared. Our results dramatically outperform CP approaches based on classical depth-first search methods. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： design languages constraint programming combinatorial optimization search strategies tree search large neighborhood search

来源：评论

学校读者我要写书评

暂无评论

Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints

引用

COMPUTERS & OPERATIONS RESEARCH 2018年第Apr.期92卷 87-97页

作者： Hojabri, Hossein Gendreau, Michel Potvin, Jean-Yves Rousseau, Louis-Martin Univ Montreal Dept Informat & Rech Operat CP 6128Succ Ctr Ville Montreal PQ H3C 3J7 Canada Ecole Polytech Montreal Dept Math & Genie Ind CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Univ Montreal Ctr Interuniv Rech Reseaux Entreprise Logist & Tr CP 6128Succ Ctr Ville Montreal PQ H3C 3J7 Canada

This paper considers an extension of the vehicle routing problem with time windows, where the arrival of two vehicles at different customer locations must be synchronized. That is, one vehicle has to deliver some product to a customer, like a home theater system, while the crew on another vehicle must install it. This type of problem is often encountered in practice and is very challenging due to the interdependency among the vehicle routes, but has received little attention in the literature. A constraint programming-based adaptive large neighborhood search is proposed to solve this problem. The search abilities of the large neighborhood search and the constraint propagation abilities of constraint programming are combined to determine the feasibility of any proposed modification to the current solution. Numerical results are reported on instances derived from benchmark instances for the vehicle routing problem with time windows with up to 200 customers. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Vehicle routing Synchronization Large neighborhood search constraint programming

来源：评论

学校读者我要写书评

暂无评论

A study of constraint programming heuristics for the car-sequencing problem

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2015年 38卷 34-44页

作者： Siala, Mohamed Hebrard, Emmanuel Huguet, Marie-Jose CNRS LAAS F-31400 Toulouse France Univ Toulouse INSA F-31400 Toulouse France Univ Toulouse LAAS F-31400 Toulouse France

In the car-sequencing problem, a number of cars have to be sequenced on an assembly line respecting several constraints. This problem was addressed by both Operations Research (OR) and constraint programming (CP) communities, either as a decision problem or as an optimization problem. In this paper, we consider the decision variant of the car sequencing problem and we propose a systematic way to classify heuristics for solving it. This classification is based on a set of four criteria, and we consider all relevant combinations for these criteria. Some combinations correspond to common heuristics used in the past, whereas many others are novel. Not surprisingly, our empirical evaluation confirms earlier findings that specific heuristics are very important for efficiently solving the car-sequencing problem (see for instance Smith, 1996), in fact, often as important or more than the propagation method. Moreover, through a criteria analysis, we are able to get several new insights into what makes a good heuristic for this problem. In particular, we show that the criterion used to select the most constrained option is critical, and the best choice is fairly reliably the "load" of an option. Similarly, branching on the type of vehicle is more efficient than branching on the use of an option. Overall, we can therefore indicate with a relatively high confidence which is the most robust strategy, or at least outline a small set of potentially best strategies. Last, following a remark in Regin and Puget (1997) stating that the notion of slack used in heuristics induces a pruning rule, we propose an algorithm for this method and experimentally evaluate it, showing that, although computationally cheap and easy to implement, this is in practice a very efficient way to solve car-sequencing benchmarks. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Car-sequencing Heuristics Tree search methods constraint programming

来源：评论

学校读者我要写书评

暂无评论

A hybrid constraint programming/Mixed Integer programming framework for the preventive signaling maintenance crew scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第1期269卷 341-352页

作者： Pour, Shahrzad M. Drake, John H. Ejlertsen, Lena Secher Rasmussen, Kourosh Marjani Burke, Edmund K. Tech Univ Denmark DTU Management Engn DK-2800 Lyngby Denmark Queen Mary Univ London Operat Res Grp Mile End Rd London E1 4NS England Banedanmark Amer Plads 15 DK-2100 Copenhagen Denmark

A railway signaling system is a complex and interdependent system which should ensure the safe operation of trains. We introduce and address a mixed integer optimisation model for the preventive signal maintenance crew scheduling problem in the Danish railway system. The problem contains many practical constraints, such as temporal dependencies between crew schedules, the splitting of tasks across multiple days, crew competency requirements and several other managerial constraints. We propose a novel hybrid framework using constraint programming to generate initial feasible solutions to feed as 'warm start' solutions to a Mixed Integer programming solver for further improvement. We apply this hybrid framework to a section of the Danish rail network and benchmark our results against both direct application of a Mixed Integer programming solver and modelling the problem as a constraint Optimisation Problem. Whereas the current practice of using a general purpose Mixed Integer programming solver is only able to solve instances over a two-week planning horizon, the hybrid framework generates good results for problem instances over an eight-week period. In addition, the use of a Mixed Integer programming solver to improve the initial solutions generated by constraint programming is shown to be significantly superior to addressing the problem as a constraint Optimisation Problem. (C) 2017 The Authors. Published by Elsevier B.V.

关键词： Transportation Scheduling constraint programming Mixed Integer programming Hybrid approaches

来源：评论

学校读者我要写书评

暂无评论

A combined integer/constraint programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions

引用

ENGINEERING OPTIMIZATION 2011年第2期43卷 135-157页

作者： Edis, Emrah B. Ozkarahan, Irem Dokuz Eylul Univ Dept Ind Engn TR-35160 Izmir Turkey Troy Univ Dept Comp Sci Montgomery AL 36104 USA

A resource-constrained identical parallel machine scheduling problem with machine eligibility restrictions is investigated in this study. For the considered problem, three optimization models;an integer programming (IP) model, a constraint programming (CP) model and a combined IP/CP model are developed. A problem-based search procedure to be used in CP and IP/CP combined models is also proposed to give quick and efficient results. All three optimization models are constructed and solved in OPL Studio 3.7 setting 1000 second run-time limit. Computational results show that the combined IP/CP OPL model with the proposed problem-based search procedure not only achieves magnitude reduction in computational time but also gives optimal results in 174 out of 200 test problems, while IP and CP models prove optimality in only 47 and 6 problems, respectively. Finally, computational results are also analysed and discussed in terms of various problem parameters.

关键词： parallel machine scheduling integer programming constraint programming additional resources machine eligibility

来源：评论

学校读者我要写书评

暂无评论

Mixing Static and Dynamic Partitioning to Parallelize a constraint programming Solver

引用

INTERNATIONAL JOURNAL OF PARALLEL programming 2016年第3期44卷 486-505页

作者： Menouer, Tarek Rezgui, Mohamed Le Cun, Bertrand Regin, Jean-Charles Univ Versailles St Quentin En Yvelines Prism Lab 45 Ave des Etats Unis F-78035 Versailles France Univ Nice Sophia Antipolis Lab I3S 28 Ave Valombrose F-06100 Nice France

This paper presents an external parallelization of constraint programming (CP) search tree mixing both static and dynamic partitioning. The principle of the parallelization is to partition the CP search tree into a set of sub-trees, then assign each sub-tree to one computing core in order to perform a local search using a sequential CP solver. In this context, static partitioning consists of decomposing the CP variables domains in order to split the CP search tree into a set of disjoint sub-trees to assign them to the cores. This strategy performs well without adding an extra cost to the parallel search, but the problem is the load imbalance between computing cores. On the other hand, dynamic partitioning is based on preservation of the search state to generate, dynamically or on demand, the sub-trees that are assigned to the cores. This strategy offers good load balancing between the different computing cores, but computing overcosts appear due to the initialisation of the search when a sub-tree is migrated from one core to another. In this paper, we propose a new partitioning strategy that mixes the static and dynamic partitioning and enjoys the benefits of each strategy. This mixed partitioning is designed to run on shared and distributed memory architectures. The performances obtained are illustrated by solving the CP problems modelled using the FlatZinc format and solved using the Google OR-Tools solver on top of the parallel Bobpp framework.

关键词： Parallelism constraint programming Work Stealing Dynamic load balancing

来源：评论

学校读者我要写书评

暂无评论

A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions

引用

ENGINEERING OPTIMIZATION 2022年第9期54卷 1563-1582页

作者： de Abreu, Levi Ribeiro Guimaraes Araujo, Kennedy Anderson Prata, Bruno de Athayde Nagano, Marcelo Seido Moccellin, Joao Vitor Univ Sao Paulo Dept Prod Engn Sao Carlos Brazil Univ Sao Paulo Dept Appl Math Sao Paulo Brazil Univ Fed Ceara Dept Ind Engn Fortaleza Ceara Brazil

This article presents a new variant for the open shop scheduling problem, the open shop scheduling problem with repetitions (OSSPR), where the jobs can be processed on any machine more than once (operation by operation). Thereby, all the jobs can be scheduled in an unconstrained way, substantially increasing the number of feasible solutions in comparison with the classical open shop. The OSSPR has many applications in automotive and maintenance actives. To solve the problem, a mixed-integer linear programming model is presented and a new constraint programming model is proposed. Since the problem under study is NP-hard, a new efficient variable neighbourhood search is proposed using variable search strategies through the proposed constraint programming model. The objective function is makespan minimization, and it uses the lower bound deviation as performance criterion. Computational results show very good performance of the proposed metaheuristic on the instances tested.

关键词： Production sequencing makespan constraint programming exact methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：