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

Exact and metaheuristic methods for a real-world examination timetabling problem

JOURNAL OF SCHEDULING 2023年第4期26卷 353-367页

作者： Carlsson, Mats Ceschia, Sara Di Gaspero, Luca Mikkelsen, Rasmus Ornstrup Schaerf, Andrea Stidsen, Thomas Jacob Riis RISE Res Inst Sweden Uppsala Sweden Univ Udine Udine Italy Tech Univ Denmark Lyngby Denmark

We propose a portfolio of exact and metaheuristic methods for the rich examination timetabling problem introduced by Battistutta et al. (in: Hebrard, Musliu (eds) 17th International conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR-2020), LNCS, vol 12296. Springer, Berlin, pp 69-81, 2020). The problem includes several real-world features that arise in Italian universities, such as examinations split into two parts, possible requirements of multiple rooms for a single examination, and unavailabilities and preferences for periods and rooms. We developed a CP model encoded in the MiniZinc modeling language and solved it with Gecode, as well as two MIP models solved with Gurobi. The first MIP model is encoded natively and the second one again in MiniZinc. Finally, we extended the metaheuristic method based on simulated annealing of Battistutta et al. by introducing a new neighborhood relation. We compare the different techniques on the real-world instances provided by Battistutta et al., which have been slightly refined by correcting some semantic issues. Finally, we developed a solution checker that is publicly available, together with all instances and solutions, for inspection and future comparisons.

关键词： Examination timetabling constraint programming Integer programming Simulated annealing

来源：评论

学校读者我要写书评

暂无评论

Learning to select SAT encodings for pseudo-Boolean and linear integer constraints

引用

constraintS 2023年第3期28卷 397-426页

作者： Ulrich-Oltean, Felix Nightingale, Peter Walker, James Alfred Univ York Dept Comp Sci Deramore Lane York YO10 5GH England

Many constraint satisfaction and optimisation problems can be solved effectively by encoding them as instances of the Boolean Satisfiability problem (SAT). However, even the simplest types of constraints have many encodings in the literature with widely varying performance, and the problem of selecting suitable encodings for a given problem instance is not trivial. We explore the problem of selecting encodings for pseudo-Boolean and linear constraints using a supervised machine learning approach. We show that it is possible to select encodings effectively using a standard set of features for constraint problems;however we obtain better performance with a new set of features specifically designed for the pseudo-Boolean and linear constraints. In fact, we achieve good results when selecting encodings for unseen problem classes. Our results compare favourably to AutoFolio when using the same feature set. We discuss the relative importance of instance features to the task of selecting the best encodings, and compare several variations of the machine learning method.

关键词： constraint programming SAT encodings Machine learning Global constraints Pseudo-Boolean constraints Linear constraints

来源：评论

学校读者我要写书评

暂无评论

Achieving consistency with cutting planes

引用

MATHEMATICAL programming 2023年第1期198卷 507-537页

作者： Davarnia, Danial Rajabalizadeh, Atefeh Hooker, John Iowa State Univ Ind & Mfg Syst Engn Ames IA 50011 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

The primary role of cutting planes is to separate fractional solutions of the linear programming relaxation, which results in tighter bounds for pruning the search tree and reducing its size. Bounding, however, has an indirect impact on the size of the search tree. Cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching, which directly reduces the tree size. A partial assignment is inconsistent with a constraint set when it cannot be extended to a full feasible assignment. The constraint programming community has studied consistency extensively and used it as an effective tool for the reduction of backtracking. We extend this approach to integer programming by defining concepts of consistency that are useful in a branch-and-bound context. We present a theoretical framework for studying these concepts, their connection with the convex hull and their power to exclude infeasible partial assignments. We introduce a new class of cutting planes that target achieving consistency rather than improving dual bounds. Computational experiments on both synthetic and benchmark instances show that the new class of cutting planes can significantly outperform classical cutting planes, such as disjunctive cuts, by reducing the size of the search tree and the solution time. More broadly, we suggest that consistency concepts offer a new perspective on integer programming that can lead to a better understanding of what makes cutting planes work when used in branch-and-bound search.

关键词： Cutting planes Branch-and-bound Consistency Integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

Taming complexity of industrial printing systems using a constraint-based DSL: An industrial experience report

引用

SOFTWARE-PRACTICE & EXPERIENCE 2023年第10期53卷 2026-2064页

作者： Denkers, Jasper Brunner, Marvin van Gool, Louis Vinju, Jurgen J. Zaidman, Andy Visser, Eelco Delft Univ Technol Software Technol Delft Netherlands Canon Prod Printing Venlo Netherlands Ctr Wiskunde & Informat Software Anal & Transformat Amsterdam Netherlands Eindhoven Univ Technol Software Engn & Technol Eindhoven Netherlands

Flexible printing systems are highly complex systems that consist of printers, that print individual sheets of paper, and finishing equipment, that processes sheets after printing, for example, assembling a book. Integrating finishing equipment with printers involves the development of control software that configures the devices, taking hardware constraints into account. This control software is highly complex to realize due to (1) the intertwined nature of printing and finishing, (2) the large variety of print products and production options for a given product, and (3) the large range of finishers produced by different vendors. We have developed a domain-specific language called CSX that offers an interface to constraint solving specific to the printing domain. We use it to model printing and finishing devices and to automatically derive constraint solver-based environments for automatic configuration. We evaluate CSX on its coverage of the printing domain in an industrial context, and we report on lessons learned on using a constraint-based DSL in an industrial context.

关键词： constraint programming digital printing systems domain-specific languages industrial experiences

来源：评论

学校读者我要写书评

暂无评论

Brunovsky Decomposition for Dynamic Interval Localization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2023年第11期68卷 6937-6943页

作者： Rohou, Simon Jaulin, Luc CNRS Lab STICC ENSTA Bretagne UMR F-6285 Brest France

This article proposes a new set-membership method for estimating the trajectories of dynamical systems, when the states are completely unknown and only nonlinear observations are available. The first part of the proposed method is symbolic and follows the decomposition of Brunovsky, i.e., it decomposes the set of differential equations describing the dynamical system into two blocks of constraints: one block gathers nonlinear analytical equations that do not involve differential operators, while the other block is composed of linear chains of integrators. The second part of the method, which relies on the symbolic decomposition, is numerical and based on a contractor approach. It involves a specific optimal operator for narrowing the sets of feasible solutions. This approach is shown to be efficient on a difficult problem of dynamic localization of a mobile robot, without any prior knowledge about its states.

关键词： Brunovsky constraint programming differential equations interval analysis localization nonlinear system

来源：评论

学校读者我要写书评

暂无评论

constraint programming-based Column Generation

引用

ANNALS OF OPERATIONS RESEARCH 2013年第1期204卷 11-32页

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

This paper surveys recent applications and advances of the constraint programming-based Column Generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by constraint programming. This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using constraint programming are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the constraint programming-based Column Generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad-hoc networks.

关键词： Column Generation constraint programming Integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Complexity of minimum-size arc-inconsistency explanations

引用

constraintS 2023年第3期28卷 427-449页

作者： Bessiere, Christian Carbonnel, Clement Cooper, Martin C. Hebrard, Emmanuel Univ Montpellier CNRS Montpellier France Univ Toulouse IRIT Toulouse France LAAS CNRS Toulouse France

Explaining the outcome of programs has become one of the main concerns in AI research. In constraint programming, a user may want the system to explain why a given variable assignment is not feasible or how it came to the conclusion that the problem does not have any solution. One solution to the latter is to return to the user a sequence of simple reasoning steps that lead to inconsistency. Arc consistency is a well-known form of reasoning that can be understood by a human. We consider explanations as sequences of propagation steps of a constraint on a variable (i.e. the ubiquitous revise function in arc-consistency algorithms) that lead to inconsistency. We characterize several cases for which providing a shortest such explanation is easy: For instance when constraints are binary and variables have maximum degree two. However, these polynomial cases are tight. For instance, providing a shortest explanation is NP-hard when constraints are binary and the maximum degree is three, even if the number of variables is bounded. It remains NP-hard on trees, despite the fact that arc consistency is a decision procedure on trees. The problem is not even FPT-approximable unless the FPT not equal W[2] hypothesis is false.

关键词： constraint programming constraint propagation Minimum explanations Complexity

来源：评论

学校读者我要写书评

暂无评论

Automatic error function learning with interpretable compositional networks

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2023年 1-29页

作者： Richoux, Florian Baffier, Jean-Francois AIST Tokyo Japan JFLI CNRS Tokyo Japan IIJ Res Lab Tokyo Japan

In constraint programming, constraints are usually represented as predicates allowing or forbidding combinations of values. However, some algorithms can exploit a finer representation: error functions. By associating a function to each constraint type to evaluate the quality of an assignment, it extends the expressiveness of regular constraint Satisfaction Problem/Constrained Optimization Problem formalisms. Their usage comes with a price though: it makes problem modeling significantly harder, since users must provide a set of error functions that are not always easy to define. Here, we propose a method to automatically learn an error function corresponding to a constraint, given its predicate version only. This is, to the best of our knowledge, the first attempt to automatically learn error functions for hard constraints. In this paper, we also give for the first time a formal definition of combinatorial problems with hard constraints represented by error functions. Our method aims to learn error functions in a supervised fashion, trying to reproduce either the Hamming or the Manhattan distance, by using a graph model we named Interpretable Compositional Networks. This model allows us to get interpretable results. We run experiments on 7 different constraints to show its versatility. Experiments show that our system can learn functions that scale to high dimensions, and can learn fairly good functions over incomplete spaces. We also show that learned error functions can be used efficiently to represent constraints in different classic problems.

关键词： Combinatorial satisfaction Combinatorial optimization constraint programming Problem modeling Error function Interpretable learning

来源：评论

学校读者我要写书评

暂无评论

New formulation for scheduling flexible flow shop problems

引用

INTERNATIONAL JOURNAL OF INTERACTIVE DESIGN AND MANUFACTURING - IJIDEM 2023年第6期17卷 3305-3319页

作者： Esmaelian, Majid Mohammadi, Milad Shahmoradi, Hadi Univ Isfahan Dept Management Hezarjerib StAzadi Sq Esfahan *** Iran

This research extends the constrained vehicle routing problem concept to solve flexible flow shop scheduling problems. Mixed-integer linear programming and constraint programming formulations are developed for a flow shop problem with no-wait, time lags and release time restrictions to minimize the makespan in both permutation and non-permutation schedules. The comparative analysis of various models reveals that constraint programming models have superior computational performance than mixed-integer linear programming models. However, the mixed-integer linear programming models are also timely-efficient. Moreover, the efficiency of developed models is also represented in comparison with several benchmark datasets. Based on the findings, while the objective function values of the mixed-integer linear programming and constraint programming models in non-permutation schedules exhibit lower values than their respective equivalents in permutation schedules, both models demonstrate longer runtime in non-permutation schedules. Results represent that the proposed constraint programming and mixed-integer linear programming models are among the top three models of the benchmark datasets in terms of the number of decision variables and computational performance. One of the limitations of the research is that there is no comprehensive dataset in the literature considering all the restrictions in permutation and non-permutation schedules.

关键词： Flexible flow shop Mixed integer linear programming constraint programming Constrained vehicle routing problem

来源：评论

学校读者我要写书评

暂无评论

On the multiresource flexible job-shop scheduling problem with arbitrary precedence graphs

引用

PRODUCTION AND OPERATIONS MANAGEMENT 2023年第7期32卷 2322-2330页

作者： Kasapidis, Gregory A. Dauzere-Peres, Stephane Paraskevopoulos, Dimitris C. Repoussis, Panagiotis P. Tarantilis, Christos D. Univ Liverpool Management Sch Dept Operat & Supply Chain Management Liverpool Merseyside England Athens Univ Econ & Business Sch Business Dept Management Sci & Technol Athens Greece CNRS Mines St Etienne Dept Mfg Sci & Logist UMR LIMOS 6158 Gardanne France BI Norwegian Business Sch Dept Accounting & Operat Management Oslo Norway City Univ London Bayes Business Sch London England Athens Univ Econ & Business Sch Business Dept Mkt & Commun Athens Greece

This paper aims at linking the work presented in Dauzere-Peres et al. (1998) and more recently in Kasapidis et al. (2021) on the multiresource flexible job-shop scheduling problem with nonlinear routes or equivalently with arbitrary precedence graphs. In particular, we present a mixed integer linear programming (MIP) model and a constraint programming (CP) model to formulate the problem. We also compare the theorems introduced in Dauzere-Peres et al. (1998) and Kasapidis et al. (2021) and propose a new theorem extension. Computational experiments were conducted to assess the efficiency and effectiveness of all propositions. Lastly, the proposed MIP and CP models are tested on benchmark problems of the literature and comparisons are made with state-of-the-art algorithms.

关键词： arbitrary precedence graphs constraint programming flexible job shop scheduling integer linear programming multiple resources nonlinear precedence constraints

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：