Implementing Cumulative Functions with Generalized Cumulative Constraints

• URL: http://arxiv.org/abs/2508.01751v1
• Date: Sun, 03 Aug 2025 13:29:44 GMT
• Title: Implementing Cumulative Functions with Generalized Cumulative Constraints
• Authors: Pierre Schaus, Charles Thomas, Roger Kameugne,
• Abstract summary: We present an implementation of a modeling approach using a single, generic global constraint called the Generalized Cumulative.<n>We also introduce a novel time-table filtering algorithm designed to handle tasks defined on conditional time-intervals.
• Score: 5.85656359624005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modeling scheduling problems with conditional time intervals and cumulative functions has become a common approach when using modern commercial constraint programming solvers. This paradigm enables the modeling of a wide range of scheduling problems, including those involving producers and consumers. However, it is unavailable in existing open-source solvers and practical implementation details remain undocumented. In this work, we present an implementation of this modeling approach using a single, generic global constraint called the Generalized Cumulative. We also introduce a novel time-table filtering algorithm designed to handle tasks defined on conditional time-intervals. Experimental results demonstrate that this approach, combined with the new filtering algorithm, performs competitively with existing solvers enabling the modeling of producer and consumer scheduling problems and effectively scales to large problems.

Related papers

• Solving Parallel Machine Scheduling With Precedences and Cumulative Resource Constraints With Calendars [2.863183011550039]
  We introduce a novel variant of parallel machine scheduling with job precedences and calendar-based cumulative resource constraints.<n>We propose a construction as well as a tailored metaheuristic using local search to efficiently tackle large-scale problem instances.
  arXiv  Detail & Related papers  (2025-12-05T12:35:44Z)
• Quantum-classical hybrid algorithm using quantum annealing for multi-objective job shop scheduling [0.5872014229110214]
  Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition.<n>We develop a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling.<n> Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods.
  arXiv  Detail & Related papers  (2025-11-05T07:39:09Z)
• FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming [52.52020895303244]
  Mixed-Integer Linear Programming (MILP) is a foundational tool for complex decision-making problems.<n>We propose Joint Continuous-Integer Flow for Mixed-Integer Linear Programming (FMIP), which is the first generative framework that models joint distribution of both integer and continuous variables for MILP solutions.<n>FMIP is fully compatible with arbitrary backbone networks and various downstream solvers, making it well-suited for a broad range of real-world MILP applications.
  arXiv  Detail & Related papers  (2025-07-31T10:03:30Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  We present Recipe2Plan, a novel benchmark framework based on real-world cooking scenarios.<n>Unlike conventional benchmarks, Recipe2Plan challenges agents to optimize cooking time through parallel task execution.
  arXiv  Detail & Related papers  (2025-03-04T03:27:02Z)
• A Benchmarking Environment for Worker Flexibility in Flexible Job Shop Scheduling Problems [0.0]
  In Production Scheduling, the Flexible Job Shop Scheduling Problem (FJSSP) aims to optimize a sequence of operations and assign each to an eligible machine with varying processing times.<n>The resulting problem is called Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W)<n>This paper presents a collection of 402 commonly accepted FJSSP instances and proposes an approach to extend these with worker flexibility.
  arXiv  Detail & Related papers  (2025-01-27T15:56:12Z)
• Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model [6.123324869194196]
  We study the assortment optimization problem under the mixed-logit customer choice model. Existing exact methods have primarily relied on mixed-integer linear programming (MILP) or second-order cone (CONIC) reformulations. Our work addresses the problem by focusing on components of the objective function that can be proven to be monotonically super-modular and convex.
  arXiv  Detail & Related papers  (2024-07-26T06:27:11Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Differentiable Combinatorial Scheduling at Scale [18.09256072039255]
  We propose a differentiable scheduling framework, utilizing Gumbel-Softmax differentiable sampling technique. To encode inequality constraints for scheduling tasks, we introduce textitconstrained Gumbel Trick, which adeptly encodes arbitrary inequality constraints. Our method facilitates an efficient and scalable scheduling via gradient descent without the need for training data.
  arXiv  Detail & Related papers  (2024-06-06T02:09:39Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
  arXiv  Detail & Related papers  (2022-02-28T12:26:47Z)
• Efficient Temporal Piecewise-Linear Numeric Planning with Lazy Consistency Checking [4.834203844100679]
  We propose a set of techniques that allow the planner to compute LP consistency checks lazily where possible. We also propose an algorithm to perform duration-dependent goal checking more selectively. The resultant planner is not only more efficient, but outperforms most state-of-the-art temporal-numeric and hybrid planners.
  arXiv  Detail & Related papers  (2021-05-21T07:36:54Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Metaheuristics for the Online Printing Shop Scheduling Problem [0.0]
  This real scheduling problem, that emerged in the nowadays printing industry, corresponds to a flexible job shop scheduling problem with sequencing flexibility. A local search strategy and metaheuristic approaches for the problem are proposed and evaluated. Numerical experiments with classical instances of the flexible job shop scheduling problem show that the introduced methods are also competitive when applied to this particular case.
  arXiv  Detail & Related papers  (2020-06-22T15:38:00Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30: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.