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

A constraint programming-based approach to a large-scale energy management problem with varied constraints

JOURNAL OF SCHEDULING 2013年第6期16卷 629-648页

作者： Brandt, Felix Bauer, Reinhard Voelker, Markus Cardeneo, Andreas Res Ctr Informat Technol D-76131 Karlsruhe Germany Karlsruhe Inst Technol Inst Theoret Informat D-76128 Karlsruhe Germany

This paper addresses a large-scale power plant maintenance scheduling and production planning problem, which has been proposed by the ROADEF/EURO Challenge 2010. We develop two lower bounds for the problem: a greedy heuristic and a flow network for which a minimum cost flow problem has to be solved. Furthermore, we present a solution approach that combines a constraint programming formulation of the problem with several heuristics. The problem is decomposed into an outage scheduling and a production planning phase. The first phase is solved by a constraint program, which additionally ensures the feasibility of the remaining problem. In the second phase we utilize a greedy heuristic-developed from our greedy lower bound-to assign production levels and refueling amounts for a given outage schedule. All proposed strategies are shown to be competitive in an experimental evaluation.

关键词： Maintenance scheduling constraint programming Lower bound Flow network Greedy heuristic

来源：评论

学校读者我要写书评

暂无评论

Exact Solution of Graph Coloring Problems via constraint programming and Column Generation

引用

INFORMS JOURNAL ON COMPUTING 2012年第1期24卷 81-100页

作者： Gualandi, Stefano Malucelli, Federico Politecn Milan Dipartimento Elettr & Informat I-20133 Milan Italy

We consider two approaches for solving the classical minimum vertex coloring problem-that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors-namely, constraint programming and column generation. constraint programming is able to solve very efficiently many of the benchmarks but suffers from a lack of effective bounding methods. On the contrary, column generation provides tight lower bounds by solving the fractional vertex coloring problem exploited in a branch-and-price algorithm, as already proposed in the literature. The column generation approach is here enhanced by using constraint programming to solve the pricing subproblem and to compute heuristic solutions. Moreover, new techniques are introduced to improve the performance of the column generation approach in solving both the linear relaxation and the integer problem. We report extensive computational results applied to the benchmark instances: we are able to prove optimality of 11 new instances and to improve the best-known lower bounds on 17 other instances. Moreover, we extend the solution approaches to a generalization of the problem known as the minimum vertex graph multicoloring problem, where a given number of colors has to be assigned to each vertex.

关键词： column generation integer linear programming constraint programming graph coloring

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach to type-2 assembly line balancing problem with assignment restrictions

引用

ASSEMBLY AUTOMATION 2019年第5期39卷 813-826页

作者： Pinarbasi, Mehmet Alakas, Haci Mehmet Yuzukirmizi, Mustafa Kirikkale Univ Dept Ind Engn Kirikkale Turkey

Purpose Main constraints for an assembly line balancing problem (ALBP) are cycle time/number of stations and task precedence relations. However, due to the technological and organizational limitations, several other restrictions can be encountered in real production systems. These restrictions are called as assignment restrictions and can be task assignment, station, resource and distance limitations. The purpose of the study is to evaluate the effects of these restrictions on ALBP using constraint programming (CP) model. Design/methodology/approach A novel CP model is proposed and compared to mixed-integer programming (MIP) as a benchmark. The objective is to minimize the cycle time for a given number of stations. The authors also provide explicit anthology of the assignment restriction effects on line efficiency, the solution quality and the computation time. Findings The proposed approach is verified with the literature test instances and a real-life problem from a furniture manufacturing company. Computational experiments show that, despite the fact that additional assignment restrictions are problematic in mathematical solutions, CP is a versatile exact solution alternative in modelling and the solution quality. Practical implications - Assembly line is a popular manufacturing system in the making of standardized high volume products. The problem of assembly line balancing is a crucial challenge in these settings and consists of assigning tasks to the stations by optimizing one or more objectives. Type-2 AR-ALBP is a specific case with the objective function of minimizing the cycle time for a given number of stations. It further assumes assignment restrictions that can be confronted due to the technological limitations or the strategic decisions of the company management. This is especially encountered in rebalancing lines. Originality/value Several solution approaches such as mathematical modelling, heuristic and meta-heuristic are proposed to solve the ALBP i

关键词： Mixed-integer programming Assembly line balancing Assignment restrictions constraint programming Type-2 problem

来源：评论

学校读者我要写书评

暂无评论

Reactive scheduling framework based on domain knowledge and constraint programming

引用

COMPUTERS & CHEMICAL ENGINEERING 2010年第12期34卷 2129-2148页

作者： Novas, Juan M. Henning, Gabriela P. Univ Nacl Litoral CONICET INTEC RA-3450 Guemes Santa Fe Argentina

Industrial environments frequently face disruptive events. This contribution presents a support framework, aimed at addressing the repair-based reactive scheduling problem. It is based on an explicit object-oriented domain representation and a constraint programming (CP) approach. When an unforeseen event occurs, the framework captures the in-progress agenda status, as well as the event effect on it. Based on this information, a rescheduling problem specification is developed. Tasks to be rearranged are recognized and the set of the most suitable rescheduling action types (e.g. shift-jump, reassign, freeze) is identified. Since a given specification may lead to several solutions, the second stage relies on a CP model to address the problem just defined. To create such model, action types are automatically transformed into constraints. Provided that good quality schedules can be reached in low CPU times, alternative solution scenarios focusing on stability and regular performance measures can be posed for each problem. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Reactive scheduling Batch plants Decision support systems Knowledge-based scheduling constraint programming

来源：评论

学校读者我要写书评

暂无评论

Solving production scheduling with earliness/tardiness penalties by constraint programming

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2011年第4期22卷 553-562页

作者： Kelbel, Jan Hanzalek, Zdenek Czech Tech Univ Fac Elect Engn Dept Control Engn Prague 12135 2 Czech Republic

This paper deals with an application of constraint programming in production scheduling with earliness and tardiness penalties that reflects the scheduling part of the Just-In-Time inventory strategy. Two scheduling problems are studied, an industrial case study problem of lacquer production scheduling, and also the job-shop scheduling problem with earliness/tardiness costs. The paper presents two algorithms that help the constraint programming solver to find solutions of these complex problems. The first algorithm, called the cost directed initialization, performs a greedy initialization of the search tree. The second one, called the time reversing transformation and designed for lacquer production scheduling, reformulates the problem to be more easily searchable when the default search or the cost directed initialization is used. The conducted experiments, using case study instances and randomly generated problem instances, show that our algorithms outperform generic approaches, and on average give better results than other nontrivial algorithms.

关键词： Production scheduling Earliness/tardiness cost constraint programming

来源：评论

学校读者我要写书评

暂无评论

Integer programming, constraint programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems

引用

INFORMS JOURNAL ON COMPUTING 2022年第1期34卷 297-314页

作者： MacNeil, Moira Bodur, Merve Univ Toronto Dept Mech & Ind Engn Toronto ON M5S 3G8 Canada

Given an integer dimension K and a simple, undirected graph G with positive edge weights, the Distance Geometry Problem (DGP) aims to find a realization function mapping each vertex to a coordinate in R-K such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G. The so-called discretization assumptions reduce the search space of the realization to a finite discrete one, which can be explored via the branch-and-prune (BP) algorithm. Given a discretization vertex order in G, the BP algorithm constructs a binary tree where the nodes at a layer provide all possible coordinates of the vertex corresponding to that layer. The focus of this paper is on finding optimal BP trees for a class of discretizable DGPs. More specifically, we aim to find a discretization vertex order in G that yields a BP tree with the least number of branches. We propose an integer programming formulation and three constraint programming formulations that all significantly outperform the state-of-the-art cutting-plane algorithm for this problem. Moreover, motivated by the difficulty in solving instances with a large and low-density input graph, we develop two hybrid decomposition algorithms, strengthened by a set of valid inequalities, which further improve the solvability of the problem. Summary of Contribution: We present a new model to solve a combinatorial optimization problem on graphs, MIN DOUBLE, which comes from the highly active area of distance geometry and has applications in a wide variety of fields. We use integer programming (IP) and present the first constraint programming(CP) models and hybrid decomposition methods, implemented as a branch-and-cut procedure, for MIN DOUBLE. Through an extensive computational study, we show that our approaches advance the state of the art for MIN DOUBLE. We accomplish this by not only combining generic techniques from IP and CP but also exploring the structure of the problem in developing valid inequal

关键词： distance geometry discretization order integer programming constraint programming decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

Revisiting AES related-key differential attacks with constraint programming

引用

INFORMATION PROCESSING LETTERS 2018年第Nov.期139卷 24-29页

作者： Gerault, David Lafourcade, Pascal Minier, Marine Solnon, Christine Univ Clermont Auvergne LIMOS UMR 6158 F-63173 Clermont Ferrand France Univ Lorraine LORIA UMR 7503 F-54506 Vandoeuvre Les Nancy France Univ Lyon INSA Lyon LIRIS CNRS UMR5205 Lyon France

The Advanced Encryption Standard (AES) is one of the most studied symmetric encryption schemes. During the last years, several attacks have been discovered in different adversarial models. In this paper, we focus on related-key differential attacks, where the adversary may introduce differences in plaintext pairs and also in keys. We show that constraint programming (CP) can be used to model these attacks, and that it allows us to efficiently find all optimal related-key differential characteristics for AES-128, AES-192 and AES-256. In particular, we improve the best related-key differential for the whole AES-256 and give the best related-key differential on 10 rounds of AES-192, which is the differential trail with the longest path. Those results allow us to improve existing related-key distinguishers, basic related-key attacks and q-multicollisions on AES-256. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms AES Related-key attacks constraint programming

来源：评论

学校读者我要写书评

暂无评论

New lower bounds based on column generation and constraint programming for the pattern minimization problem

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第11期36卷 2944-2954页

作者： Alves, Claudio Macedo, Rita de Carvalho, Jose Valerio Univ Minho Ctr Invest Algoritmi Escola Engn P-4710057 Braga Portugal

The pattern minimization problem is a cutting and packing problem that consists in finding a cutting plan with the minimum number of different patterns. This objective may be relevant when changing from one pattern to another involves a cost for setting up the cutting machine. When the minimization of the number of different patterns is done by assuming that no more than the minimum number of rolls can be used, the problem is also referred to as the cutting stock problem with setup costs. Most of the approaches described in the literature are based on heuristics. Solving the problem exactly has been a real challenge, and only very few exact solution methods have been reported so far in the literature. In this paper, we intend to contribute to the resolution of the pattern minimization problem with new results. We explore a different integer programming model that can be solved using column generation, and we describe different strategies to strengthen it, among which are constraint programming and new families of valid inequalities. Lower bounds for the pattern minimization problem are derived from the new integer programming model, and also from a constraint programming model. Our approaches were tested on a set of real instances, and on a set of random instances from the literature. For these instances, the computational experiments show a clear improvement on the quality of the lower bounds. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Cutting and packing problems Pattern minimization problem Lower bounds Integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach for the premarshalling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第2期306卷 668-678页

作者： Jimenez-Piqueras, Celia Ruiz, Ruben Parreno-Torres, Consuelo Alvarez-Valdes, Ramon Univ Politecn Valencia Inst Tecnol Informat Grp Sistemas Optimizac Aplicada Ciudad Politecn Innovac Edif 8GAcc BCamino Vera S-N Valencia 46021 Spain Univ Valencia Dept Stat & Operat Res Doctor Moliner 50 Valencia 46100 Spain

The enormous amount of containers handled at ports hampers the efficiency of terminal operations. The optimization of crane movements is crucial for speeding up the loading and unloading of vessels. To this end, the premarshalling problem aims to reorder a set of containers placed in adjacent stacks with a minimum number of crane movements, so that a container with an earlier retrieval time is not below one with a later retrieval time. In this study, we present a series of constraint programming models to optimally solve the premarshalling problem. Extensive computational comparisons show that the best proposed constraint programming formulation yields better results than the state-of-the-art integer pro-gramming approach. A salient finding in this paper is that the logic behind the model construction in constraint programming is radically different from that of more traditional mixed integer linear program-ming models.(c) 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://***/licenses/by-nc-nd/4.0/ )

关键词： Logistics Container terminal optimization Premarshalling problem constraint programming

来源：评论

学校读者我要写书评

暂无评论

Enhancing the performance of constraint programming through the introduction of linear programming

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2001年第1期52卷 82-92页

作者： Little, J Brunel Univ Dept Math Sci Uxbridge UB8 3PH Middx England

constraint programming (CP) has been successful in a number of combinatorial search and discrete optimisation problems. Yet other more traditional approaches, such as Integer programming (IP), can still give a better performance on the same problem types. Central to IFS success is its reliance an a fast Linear programming (LP) solver providing solutions during the search to the corresponding relaxed problems. These solutions are used to guide the search within IP as well as a means of detecting infeasibility and integrality. This paper shows that there is scope also to include LP within the CP framework, in order to similarly guide the CP search. The problems examined here are one for which CP on its own had proved markedly inferior to IP. Hence a hybrid solver based on the CP search and using an LP solver is configured and run on these problems. The outcome shows that using the LP solver within the CP search is a valuable addition to the available search strategies. An improved performance over the CP-only strategies is obtained and, further, comparable results are obtained to those from IF. Overall, CP + LP can be considered as a more robust approach than either CP or IP on their own on a variety of combinatorial search problems.

关键词： integer programming linear programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：