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

arXiv 2024年

作者： Zhang, Jiachen Beck, J. Christopher Department of Mechanical and Industrial Engineering University of Toronto TorontoONM5S 3G8 Canada

We propose domain-independent dynamic programming (DIDP) and constraint programming (CP) models to exactly solve type-1 and type-2 assembly line balancing problem with sequence-dependent setup times (SUALBP). The goal is to assign tasks to assembly stations and to sequence these tasks within each station, while satisfying precedence relations specified between a subset of task pairs. Each task has a given processing time and a setup time dependent on the previous task on the station to which the task is assigned. The sum of the processing and setup times of tasks assigned to each station constitute the station time and the maximum station time is called the cycle time. For type-1 SUALBP, the objective is to minimize the number of stations, given a maximum cycle time. For type-2 SUALBP, the objective is to minimize the cycle time, given the number of stations. On a set of diverse SUALBP instances, experimental results show that our approaches significantly outperform the state-of-the-art mixed integer programming models for SUALBP-1. For SUALBP-2, the DIDP model outperforms the state-of-the-art exact approach based on logic-based Benders decomposition. By closing 76 open instances for SUALBP-2, our results demonstrate the promise of DIDP for solving complex planning and scheduling problems. Copyright © 2024, The Authors. All rights reserved.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Solving the Parallel Drone Scheduling Traveling Salesman Problem via constraint programming

引用

ALGORITHMS 2023年第1期16卷 40-40页

作者： Montemanni, Roberto Dell'Amico, Mauro Univ Modena & Reggio Emilia Dept Sci & Methods Engn Via Amendola 2 I-42122 Reggio Emilia Italy Univ Modena & Reggio Emilia Interdept Ctr En&Tech Capannone 19 Tecnopolo Piazza Europa 1 I-42122 Reggio Emilia Italy

Drones are currently seen as a viable way of improving the distribution of parcels in urban and rural environments, while working in coordination with traditional vehicles, such as trucks. In this paper, we consider the parallel drone scheduling traveling salesman problem, where a set of customers requiring a delivery is split between a truck and a fleet of drones, with the aim of minimizing the total time required to serve all the customers. We propose a constraint programming model for the problem, discuss its implementation and present the results of an experimental program on the instances previously cited in the literature to validate exact and heuristic algorithms. We were able to decrease the cost (the time required to serve customers) for some of the instances and, for the first time, to provide a demonstrated optimal solution for all the instances considered. These results show that constraint programming can be a very effective tool for attacking optimization problems with traveling salesman components, such as the one discussed.

关键词： parallel drone scheduling traveling salesman problem constraint programming drones optimization

来源：评论

学校读者我要写书评

暂无评论

constraint programming approaches to disassembly line balancing problem with sequencing decisions

引用

COMPUTERS & OPERATIONS RESEARCH 2021年 126卷 105111-105111页

作者： Edis, Emrah B. Manisa Celal Bayar Univ Dept Ind Engn TR-45140 Manisa Turkey

Recovery of products has received much attention in the last decade due to the increase in both environmental awareness and regulations enacted by governments. In product recovery, disassembly of a product into its constituent parts on a line is one of the most significant operations. This paper deals with a disassembly line balancing and sequencing (DLBS) problem subject to balancing issues, hazardousness of parts, demand quantities and direction changes considered in a lexicographic order. Due to the combinatorial nature of this problem, exact methods, e.g., mixed integer linear programming (MILP), are able to solve only small and medium size problems. Therefore, various metaheuristic algorithms are proposed in literature to find near-optimal solutions. In this paper, constraint programming (CP), which is a suitable technique especially for highly-constrained discrete problems, is used to develop models and solution approaches. To the best of author's knowledge, this study is the first that uses CP for the disassembly line balancing problems. For the DLBS problem, first, a generic CP model is developed. This CP model provides efficient results for small/medium size disassembly problems and benchmark instances. Observing that the generic CP model could not produce even feasible sequence of tasks for some large-sized benchmark instances, a CP-based solution approach is proposed. This approach generates a feasible sequence subject to a fixed assignment of tasks to the workstations by using a CP model and uses this sequence as an initial feasible solution within a warm-start context in CP sequencing models. The computational results show that the proposed CP model improves the several best solutions of medium-sized benchmark instances, while the proposed CP-based solution approach produces excellent results in all large test instances by either improving the best solutions (found so far) or establishing new benchmark solutions. (C) 2020 Elsevier Ltd. All rights reserv

关键词： Disassembly line balancing Sequencing constraint programming Warm-start

来源：评论

学校读者我要写书评

暂无评论

constraint programming Algorithms for Route Planning Exploiting Geometrical Information 36

Constraint Programming Algorithms for Route Planning Exploit...

引用

36th International Conference on Logic programming (ICLP)

作者： Bertagnon, Alessandro Univ Ferrara Dept Engn Ferrara Italy

Problems affecting the transport of people or goods are plentiful in industry and commerce and they also appear to be at the origin of much more complex problems. In recent years, the logistics and transport sector keeps growing supported by technological progress, i.e. companies to be competitive are resorting to innovative technologies aimed at efficiency and effectiveness. This is why companies are increasingly using technologies such as Artificial Intelligence (AI), Blockchain and Internet of Things (IoT). Artificial intelligence, in particular, is often used to solve optimization problems in order to provide users with the most efficient ways to exploit available resources. In this work we present an overview of our current research activities concerning the development of new algorithms, based on constraint Logic programming (CLP) techniques, for route planning problems exploiting the geometric information intrinsically present in many of them or in some of their variants. The research so far has focused in particular on the Euclidean Traveling Salesperson Problem (Euclidean TSP) with the aim to exploit the results obtained also to other problems of the same category, such as the Euclidean Vehicle Routing Problem (Euclidean VRP), in the future.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint programming for an Efficient and Flexible Block Modeling Solver 34

Constraint Programming for an Efficient and Flexible Block M...

引用

34th AAAI Conference on Artificial Intelligence / 32nd Innovative Applications of Artificial Intelligence Conference / 10th AAAI Symposium on Educational Advances in Artificial Intelligence

作者： Mattenet, Alex Lucia Davidson, Ian Nijssen, Siegfried Schaus, Pierre UCLouvain ICTEAM Louvain Belgium Univ Calif Davis Comp Sci Dept Davis CA 95616 USA

ISBN: (纸本)9781577358350

constraint programming (CP) is a powerful paradigm for solving combinatorial problems. In CP, the user creates a model by declaring variables with their domains and expresses the constraints that need to be satisfied in any solution. The solver is then in charge of finding feasible solutions-a value in the domain of each variable that satisfies all the constraints. The discovery of solutions is done by exploring a search tree that is pruned by the constraints in charge of removing impossible values. The CP framework has the advantage of exposing a rich high-level declarative constraint language for modeling, as well as efficient purpose-specific filtering algorithms that can be reused in many problems. In this work, we harness this flexibility and efficiency for the Block Modeling problem. It is a variant of the graph clustering problem that has been used extensively in many domains including social science, spatio-temporal data analysis and even medical imaging. We present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches. We show its use in the analysis of real datasets.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Neuro-Symbolic constraint programming for Structured Prediction 15

Neuro-Symbolic Constraint Programming for Structured Predict...

引用

15th International Workshop on Neural-Symbolic Learning and Reasoning (NeSy) as part of the 1st International Joint Conference on Learning and Reasoning (IJCLR)

作者： Dragone, Paolo Teso, Stefano Passerini, Andrea Twitter London England Univ Trento Trento Italy

We propose Nester, a method for injecting neural networks into constrained structured predictors. Nester first uses a neural network to compute an initial prediction that may or may not satisfy the constraints, and then applies a constraint-based structured predictor to refine the raw predictions according to hard and soft constraints. Nester combines the advantages of its two components: the network can learn complex representations from low-level data while the constraint program on top reasons about the high-level properties and requirements of the prediction task. An empirical evaluation on handwritten equation recognition shows that Nester achieves better performance than both the either component in isolation, especially when training examples are scarce, while scaling to more complex problems than other neuro-programming approaches. Nester proves especially useful to reduce errors at the semantic level of the problem, which is particularly challenging for neural network architectures.

关键词： Machine Learning Neuro-Symbolic Integration Structured Prediction constraint programming

来源：评论

学校读者我要写书评

暂无评论

Parallel Batch Scheduling With Incompatible Job Families Via constraint programming

arXiv

引用

arXiv 2024年

作者： Huertas, Jorge A. Van Hentenryck, Pascal Georgia Institute of Technology AtlantaGA United States

This paper addresses the incompatible case of parallel batch scheduling, where compatible jobs belong to the same family, and jobs from different families cannot be processed together in the same batch. Existing constraint programming (CP) models for this problem fail to synchronize the processing of the jobs within their batch, resulting in batch interruptions. In the context of the diffusion area in the semiconductor manufacturing process, these interrupted solutions would disrupt the thermal stability required for a uniform dopant distribution on the wafers. This paper proposes three new CP models that directly tackle these interruptions in the formulation, including two adaptions of existing models and a novel Redundant Synchronized (RS) model. These existing and novel models are compared on standard test cases, demonstrating the superiority of the RS model in finding optimal or near-optimal solutions quickly. Copyright © 2024, The Authors. All rights reserved.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint programming and Local Search Heuristic: a Matheuristic Approach for Routing and Scheduling Feeder Vessels in Multi-terminal Ports

引用

Operations Research Forum 2020年第4期1卷 1-33页

作者： Sacramento, David Solnon, Christine Pisinger, David DTU Management - Technical University of Denmark Kongens Lyngby Denmark INSA Lyon CITI INRIA CHROMA Villeurbanne F-69621 France

In the liner shipping business, shipping ports represent the main nodes in the maritime transportation network. These ports have a collection of terminals where container vessels can load and discharge containers. However, the logistics and planning of operations differ depending on the vessel size. Large container vessels visit a single terminal, whereas smaller container vessels, or feeder vessels, visit several terminals to transport all containers within the multiple terminals of the port. In this paper, we study the Port Scheduling Problem, the problem of scheduling the operations of feeder vessels in multi-terminal ports. The resulting problem can be identified as a version of the General Shop Scheduling Problem. We consider a constraint programming formulation of the problem, and we propose a matheuristic solution approach for solving large instances. The proposed matheuristic is a hybrid solution method that combines constraint programming with a local search heuristic. The solution approach benefits from the fast search capabilities of local search algorithms to explore the solution space using an Adaptive Large Neighbourhood Search heuristic. During the search, we further use the constraint programming model as an intensification technique, every time a new best-known solution is found. We conduct detailed computational experiments on the PortLib instances, showing that the incorporation of constraint programming within the heuristic search can result in significant benefits. The high instability in solution quality obtained by local search heuristics can be lowered by a simple combination of both methods. © 2020, Springer Nature Switzerland AG.

关键词： ALNS constraint programming Feeder vessels Maritime optimisation Matheuristic

来源：评论

学校读者我要写书评

暂无评论

SeaPearl: A constraint programming Solver Guided by Reinforcement Learning 18th

SeaPearl: A Constraint Programming Solver Guided by Reinforc...

引用

18th International Conference on the Integration of constraint programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Chalumeau, Felix Coulon, Ilan Cappart, Quentin Rousseau, Louis-Martin Inst Polytech Paris Ecole Polytech Palaiseau France Ecole Polytech Montreal Montreal PQ Canada

ISBN: (纸本)9783030782306;9783030782290

The design of efficient and generic algorithms for solving combinatorial optimization problems has been an active field of research for many years. Standard exact solving approaches are based on a clever and complete enumeration of the solution set. A critical and non-trivial design choice with such methods is the branching strategy, directing how the search is performed. The last decade has shown an increasing interest in the design of machine learning-based heuristics to solve combinatorial optimization problems. The goal is to leverage knowledge from historical data to solve similar new instances of a problem. Used alone, such heuristics are only able to provide approximate solutions efficiently, but cannot prove optimality nor bounds on their solution. Recent works have shown that reinforcement learning can be successfully used for driving the search phase of constraint programming (CP) solvers. However, it has also been shown that this hybridization is challenging to build, as standard CP frameworks do not natively include machine learning mechanisms, leading to some sources of inefficiencies. This paper presents the proof of concept for SeaPearl, a new CP solver implemented in Julia, that supports machine learning routines in order to learn branching decisions using reinforcement learning. Support for modeling the learning component is also provided. We illustrate the modeling and solution performance of this new solver on two problems. Although not yet competitive with industrial solvers, SeaPearl aims to provide a flexible and open-source framework in order to facilitate future research in the hybridization of constraint programming and machine learning.

关键词： Reinforcement learning Solver design constraint programming

来源：评论

学校读者我要写书评

暂无评论

Improving the Efficiency of Euclidean TSP Solving in constraint programming by Predicting Effective Nocrossing constraints 1

引用

19th International Conference of the Italian-Association-for-Artificial-Intelligence (AIxIA)

作者： Bellodi, Elena Bertagnon, Alessandro Gavanelli, Marco Zese, Riccardo Univ Ferrara Dept Engn Via G Saragat 1 I-44122 Ferrara Italy

ISBN: (数字)9783030770914

ISBN: (纸本)9783030770914;9783030770907

The Traveling Salesperson Problem (TSP) is a well-known problem addressed in the literature through various techniques, including Integer Linear programming, constraint programming (CP) and Local Search. Many real life instances belong to the subclass of Euclidean TSPs, in which the nodes to be visited are points in the Euclidean plane, and the distance between them is the Euclidean distance. A well-known property of the Euclidean TSP is that no crossings can exist in an optimal solution. In a previous publication, we exploited this property to speed-up the solution of Euclidean instances in CP, by imposing a quadratic number of so-called no-overlapping constraints. In this work, we observe that not all the no-overlapping constraints are equally useful: by experimental analysis, some of them provide a speed-up, while others only introduce overhead. Thus, it is important to define a way to classify useful constraints. To do so, we use machine learning approaches with the objective to impose only those no-overlapping constraints that have been classified as effective. We compare two classifiers based on Random Forest and Neural Networks, which show to be effective, with a slight prevalence for Random Forest.

关键词： constraint programming Euclidean TSP Supervised machine learning Random forest Neural networks Redundant constraints

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：