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

30th International Conference on Principles and Practice of constraint programming, CP 2024

作者： Anders, Markus Brenner, Sofia Rattan, Gaurav TU Darmstadt Germany University of Twente Enschede Netherlands

ISBN: (纸本)9783959773362

Symmetry breaking is a widely popular approach to enhance solvers in constraint programming, such as those for SAT or MIP. Symmetry breaking predicates (SBPs) typically impose an order on variables and single out the lexicographic leader (lex-leader) in each orbit of assignments. Although it is NP-hard to find complete lex-leader SBPs, incomplete lex-leader SBPs are widely used in practice. In this paper, we investigate the complexity of computing complete SBPs, lex-leader or otherwise, for SAT. Our main result proves a natural barrier for efficiently computing SBPs: efficient certification of graph non-isomorphism. Our results explain the difficulty of obtaining short SBPs for important CP problems, such as matrix-models with row-column symmetries and graph generation problems. Our results hold even when SBPs are allowed to introduce additional variables. We show polynomial upper bounds for breaking certain symmetry groups, namely automorphism groups of trees and wreath products of groups with efficient SBPs. © Markus Anders, Sofia Brenner, and Gaurav Rattan.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

An Optimization Model of Wagon-flow Allocation Considering Pick-up and Delivery Operations at the Railway Technical Station 20

An Optimization Model of Wagon-flow Allocation Considering P...

引用

IEEE 20th International Conference on Automation Science and Engineering (CASE)

作者： Tao, Shumei Ma, Liang Guo, Wentao Southwest Jiaotong Univ Sch Informat Sci & Technol Chengdu 611756 Peoples R China Southwest Jiaotong Univ Sichuan Engn Res Ctr Train Operat Control Technol Chengdu 611756 Peoples R China China Railway Shenyang Bur Grp Co Ltd Dispatching Off Shenyang 110001 Peoples R China

ISBN: (纸本)9798350358513;9798350358520

Railcars arriving at the railroad technical station include transfer and local railcars. Local railcars are loaded, unloaded, and inspected through pick-up and delivery operations before being marshalled into departure trains. The technical station wagon-flow allocation problem, as the core issue of its transportation scheduling, is essentially the process of selecting and matching various wagon-flow, which has a profound impact on the overall transportation capacity of the station. Therefore, this article first establishes a constraint programming model to focus on the coordinated optimization problem of wagon-flow allocation and pick-up and delivery operations at the railway technical station. constraints such as operational sequencing, wagon-flow continuity, locomotive usage, and full axle capacity are considered. The primary objective is to maximize the total priority of successfully assembled departure trains. The other objectives include maximizing shunting and track utilization rates and minimizing the number of sources of successful assembled wagon-flow. Additionally, a fast iterative solution algorithm with initial solutions is designed based on constraint propagation and constructive search strategy, achieving hierarchical iterative solution of the entire model. Finally, using actual data from a specific district station as a case study, the verification results show that the method proposed can solve the coordination among pick-up, delivery, disassembly and assembly operations. It can achieve comprehensive utilization of wagon-flow and coordinated wagon-flow allocation of departure trains based on decision-making on pick-up and delivery order, and the algorithm's solving efficiency meets the requirements of on-site timeliness.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Deterministic Partitioning Strategy to Parallelize the constraint programming Search Space 14

Deterministic Partitioning Strategy to Parallelize the Const...

引用

Simulation Multi-Conference

作者： Tarek Menouer Bertrand Le Cun University of Versailles Saint-Quentin-en-Yvelines France

ISBN: (纸本)9781632662163

This paper presents a deterministic parallelization to explore a constraint programming search space. This work is an answer to an industrial project named PAJERO, which is in need of a parallel constraint solver which always responds with the same solution whether using sequential or parallel machines. It is well known that parallel tree search changes the order in which the exploration of solution space is done. In the context where the first solution found is returned, using a different number of cores may change the returned solution. In the literature, several non deterministic strategies have been proposed to parallelize the exploration of constraint programming search space. Most of them are based on the Work Stealing technique used to partition the constraint programming search space on demand and during the execution of the search algorithm. Our study focuses on the determinism of the parallel search versus the sequential one. We consider that the sequential search algorithm is deterministic, then propose an elegant and simple solution introducing a total order on the nodes in which the parallel algorithm always gives the same solution as the sequential one regardless of the number of cores used. To evaluate this deterministic strategy, we ran tests using the Google OR-Tools constraint programming solver on top of our parallel Bobpp framework. The performances are illustrated by solving constraint programming problems modeled in FlatZinc format.

关键词： Parallelism constraint programming Work Stealing Determinism

来源：评论

学校读者我要写书评

暂无评论

Grid Scheduling Considering Energy Consumption Management and Quality of Service

引用

JOURNAL OF GRID COMPUTING 2022年第3期20卷 1-25页

作者： Esmaili, Samaneh Kianfar, Kamran Univ Isfahan Fac Engn Esfahan *** Iran

In this research, the grid scheduling problem has been investigated in order to maximize profit considering the dynamic voltage and frequency scaling technique, customer-centric quality of service and time-dependent energy pricing. Mixed-integer linear programming, constraint programming, a greedy heuristic algorithm along with a hybrid method of genetic algorithm and constraint programming are developed. Some techniques are proposed to improve the efficiency of the presented constraint programming model, and their effectiveness is investigated using a full factorial experiment. Parameters of the proposed hybrid algorithm have been set by Taguchi test. The hybrid meta-heuristic algorithm, with a short execution time, generates solutions of about 18% and 88% better than the best solution of the constraint programming model for large-scale problem instances. The results show that the final profit will be reduced by about 22% if the electricity prices are wrongly considered with a flat rate during the scheduling process.

关键词： Grid scheduling Time-dependent energy pricing Customer-centric quality of service DVFS constraint programming Hybrid genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Coordinated Route Planning of Multiple Fuel-constrained Unmanned Aerial Systems with Recharging on an Unmanned Ground Vehicle for Mission Coverage

引用

JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS 2022年第1期106卷 1-18页

作者： Ramasamy, Subramanian Reddinger, Jean-Paul F. Dotterweich, James M. Childers, Marshal A. Bhounsule, Pranav A. Univ Illinois Dept Mech & Ind Engn Chicago IL 60607 USA US Army DEVCOM Res Lab Aberdeen Proving Ground MD 21005 USA

Small Unmanned Aerial Systems (sUAS) such as quadcopters are ideal for aerial surveillance because of their runway independence, terrain-agnostic maneuverability, low cost, and simple hardware. However, battery capacity constraints limit the effective range and endurance of sUASs, requiring human intervention to replace batteries or perform manual recharging for longer operations. To increase their range, an Unmanned Ground Vehicle (UGV) may provide recharging depot as needed. The problem is then to find optimal paths for the UGV and sUASs to visit mission points and sUAS-UGV rendezvous points for recharging. We present a three-tiered heuristics to solve this computationally hard combinatorial optimization problem: (1) K-means clustering is used to find UGV waypoints, (2) a traveling salesman formulation (TSP) is used to solve the optimal UGV route, and (3) vehicle routing problem formulation (VRP) with capacity constraints, time windows, and dropped visits is used to solve for sUAS routes. We use constraint programming for optimization of the TSP and VRP, achieving a solution for 25 mission points and up to 4 sUASs in about a minute on a standard desktop computer. We also found that constraint programming solvers are 7 - 30 times faster, but 4 - 15% sub-optimal compared to mixed-integer solvers, which provide exact solutions. Further, we used constraint programming solvers in a Monte-Carlo approach to evaluate the role of mission spread, number of clusters, and number of sUASs on the optimal solution. Our contribution is the development of heuristics for route selection of sUAS-UGVs that produces high quality solutions as more mission points and sUASs are added without substantially increasing the computational time.

关键词： Traveling salesman problem Vehicle routing problem K-means clustering Fuel constraints constraint programming Local search heuristics

来源：评论

学校读者我要写书评

暂无评论

Reducing Energy Consumption in Electronic Component Manufacturing through Large Neighborhood Search

Reducing Energy Consumption in Electronic Component Manufact...

引用

2024 Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion

作者： Da Ros, Francesca Di Gaspero, Luca Lackner, Marie-Louise Musliu, Nysret Intelligent Optimization Laboratory DMIF - Università degli Studi di Udine Udine Italy Intelligent Optimization Laboratory DPIA - Università degli Studi di Udine Udine Italy Christian Doppler Laboratory DBAI - TU Wien Vienna Austria

ISBN: (纸本)9798400704956

Amidst the ongoing climate crisis, there is a pressing need to reduce energy consumption - especially in industrial settings, as recognized by the United Nations Sustainability Goals (in particular, 9 and 12). To mitigate energy usage in production, strategically grouping compatible jobs and processing them together in batches, as captured by batch scheduling problems, is often beneficial. The Oven Scheduling Problem (OSP), is an NP-hard real-world parallel batch scheduling problem that arises in the electronic component industry. The goal of the OSP is to schedule jobs on ovens while minimizing total oven operating time, job tardiness, and setup costs. To reduce oven runtime, compatible jobs can be processed simultaneously in batches. The schedule must respect oven eligibility and availability, job release dates, setup times between batches, and oven capacity *** propose and fine-tune a Large Neighborhood Search (LNS) algorithm that uses three different destroy operators and a repair operator based on an exact method (a constraint programming model). Our findings demonstrate that LNS significantly enhances the solution quality for many large instances compared to existing exact methods from the literature. Furthermore, we develop a user-friendly dashboard to facilitate decision-makers in the navigation of the optimization tool. © 2024 is held by the owner/author(s).

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Two-stage and one-group two-dimensional guillotine cutting problems with defects: a CP-based algorithm and ILP formulations

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2022年第6期60卷 1854-1873页

作者： Martin, Mateus Morabito, Reinaldo Munari, Pedro Univ Fed Sao Paulo Inst Sci & Technol Sao Paulo Brazil Univ Fed Sao Carlos Dept Prod Engn Via Washington Luiz Km 235 BR-13565905 Sao Carlos SP Brazil

We address two variants of the two-dimensional guillotine cutting problem that appear in different manufacturing settings that cut defective objects. Real-world applications include the production of flat glass in the glass industry and the cutting of wooden boards with knotholes in the furniture industry. These variants assume that there are several defects in the object, but the items cut should be defective-free;the cutting pattern is limited to two guillotine stages;and the maximum number of copies per item type in the pattern can be limited. The first variant deals with exact 2-stage patterns, while the second with exact 1-group patterns. To effectively solve these problems, we propose a constraint programming (CP) based algorithm as well as different Integer Linear programming (ILP) formulations. The first presented formulations are extensions of the modelling approach of [Martin, M., E. G. Birgin, R. D. Lobato, R. Morabito, and P. Munari. 2020. "Models for the Two-Dimensional Rectangular Single Large Placement Problem with Guillotine Cuts and Constrained Pattern." International Transactions in Operational Research 27: 767-793. doi:] for the case with defects, while the others are novel and more elaborate formulations based on the relative position of the items. We evaluate these three approaches with computational experiments using a set of benchmark instances from the literature. The results show that the approaches find optimal and near-optimal solutions in short processing times for several types of problem instances.

关键词： Cutting and packing guillotine cuts defects 2-stage and 1-group patterns constraint programming iInteger linear programmingt

来源：评论

学校读者我要写书评

暂无评论

Workforce planning and production scheduling in a reconfigurable manufacturing system facing the COVID-19 pandemic

引用

JOURNAL OF MANUFACTURING SYSTEMS 2022年 63卷 563-574页

作者： Vahedi-Nouri, Behdin Tavakkoli-Moghaddam, Reza Hanzalek, Zdenek Dolgui, Alexandre Univ Tehran Coll Engn Sch Ind Engn Tehran Iran Czech Tech Univ IID CIIRC Prague Czech Republic IMT Atlantique LS2N CNRS Nantes France

Due to the outbreak of the COVID-19 pandemic, the manufacturing sector has been experiencing unprecedented issues, including severe fluctuation in demand, restrictions on the availability and utilization of the workforce, and governmental regulations. Adopting conventional manufacturing practices and planning approaches under such circumstances cannot be effective and may jeopardize workers' health and satisfaction, as well as the continuity of businesses. Reconfigurable Manufacturing System (RMS) as a new manufacturing paradigm has demonstrated a promising performance when facing abrupt market or system changes. This paper investigates a joint workforce planning and production scheduling problem during the COVID-19 pandemic by leveraging the adaptability and flexibility of an RMS. In this regard, workers' COVID-19 health risk arising from their allocation, and workers' preferences for flexible working hours are incorporated into the problem. Accordingly, first, novel Mixed-Integer Linear programming (MILP) and constraint programming (CP) models are developed to formulate the problem. Next, exploiting the problem's intrinsic characteristics, two properties of an optimal solution are identified. By incorporating these properties, the initial MILP and CP models are considerably improved. Afterward, to benefit from the strengths of both improved models, a novel hybrid MILP-CP solution approach is devised. Finally, comprehensive computational experiments are conducted to evaluate the performance of the proposed models and extract useful managerial insights on the system flexibility.

关键词： Scheduling Workforce planning COVID-19 pandemic Reconfigurable manufacturing system Reconfigurable machine tool constraint programming

来源：评论

学校读者我要写书评

暂无评论

Maximal-Sum submatrix search using a hybrid contraint programming/linear programming approach

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第3期297卷 853-865页

作者： Derval, Guillaume Schaus, Pierre UCLouvain Louvain Belgium

A Maximal-Sum Submatrix (MSS) maximizes the sum of the entries corresponding to the Cartesian product of a subset of rows and columns from an original matrix (with positive and negative entries). Despite being NP-hard, this recently introduced problem was already proven to be useful for practical data mining applications. It was used for identifying bi-clusters in gene expression data or to extract a sub matrix that is then visualized in a circular plot. The state-of-the-art results for MSS are obtained using an advanced constraint Programing approach that combines a custom filtering algorithm with a Large Neighborhood Search. We improve the state-of-the-art approach by introducing new upper bounds based on linear and mixed-integer programming formulations, along with dedicated pruning algorithms. We experiment on both synthetic and real-life data, and show that our approach outperforms the previous methods. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Maximum-sum submatrix Linear relaxation constraint programming

来源：评论

学校读者我要写书评

暂无评论

Optimization Strategies for Resource-Constrained Project Scheduling Problems in Underground Mining

引用

INFORMS JOURNAL ON COMPUTING 2022年第6期34卷 3042-3058页

作者： Hill, Alessandro Brickey, Andrea J. Cipriano, Italo Goycoolea, Marcos Newman, Alexandra Calif Polytech State Univ San Luis Obispo Dept Ind & Mfg Engn San Luis Obispo CA 93407 USA South Dakota Sch Mines & Technol Min Engn & Management Rapid City SD 57701 USA Univ Adolfo Ibanez Alicanto Labs Santiago 7941169 Chile Univ Adolfo Ibanez Sch Business Santiago 7941169 Chile Colorado Sch Mines Dept Mech Engn Golden CO 80401 USA

Effective computational methods are important for practitioners and researchers working in strategic underground mine planning. We consider a class of problems that can be modeled as a resource-constrained project scheduling problem with optional activities;the objective maximizes net present value. We provide a computational review of math programming and constraint programming techniques for this problem, describe and implement novel problem-size reductions, and introduce an aggregated linear program that guides a list scheduling algorithm running over unaggregated instances. Practical, large-scale planning problems cannot be processed using standard optimization approaches. However, our strategies allow us to solve them to within about 5% of optimality in several hours, even for the most difficult instances.

关键词： underground mine planning resource-constrained project scheduling constraint programming mathematical programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：