Models and algorithms for simple disjunctive temporal problems

• URL: http://arxiv.org/abs/2302.02644v1
• Date: Mon, 6 Feb 2023 09:40:24 GMT
• Title: Models and algorithms for simple disjunctive temporal problems
• Authors: Carlo S. Sartori, Pieter Smet, Greet Vanden Berghe
• Abstract summary: We focus on the case where events may have an arbitrarily large number of release and due dates. We provide three mathematical models to describe this problem using constraint programming and linear programming. We implement algorithms from the literature and provide the first in-depth empirical study comparing methods to solve simple disjunctive temporal problems.
• Score: 0.8793721044482611
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Simple temporal problems represent a powerful class of models capable of describing the temporal relations between events that arise in many real-world applications such as logistics, robot planning and management systems. The classic simple temporal problem permits each event to have only a single release and due date. In this paper, we focus on the case where events may have an arbitrarily large number of release and due dates. This type of problem, however, has been referred to by various names. In order to simplify and standardize nomenclatures, we introduce the name Simple Disjunctive Temporal Problem. We provide three mathematical models to describe this problem using constraint programming and linear programming. To efficiently solve simple disjunctive temporal problems, we design two new algorithms inspired by previous research, both of which exploit the problem's structure to significantly reduce their space complexity. Additionally, we implement algorithms from the literature and provide the first in-depth empirical study comparing methods to solve simple disjunctive temporal problems across a wide range of experiments. Our analysis and conclusions offer guidance for future researchers and practitioners when tackling similar temporal constraint problems in new applications. All results, source code and instances are made publicly available to further assist future research.

Related papers

• Endogenous Macrodynamics in Algorithmic Recourse [52.87956177581998]
  Existing work on Counterfactual Explanations (CE) and Algorithmic Recourse (AR) has largely focused on single individuals in a static environment. We show that many of the existing methodologies can be collectively described by a generalized framework. We then argue that the existing framework does not account for a hidden external cost of recourse, that only reveals itself when studying the endogenous dynamics of recourse at the group level.
  arXiv  Detail & Related papers  (2023-08-16T07:36:58Z)
• Unlocking Temporal Question Answering for Large Language Models with Tailor-Made Reasoning Logic [84.59255070520673]
  Large language models (LLMs) face a challenge when engaging in temporal reasoning. We propose TempLogic, a novel framework designed specifically for temporal question-answering tasks.
  arXiv  Detail & Related papers  (2023-05-24T10:57:53Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• Efficient lifting of symmetry breaking constraints for complex combinatorial problems [9.156939957189502]
  This work extends the learning framework and implementation of a model-based approach for Answer Set Programming. In particular, we incorporate a new conflict analysis algorithm in the Inductive Logic Programming system ILASP.
  arXiv  Detail & Related papers  (2022-05-14T20:42:13Z)
• Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach [0.0]
  In this paper, we show how such a systematic exploration of algorithmic options can be done using parameterized complexity analysis. We show that none of our problems can be solved efficiently either in general or relative to a number of (often simultaneous) restrictions on environments, demonstrations, and policies.
  arXiv  Detail & Related papers  (2022-05-10T15:54:06Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Recall and Learn: A Memory-augmented Solver for Math Word Problems [15.550156292329229]
  We propose a novel human-like analogical learning method in a recall and learn manner. Our proposed framework is composed of modules of memory, representation, analogy, and reasoning.
  arXiv  Detail & Related papers  (2021-09-27T14:59:08Z)
• Constrained Learning with Non-Convex Losses [119.8736858597118]
  Though learning has become a core technology of modern information processing, there is now ample evidence that it can lead to biased, unsafe, and prejudiced solutions.
  arXiv  Detail & Related papers  (2021-03-08T23:10:33Z)
• Learning to solve the single machine scheduling problem with release times and sum of completion times [0.76146285961466]
  We focus on the solution of a hard single machine scheduling problem by new algorithms embedding techniques from machine learning field and scheduling theory. Theses transform an instance of the hard problem into an instance of a simpler one solved to optimality.
  arXiv  Detail & Related papers  (2021-01-04T16:40:18Z)
• Nature-Inspired Optimization Algorithms: Challenges and Open Problems [3.7692411550925673]
  Problems in science and engineering can be formulated as optimization problems, subject to complex nonlinear constraints. The solutions of highly nonlinear problems usually require sophisticated optimization algorithms, and traditional algorithms may struggle to deal with such problems. A current trend is to use nature-inspired algorithms due to their flexibility and effectiveness.
  arXiv  Detail & Related papers  (2020-03-08T13:00:04Z)
• The empirical duality gap of constrained statistical learning [115.23598260228587]
  We study the study of constrained statistical learning problems, the unconstrained version of which are at the core of virtually all modern information processing. We propose to tackle the constrained statistical problem overcoming its infinite dimensionality, unknown distributions, and constraints by leveraging finite dimensional parameterizations, sample averages, and duality theory. We demonstrate the effectiveness and usefulness of this constrained formulation in a fair learning application.
  arXiv  Detail & Related papers  (2020-02-12T19:12:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.