The final step of the typical process of developing educational and psychological tests is to place the selected test items in a formatted form. The step involves the grouping and ordering of the items to meet a varie...
详细信息
The final step of the typical process of developing educational and psychological tests is to place the selected test items in a formatted form. The step involves the grouping and ordering of the items to meet a variety of formatting constraints. As this activity tends to be time-intensive, the use of mixed-integer programming (MIP) has been proposed to automate it. The goal of this article is to show how constraint programming (CP) can be used as an alternative to automate test-form generation problems with a large variety of formatting constraints, and how it compares with MIP-based form generation as for its models, solutions, and running times. Two empirical examples are presented: (i) automated generation of a computerized fixed-form;and (ii) automated generation of shadow tests for multistage testing. Both examples show that CP works well with feasible solutions and running times likely to be better than that for MIP-based applications.
Constructive learning is the task of learning to synthesize structured objects from data. Examples range from classical sequence labeling to layout synthesis and drug design. Learning in these scenarios involves repea...
详细信息
ISBN:
(纸本)9780999241127
Constructive learning is the task of learning to synthesize structured objects from data. Examples range from classical sequence labeling to layout synthesis and drug design. Learning in these scenarios involves repeatedly synthesizing candidates subject to feasibility constraints and adapting the model based on the observed loss. Many synthesis problems of interest are non-standard: they involve discrete and continuous variables as well as arbitrary constraints among them. In these cases, widespread formalisms (like linear programming) can not be applied, and the developer is left with writing her own ad-hoc solver. This can be very time consuming and error prone. We introduce Pyconstruct, a Python library tailored for solving real-world constructive problems with minimal effort. The library leverages max-margin approaches to decouple learning from synthesis and constraint programming as a generic framework for synthesis. Pyconstruct enables easy prototyping of working solutions, allowing developers to write complex synthesis problems in a declarative fashion in few lines of code. The library is available at: http://***/2st8nt3
constraint programming (CP) is a powerful declarative programming paradigm combining inference and search in order to find solutions to various type of constraint systems. Dealing with highly disjunctive constraint sy...
详细信息
ISBN:
(纸本)9781538674499
constraint programming (CP) is a powerful declarative programming paradigm combining inference and search in order to find solutions to various type of constraint systems. Dealing with highly disjunctive constraint systems is notoriously difficult in CP. Apart from trying to solve each disjunct independently from each other, there is little hope and effort to succeed in constructing intermediate results combining the knowledge originating from several disjuncts. In this paper, we propose If Then Else (ITE), a lightweight approach for implementing stratified constructive disjunction and negation on top of an existing CP solver, namely SICStus Prolog clp (FD). Although constructive disjunction is known for more than three decades, it does not have straightforward implementations in most CP solvers. ITE is a freely available library proposing stratified and constructive reasoning for various operators, including disjunction and negation, implication and conditional. Our preliminary experimental results show that ITE is competitive with existing approaches that handle disjunctive constraint systems.
The paper considers two kinds of optimization methods: constraint programming and metaheuristic search. It shows how each of the approaches can be applied to multiple instances of the job shop scheduling problem and c...
详细信息
ISBN:
(纸本)9781538644218
The paper considers two kinds of optimization methods: constraint programming and metaheuristic search. It shows how each of the approaches can be applied to multiple instances of the job shop scheduling problem and compares the performance of these approaches among themselves and also under various parameter settings. It is shown that, given the instances of the problem and the parameter configurations considered in the paper, constraint programming clearly outperforms the other approaches. In its final section, the paper outlines further conclusions as well as suggestions for future work.
We consider a vehicle routing problem which seeks to minimize cost subject to time window and synchronization constraints. In this problem, the fleet of vehicles is categorized into regular and special vehicles. Some ...
详细信息
This paper proposes a scheduling method for fork-join malleable tasks based on constraint programming (CP). For a given task-graph, each of the tasks can be split into multiple sub-tasks, and each sub-task is schedule...
详细信息
ISBN:
(纸本)9781538691823
This paper proposes a scheduling method for fork-join malleable tasks based on constraint programming (CP). For a given task-graph, each of the tasks can be split into multiple sub-tasks, and each sub-task is scheduled independently. The proposed method decides the number of sub-tasks to be split, and the execution order of tasks in such a way that the overall schedule length is minimized. Experimental results show that our CP-based scheduling method could find better schedules than the state-of-the-art method which is based on integer linear programming.
This work studies the Unrelated Parallel Machine scheduling problem subject to additional Resources (UPMR). A set of jobs are to be processed by a set of unrelated parallel machines. The processing time and the number...
详细信息
ISBN:
(纸本)9783319754208;9783319754192
This work studies the Unrelated Parallel Machine scheduling problem subject to additional Resources (UPMR). A set of jobs are to be processed by a set of unrelated parallel machines. The processing time and the number of needed resources for each job depend on the machine processing it. Resources are renewable and available in a limited amount. The objective to minimize is the maximum completion time. We formulate the problem using a constraint programming model and solve it using the state-of-the-art solver. We compare the results of this model against the existing approaches of the literature on two sets of small and medium instances. On the set of small instances, we show that the proposed model outperforms existing approaches and optimality is attained for all instances of the set. We further investigate its performance on the medium instances and show that it is able to reach more optimal solutions than any performing approach.
The research work carried out in this dissertation proposes a new mechanism to apply a strategic shifting of Estimated Take-Off Times within their Calculated Take-Off Time Windows to reduce the probability of Air Traf...
详细信息
The research work carried out in this dissertation proposes a new mechanism to apply a strategic shifting of Estimated Take-Off Times within their Calculated Take-Off Time Windows to reduce the probability of Air Traffic Controllers interventions. This dissertation focuses on improving the air traffic dynamic demand capacity balance by using means of the prompt identification of concurrence events at network level, the analysis of spatio-temporal interdependencies and the mitigation of the detected concurrence events. These measures can be considered as short-term Air Traffic Flow and Capacity Management (ATFCM) measures that could be applied at local level that could reducing traffic peaks for the whole European airspace. The underlying philosophy is to capitalise present freedom degrees between layered Air Traffic Management (ATM) planning tools that sequence departures at airports. The work contributes to the well-accepted and widely spread research topic Trajectory Based Operation (TBO) that enhances the design of new Decision Support Tools (DST). The dissertation is aligned with a European H2020 Research project called "Partake". The main contributions of the Doctoral Thesis is the development and implementation of a consecutive methodology for detecting concurrence events, analysing the trajectory interdependencies and using a mitigation method based on constraint programming to determine the Estimated Take-Off Time shifts. Furthermore, the doctoral thesis includes a strong experimental component focusing on validating the set of tools and its application to a realistic scenario located in the London Terminal Manoeuvring Area. This research topic follows to some extend my study background Logistics because the European Air Traffic Management (ATM) system has to be competitive in the way to support the Airspace User (AU's) demands up to a certain point e. g. satisfying the right time (e. g. departure slots), the right costs (e. g. suitable level of Air Traffic
In this thesis a set of tools based on guaranteed methods are presented in order to solve multi-physics dynamic problems. These systems can be applied in various domains such that engineering design process, model of ...
详细信息
In this thesis a set of tools based on guaranteed methods are presented in order to solve multi-physics dynamic problems. These systems can be applied in various domains such that engineering design process, model of chemical reactions, simulation of biological systems or even to predict athletic *** resolution of these optimization problems is made of two stages. The first one consists in defining a mathematical model by setting up the equations for the problem. The model is made of a set of variables, a set of algebraic and functional constraints and cost functions. The latter are used in the second stage in order to extract the optimal solutions from the model depending on several criteria (volume, weight, etc).Algebraic constraints are used to describe the static properties of the system (quantity, size, density, etc). They are non-linear, non-convex and sometimes discontinuous. Functional constraints are used to manipulate dynamic quantities. These constraints can be quite simple such as monotony or periodicity or they can be more complex such as simple or piecewise differential constraints. Differential equations are used to describe physico-chemical properties (magnetic, thermal, etc) and other features evolving with the component use. Several levels of approximation exist for each of these two stages. These approximations give some relevant results but they do not guarantee the feasibility nor the optimality of the *** presenting a set of guaranteed methods in order to perform the guaranteed integration of ordinary differential equations, a peculiar type of hybrid system that can be modeled with piecewise ordinary differential equation is considered. A new method that computes guaranteed integration of these piecewise ordinary differential equations is developed through an extension of the initial algorithm based on several proofs and theorems. In a second step these algorithms are gathered within a contractor programming module that
Operating Room (OR) Scheduling is one of the most critical problems at the operational level for hospital managers. A useful strategy for OR scheduling, especially in large hospitals is the block strategy. In this str...
详细信息
Operating Room (OR) Scheduling is one of the most critical problems at the operational level for hospital managers. A useful strategy for OR scheduling, especially in large hospitals is the block strategy. In this strategy, a specific time is blocked for each surgeon or surgical team. This strategy usually leads to unused operating rooms' capacity. To overcome this problem, in this article, a novel modified block strategy is presented for the daily scheduling of elective patients. This study aims to find the optimal sequence and schedule of patients by minimizing the cost of overtime, makespan and completion time of surgeons' operations by considering the resource constraints. Considering the limitations and real conditions of Al-Zahra Hospital, the largest educational hospital in Isfahan, Iran, is also an aspect of this study. The problem is modeled by mixed integer programming and constraint programming (CP). The performance of the models is verified by several random test instances. The results indicate that CP is more efficient than mathematical modeling in terms of the computational time for solving the considered problems, especially for large-size instances. The average percent of improvement in computational time is about 53% using the CP model. The proposed CP model is also used to solve real problem instances from Al-Zahra hospital. The results show that by using the CP model, the completion time of surgeons' operations is shortened by 9% and ORs' overtime and makespan objectives are reduced by 55% and 20% respectively. (C) 2019 Elsevier Ltd. All rights reserved.
暂无评论