Optimizing Earth Observation Satellite Schedules under Unknown Operational Constraints: An Active Constraint Acquisition Approach

• URL: http://arxiv.org/abs/2604.13283v1
• Date: Tue, 14 Apr 2026 20:19:28 GMT
• Title: Optimizing Earth Observation Satellite Schedules under Unknown Operational Constraints: An Active Constraint Acquisition Approach
• Abstract summary: Conservative Constraint Acquisition(CCA) is a domain-specific procedure designed to identify justified constraints efficiently.<n>L&O supports an interactive search process that alternates optimization under a learned constraint model with targeted oracle queries.<n>At $n=50$, where the CP-SAT reference is the best solution found in 120s, L&O improves on on average (17.9% vs. 20.3%) while using 21.3 main queries instead of 100.
• Score: 1.3097161185372153
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Earth Observation (EO) satellite scheduling (deciding which imaging tasks to perform and when) is a well-studied combinatorial optimization problem. Existing methods typically assume that the operational constraint model is fully specified in advance. In practice, however, constraints governing separation between observations, power budgets, and thermal limits are often embedded in engineering artefacts or high-fidelity simulators rather than in explicit mathematical models. We study EO scheduling under \emph{unknown constraints}: the objective is known, but feasibility must be learned interactively from a binary oracle. Working with a simplified model restricted to pairwise separation and global capacity constraints, we introduce Conservative Constraint Acquisition~(CCA), a domain-specific procedure designed to identify justified constraints efficiently in practice while limiting unnecessary tightening of the learned model. Embedded in the \textsc{Learn\&Optimize} framework, CCA supports an interactive search process that alternates optimization under a learned constraint model with targeted oracle queries. On synthetic instances with up to 50~tasks and dense constraint networks, L\&O improves over a no-knowledge greedy baseline and uses far fewer main oracle queries than a two-phase acquire-then-solve baseline (FAO). For $n\leq 30$, the average gap drops from 65--68\% (Priority Greedy) to 17.7--35.8\% using L\&O. At $n{=}50$, where the CP-SAT reference is the best feasible solution found in 120~s, L\&O improves on FAO on average (17.9\% vs.\ 20.3\%) while using 21.3 main queries instead of 100 and about $5\times$ less execution time.

Related papers

• Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity [68.54852541944625]
  Black-box optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations.<n>We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters.
  arXiv  Detail & Related papers  (2026-05-29T14:24:54Z)
• Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation [21.36054923028733]
  Reinforcement learning (RL) in large environments often suffers from severe computational bottlenecks.<n>We propose a novel algorithm that achieves the optimal $tildeO(sqrtT)$ regret bound while requiring only $O(Hloglog T)$ calls.<n>This oracle complexity is entirely independent of the size of the state and action spaces.
  arXiv  Detail & Related papers  (2026-05-01T04:32:23Z)
• Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization [18.737087162461563]
  Test-time compute scaling has become a powerful lever for improving large language model performance.<n>Yet deploying these techniques under finite inference budgets requires a decision that current systems largely ignore.<n>We formalize this as a constrained optimization problem (maximize expected accuracy subject to an average compute budget) and solve it with a two-stage Solve-then-Learn pipeline.
  arXiv  Detail & Related papers  (2026-04-16T10:39:22Z)
• Compact Constraint Encoding for LLM Code Generation: An Empirical Study of Token Economics and Constraint Compliance [0.0]
  We investigate whether compact, structured constraint headers can reduce prompt token consumption without degrading constraint compliance.<n>We find that compact headers reduce constraint-portion tokens by approximately 71% and full-prompt tokens by 25-30%, replicated across three independent rounds.
  arXiv  Detail & Related papers  (2026-04-08T15:18:33Z)
• CCTU: A Benchmark for Tool Use under Complex Constraints [66.87622847854337]
  We introduce CCTU, a benchmark for evaluating large language models (LLMs) under complex constraints.<n>The benchmark comprises 200 carefully curated and challenging test cases across diverse tool-use scenarios.<n>We develop an executable constraint validation module that performs step-level validation and enforces compliance.
  arXiv  Detail & Related papers  (2026-03-16T14:05:13Z)
• ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization [0.0]
  We introduce ConstraintBench, a benchmark for evaluating large language models on direct constrained optimization.<n>We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck.<n>No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference.
  arXiv  Detail & Related papers  (2026-02-25T22:54:26Z)
• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• Efficient LLM Collaboration via Planning [56.081879390960204]
  Small and large models take turns acting as planner and executor, exchanging plans in a multi-stage cascade to collaboratively solve tasks.<n>We demonstrate that COPE achieves performance comparable to large proprietary models, while drastically reducing the inference API cost.
  arXiv  Detail & Related papers  (2025-06-13T08:35:50Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents.<n>Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• Learning to Learn in Interactive Constraint Acquisition [7.741303298648302]
  In Constraint Acquisition (CA), the goal is to assist the user by automatically learning the model. In (inter)active CA, this is done by interactively posting queries to the user. We propose to use probabilistic classification models to guide interactive CA to generate more promising queries.
  arXiv  Detail & Related papers  (2023-12-17T19:12:33Z)
• $\texttt{FedBC}$: Calibrating Global and Local Models via Federated Learning Beyond Consensus [66.62731854746856]
  In federated learning (FL), the objective of collaboratively learning a global model through aggregation of model updates across devices tends to oppose the goal of personalization via local information. In this work, we calibrate this tradeoff in a quantitative manner through a multi-criterion-based optimization. We demonstrate that $texttFedBC$ balances the global and local model test accuracy metrics across a suite datasets.
  arXiv  Detail & Related papers  (2022-06-22T02:42:04Z)
• An Information Theory-inspired Strategy for Automatic Network Pruning [97.03772272417599]
  Deep convolution neural networks are well known to be compressed on devices with resource constraints.<n>Most existing network pruning methods require laborious human efforts and prohibitive computation resources.<n>We propose an information theory-inspired strategy for automatic model compression.
  arXiv  Detail & Related papers  (2021-08-19T07:03:22Z)

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.