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

Integer and constraint programming model formulations for flight-gate assignment problem

OPERATIONAL RESEARCH 2022年第1期22卷 135-163页

作者： Ornek, M. Arslan Ozturk, Cemalettin Sugut, Ipek Yasar Univ Dept Ind Engn TR-35100 Izmir Turkey United Technol Res Ctr Ireland Raytheon Technol Cork Ireland Turkish Airlines Istanbul Turkey

Flight-gate assignment problems are complex real world problems involving different constraints. Some of these constraints include plane-gate eligibility, assigning planes of the same airline and planes getting service from the same ground handling companies to adjacent gates, buffers for changes in flight schedules, night stand flights, priority of some gates over others, and so on. In literature there are numerous models to solve this highly complicated problem and tackle its complexity. In this study, first, we propose two different integer programming models, namely, timetabling and assignment based models, and then a scheduling based constraint programming model to solve the problem to optimality. These models prove to be highly efficient in that the computational times are quite short. We also present the results for one day operation of an airport using real data. Finally, we present our conclusions based on our study along with the possible further research.

关键词： Flight-gate assignment problem Integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

Integer programming, constraint programming, and Metaheuristic Approaches for Static Optimization of Anycast Flows in Elastic Optical Networks

引用

NETWORKS 2015年第4期66卷 253-266页

作者： Kucharzak, Michal Walkowiak, Krzysztof Kopec, Pawel Bulira, Damian Kasprzak, Andrzej Wroclaw Univ Technol Dept Syst & Comp Networks PL-50370 Wroclaw Poland

Elastic optical network (EON) is a novel optical technology introduced recently to provide flexible and multibitrate data transmission in the optical layer. Since many new network services including cloud computing and content delivery networks are provisioned with the use of specialized data centers located in different network nodes, in place of one-to-one unicast transmission, the anycast transmission defined as one-toone-of-many gains much popularity as a quite simple way to improve network performance. Therefore, this article focuses on modeling and static optimization of anycast flows in EONs. In particular, a NP-hard Routing and Spectrum Allocation for Restoration of Anycast Flows (RSA/RAF) problem is formulated. Next, various optimization approaches are proposed to solve this problem, namely, integer linear programming (ILP) using branch and bound algorithm, constraint programming (CP), and various heuristic approaches. Extensive numerical experiments are run to evaluate and compare all proposed methods. The main conclusion is that in some cases the CP approach is more efficient than the ILP modeling. Moreover, the results show that the SA algorithm significantly outperforms other heuristic methods. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 253-266 2015

关键词： elastic optical network integer modeling constraint programming optimization

来源：评论

学校读者我要写书评

暂无评论

constraint programming Approach to Coverage-Path Planning for Autonomous Multi-UAV Infrastructure Inspection

引用

DRONES 2023年第9期7卷

作者： Matlekovic, Lea Schneider-Kamp, Peter Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense Denmark

This article presents a constraint modeling approach to global coverage-path planning for linear-infrastructure inspection using multiple autonomous UAVs. The problem is mathematically formulated as a variant of the Min-Max K-Chinese Postman Problem (MM K-CPP) with multi-weight edges. A high-level constraint programming language is used to model the problem, which enables model execution with different third-party solvers. The optimal solutions are obtained in a reasonable time for most of the tested instances and different numbers of vehicles involved in the inspection. For some graphs with multi-weight edges, a time limit is applied, as the problem is NP-hard and the computation time increases exponentially. Despite that, the final total inspection cost proved to be lower when compared with the solution obtained for the unrestricted MM K-CPP with single-weight edges. This model can be applied to plan coverage paths for linear-infrastructure inspection, resulting in a minimal total inspection time for relatively simple graphs that resemble real transmission networks. For more extensive graphs, it is possible to obtain valid solutions in a reasonable time, but optimality cannot be guaranteed. For future improvements, further optimization could be considered, or different models could be developed, possibly involving artificial neural networks.

关键词： multi-UAVs path planning infrastructure inspection constraint programming optimization

来源：评论

学校读者我要写书评

暂无评论

Towards fast Vickrey pricing using constraint programming

引用

ARTIFICIAL INTELLIGENCE REVIEW 2004年第3-4期21卷 335-352页

作者： Holland, A O'Sullivan, B Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Constraint Computat Ctr Cork Ireland

Ensuring truthfulness amongst self-interested agents bidding against one another in an auction can be computationally expensive when prices are determined using the Vickrey-Clarke-Groves (VCG) mechanism. This mechanism guarantees that each agent's dominant strategy is to tell the truth, but it requires solving n + 1 optimization problems when the overall optimal solution involves n agents. This paper first examines a case-study example demonstrating how Operations Research techniques can be used to compute Vickrey prices efficiently. In particular, the case-study focuses on the Assignment Problem. We show how, in this case, Vickrey prices can be computed in the same asymptotic time complexity as that of the original optimization problem. This case-study can be seen as serving a pedagogical role in the paper illustrating how Operations Research techniques can be used for fast Vickrey pricing. We then propose a constraint programming approach that can be used in a more general context, where nothing is assumed about the nature of the constraints that must be satisfied or the structure of the underlying problem. In particular, we demonstrate how nogood learning can be used to improve the efficiency of constraint-based Vickrey pricing in combinatorial auctions.

关键词： combinational auctions constraint programming Vickrey pricing

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems

引用

ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING 2010年第6期26卷 725-743页

作者： Zeballos, L. J. Univ Nacl Litoral Fac Ingn Quim Dept Ingn Ind RA-3000 Santa Fe Argentina Univ Nacl Litoral INTEC CONICET RA-3000 Santa Fe Argentina

This paper presents a constraint programming (CP) methodology to deal with the scheduling of flexible manufacturing systems (FMSs). The proposed approach, which consists of both a model and a search strategy, handles several features found in industrial environments, such as limitations on number of tools in the system, lifetime of tools, as well as tool magazine capacity of machines. In addition, it tackles the problem in a integrated way by considering tool planning and allocation, machine assignment, part routing, and task timing decisions altogether in the approach. The formulation, which is able to take into account a variety of objective functions, has been successfully applied to the solution of test problems of various sizes and degrees of difficulty. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： constraint programming Flexible manufacturing systems Scheduling Tool management

来源：评论

学校读者我要写书评

暂无评论

constraint programming for reservoir operation optimization of Bhumibol dam

引用

APPLIED WATER SCIENCE 2024年第6期14卷 142页

作者： Sawangphol, Wudhichart Kraisangka, Jidapa Rittima, Areeya Phankamolsil, Yutthana Tabucanon, Allan Sriratana Talaluxmana, Yutthana Vudhivanich, Varawoot Mahidol Univ Fac ICT Nakhon Pathom 73170 Thailand Mahidol Univ Fac Engn Nakhon Pathom 73170 Thailand Mahidol Univ Divers Engn Kanchanaburi Thailand Mahidol Univ Fac Environm & Resource Studies Nakhon Pathom 73170 Thailand Kasetsart Univ Fac Engn Dept Water Resources Engn Bangkok 10930 Thailand Kasetsart Univ Fac Engn Kamphaeng Saen Dept Irrigat Engn Nakhon Pathom 73140 Thailand

The modern constraint programming (CP) was adopted to minimize water scarcity and excessive water which are the critical issues in reservoir operation of Bhumibol Dam (BB) to solve consecutive droughts in the Chao Phraya River Basin (CPYRB), Thailand. The situations of the severe droughts have been frequently occurred in a broad area of CPYRB due to an extremely low rainfall leading to unusually low water levels and inflow in major reservoirs. Therefore, multi-objective optimization was conducted to characterize the actual operation and physical reservoir system of BB Dam. Two different CP models with seasonal and yearly constraints were manipulated using MiniZinc programming language and the constraint solver IPOPT to find the optimal daily release scheme from 2000 to 2018 of BB Dam. The potential of downstream flow conditions was also considered to partially supply downstream water demand and store savable water in a reservoir for subsequent use during possible future droughts. The results reveal that CP models can diminish some extent of yearly reservoir release, while daily long-term release scheme conforms well with the actual operation particularly during dry and wet seasons in specific drought years. These mean that amount of reservoir water of approximately 47.12-103.83 MCM/year can be saved and stored in reservoir for subsequent use in CPYRB when CP models are deployed. This results in a reservoir storage increase of 7.10-7.94% at the end of the wet season for seasonal and yearly CP models, respectively. When potential side flow is considered, the increase climbs up to 10.49%. This envisages the higher possibility of supplying reservoir water for agricultural water needs over the dry season in the Greater Chao Phraya Irrigation Scheme. As the potential hydraulic head is subject to increased reservoir water storage, therefore, the increase in hydropower production is definitely found of ranging from + 6.10% to + 13.79% by these two sorts of CP models. In add

关键词： constraint programming MiniZinc modelling language Reservoir operation Bhumibol dam Chao Phraya river basin

来源：评论

学校读者我要写书评

暂无评论

constraint programming over nonlinear constraints

引用

Science of Computer programming 1998年第1-2期30卷 83-118页

作者： Pascal Van Hentenryck Laurent Michel Frédéric Benhamou Brown University Box 1910 Providence RI 02912 USA Université d'Orléans rue Léonard de Vinci BP 6759 F-45067 Orléans France

This paper is an introduction to Newton, a constraint programming language over nonlinear real constraints. Newton originates from an effort to reconcile the declarative nature of constraint logic programming (CLP) languages over intervals with advanced interval techniques developed in numerical analysis, such as the interval Newton method. Its key conceptual idea is to introduce the notion of box-consistency, which approximates arc-consistency, a notion well-known in artificial intelligence. Box-consistency achieves an effective pruning at a reasonable computation cost and generalizes some traditional interval operators. Newton has been applied to numerous applications in science and engineering, including nonlinear equation-solving, unconstrained optimization, and constrained optimization. It is competitive with continuation methods on their equation-solving benchmarks and outperforms the interval-based methods we are aware of on optimization problems.

关键词： constraint programming Nonlinear programming Interval reasoning

来源：评论

学校读者我要写书评

暂无评论

constraint programming model for multi-manned assembly line balancing problem

引用

COMPUTERS & OPERATIONS RESEARCH 2020年 124卷 105069-105069页

作者： Cil, Zeynel Abidin Kizilay, Damla Izmir Democracy Univ Dept Ind Engn Izmir Turkey

In recent years, the multi-manned assembly line has become popular since the large-sized products allow more than one operator working simultaneously on the same product in a workstation. This line usually occurs in large-size products such as cars, buses, trucks, and so on. The multi-manned assembly line offers several advantages, such as fewer number of workers/workstation and less cycle time to improve the performance of the system. However, it has been analyzed by a few papers in literature due to being a relatively new and complex problem. The current study aims to develop an efficient exact solution approach, constraint programming, to solve from small to large-size problems by minimizing the cycle time as a primary objective and the total number of workers as a secondary objective. First, two mixed-integer linear programming (MILP) models are proposed based on previous studies to solve the small test cases of the problem optimally. However, the models are not capable of solving the large-size test instances. Therefore, a constraint programming (CP) model is formulated to address both small and large-size data sets. The results of the CP model are compared with two MILP models and two heuristic algorithms available in the literature. The computational results indicate that the CP model discovers optimal solutions, approximately 90% of all the instances, and small optimality gaps in the remaining instances. It is useful to highlight that the CP model is highly concise and solved by a black-box, commercial solver. (c) 2020 Elsevier Ltd. All rights reserved.

关键词： constraint programming Multi-manned assembly line balancing Mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

constraint programming Approach to Reconfigurable Processor Extension Generation and Application Compilation

引用

ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS 2012年第2期5卷 10-10页

作者： Martin, Kevin Wolinski, Christophe Kuchcinski, Krzysztof Floch, Antoine Charot, Francois Lund Univ Dept Comp Sci S-22100 Lund Sweden Univ Rennes 1 IRISA F-35014 Rennes France INRIA Rennes France

In this article, we present a constraint programming approach for solving hard design problems present when automatically designing specialized processor extensions. Specifically, we discuss our approach for automatic selection and synthesis of processor extensions as well as efficient application compilation for these newly generated extensions. The discussed approach is implemented in our integrated design framework, IFPEC, built using constraint programming (CP). In our framework, custom instructions, implemented as processor extensions, are defined as computational patterns and represented as graphs. This, along with the graph representation of an application, provides a way to use our CP framework equipped with subgraph isomorphism and connected component constraints for identification of processor extensions as well as their selection, application scheduling, binding, and routing. All design steps assume architectures composed of runtime reconfigurable cells, implementing selected extensions, tightly connected to a processor. An advantage of our approach is the possibility of combining different heterogeneous constraints to represent and solve all our design problems. Moreover, the flexibility and expressiveness of the CP framework makes it possible to solve simultaneously extension selection, application scheduling, and binding and improve the quality of the generated results. The article is largely illustrated with experimental results.

关键词： Design Experimentation Reconfigurable architectures resource assignment scheduling system-level synthesis constraint programming

来源：评论

学校读者我要写书评

暂无评论

An Application of the constraint programming to the Design and Operation of Synthetic Aperture Radars

An Application of the Constraint Programming to the Design a...

引用

IEEE Conference on High Performance Extreme Computing (HPEC)

作者： Holzrichter, Michael Sandia Natl Labs Albuquerque NM 87185 USA

ISBN: (纸本)9781467315760;9781467315777

The design and operation of synthetic aperture radars require compatible sets of hundreds of quantities. Compatibility is achieved when these quantities satisfy constraints arising from physics, geometry etc. In the aggregate these quantities and constraints form a logical model of the radar. In practice the logical model is distributed over multiple people, documents and software modules thereby becoming fragmented. Fragmentation gives rise to inconsistencies and errors. The SAR Inference Engine addresses the fragmentation problem by implementing the logical model of a Sandia synthetic aperture radar in a form that is intended to be usable from system design to mission planning to actual operation of the radar. These diverse contexts require extreme flexibility that is achieved by employing the constraint programming paradigm.

关键词： synthetic aperture radar constraint programming propagation networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：