acceptodds
Under review as a conference paper at ICLR 2027

Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling

Abstract

Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions. We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs. We show that these algorithms are competitive with representative incomplete DCOP algorithms. We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers. Combining our online learning methods with our iterative pricing framework, we obtain near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared with 87% for state-of-the-art baselines.

Primary area:
applications to robotics, autonomy, planning
Keywords:
distributed constraint optimization, satellite scheduling, online learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_D8urOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes an iterative pricing framework for large-scale DCOPs, combining high-level task allocation with local scheduling optimizers. The work is practically motivated and demonstrates promising empirical results. However, the paper is largely engineering-oriented, and its methodological novelty remains unclear. First, the main contributions are not clearly articulated. Second, decomposition is a well-established strategy in combinatorial optimization. Third, the fundamental differences between the proposed iterative pricing mechanism and existing state-of-the-art pricing and decomposition methods are insufficiently discussed. Addressing these concerns would substantially strengthen the paper.

Critical strengths
  1. The paper addresses a practically motivated problem in large-scale distributed optimization. The proposed framework has potential value for satellite scheduling with complex operational constraints.

  2. The proposed method achieves promising empirical results, substantially improving observation request fulfillment over the reported baselines.

Critical weaknesses
  1. Limited methodological novelty. Decomposition is a well-established strategy in combinatorial optimization [1–4]. The paper does not sufficiently clarify how its iterative pricing mechanism differs from existing decomposition-based coordination methods, particularly in terms of pricing updates and feedback between optimization levels.

  2. Poor readability and presentation. The paper is difficult to follow. Figure 1 provides little insight into the proposed framework, and the contributions in the introduction are not clearly organized. A clearer presentation of the overall methodology would improve readability.

  3. Insufficient experimental analysis. Although the paper includes several hyperparameter sensitivity studies, it lacks targeted ablations to isolate the contributions of the proposed pricing mechanism. Further experiments examining robustness to different problem scales, resource constraints, and communication overhead would strengthen the evaluation.

References

[1] Zheng et al. UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems. NeurIPS, 2024.

[2] Gao et al. Learning to Solve Orienteering Problem with Time Windows and Variable Profits. ICLR, 2026.

[3] Yuan et al. Divide, Harmonize, Then Conquer It: Shooting Multi-Commodity Flow Problems with Multimodal Language Models. ICLR, 2026.

[4] Smit et al. Neural Multi-Objective Combinatorial Optimization for Flexible Job Shop Scheduling Problems. ICLR, 2026.

Questions for authors
  1. Since distributed constraint optimization is already used for large-scale scheduling, the rationale for introducing online learning and iterative pricing remains unclear. Please specify the challenges addressed by each component and explain how the two approaches complement each other.
  2. The decomposition appears primarily to introduce a hierarchical organization of the problem, leaving its methodological novelty unclear. How does the iterative pricing feedback between the two levels differ from the coordination mechanisms in existing state-of-the-art hierarchical optimization methods?
  3. How faithfully does the model capture practical satellite operations? Since the evaluation relies on simulated instances, its effectiveness on real operational data and its practical applicability remain insufficiently established.
  4. The introduction emphasizes time-sensitive applications, including disaster response, transient scientific phenomena, and opportunistic observations, yet the experiments use predefined requests and candidate observation tasks without addressing changing communication topologies or unavailable information. Please clarify the information and communication limitations assumed by the distributed architecture, its operating conditions, and how the current experiments support its advantages for practical satellite coordination.
  5. Please define what scalability means in this work and explain which design choices enable it. Given the limited application coverage, how well does the proposed framework perform on other large-scale problems?
  6. Please specify the sampling rules used to select observation targets and the complete procedure for generating experimental instances. How do these choices ensure physically valid observation opportunities and representative operational workloads?
3 comments
AuthorsOpenReview ↗

Author response (1/3)

We thank the reviewer for recognizing the practical significance of our problem and the substantial empirical improvements achieved by our method. However, we disagree with several aspects of the review. We are concerned that the assessments of methodological novelty, presentation, and soundness do not adequately reflect the contributions and evidence already presented in our paper. We will address the criticisms point by point here in the rebuttal.

Poor readability and presentation. The paper is difficult to follow. Figure 1 provides little insight into the proposed framework, and the contributions in the introduction are not clearly organized. A clearer presentation of the overall methodology would improve readability.

We are surprised by the presentation assessment, particularly given that the other reviewers found the paper’s presentation quality strong, and did not have the same confusions about our work. Several of the reviewer’s concerns about missing explanations appear to refer to material already explicitly included in the manuscript.

The introduction motivates the work through the computational and communication limitations of existing DCOP methods on large-scale problems. It then explains why complex operational scheduling constraints make monolithic DCOP formulations impractical and why a decomposition-based approach is needed. A dedicated contributions discussion explicitly identifies both the online learning algorithms and iterative pricing framework, their motivations, and their relationship to prior work.

The paper also separates the two methodological components into Sections 3 and 5, with the underlying satellite scheduling formulation introduced in Section 4. The complete experimental evaluation and additional ablations are provided in Section 6 and Appendices E–F.

The reviewer seems confused about Figure 1. It merely depicts the satellite constellation. It does not illustrate the algorithm. The caption states that already, but if there is additional clarification that would be helpful, we are happy to incorporate any suggestions. We strongly disagree that the contributions, their motivation, and the methodology are insufficiently articulated.

Since distributed constraint optimization is already used for large-scale scheduling, the rationale for introducing online learning and iterative pricing remains unclear. Please specify the challenges addressed by each component and explain how the two approaches complement each other.

The motivation is explicitly developed in the introduction (Section 1). We will restate it here for the reviewer. Existing incomplete DCOP algorithms do not provide the desired solution quality and computational scalability for large, densely connected distributed constraint optimization problems. Our online learning algorithms address this challenge by providing new lightweight decentralized search methods based on recent advances in regret minimization.

Iterative pricing addresses a complementary challenge: representing the complex local scheduling constraints of real-world applications directly within a global DCOP is computationally prohibitive. Our decomposition instead allows individual agents to optimize these constraints locally while communicating scheduling outcomes through prices.

The two approaches are complementary but independent contributions. Online learning provides a family of distributed optimization algorithms, while iterative pricing supplies a framework for coupling high-level coordination with complex local optimization in distributed constraint optimization problems. Their combination yields by far the strongest results in the real-world satellite scheduling experiments.

AuthorsOpenReview ↗

Author response (2/3)

Limited methodological novelty. Decomposition is a well-established strategy in combinatorial optimization [1–4]. The paper does not sufficiently clarify how its iterative pricing mechanism differs from existing decomposition-based coordination methods, particularly in terms of pricing updates and feedback between optimization levels.

The decomposition appears primarily to introduce a hierarchical organization of the problem, leaving its methodological novelty unclear. How does the iterative pricing feedback between the two levels differ from the coordination mechanisms in existing state-of-the-art hierarchical optimization methods?

Iterative pricing is a new coordination mechanism in the DCOP setting, connecting high-level distributed task allocation with arbitrary local optimization oracles; it is not merely a hierarchical optimization method. Unlike a simple hierarchical decomposition, our framework iteratively communicates scheduling feasibility information through assignment-specific prices. This is a new decomposition idea for DCOPs and we already discuss related approaches, including MVA, distributed Lagrangian pricing (DisLRP), and logic-based Benders decomposition, in Section 1 and Appendix A. Could the reviewer please point out what other “coordination mechanisms in existing state-of-the-art hierarchical optimization methods” they are referring to?

We are also puzzled by the four references suggested as evidence of limited novelty. While those four papers are relevant to (some) combinatorial optimization broadly, none address distributed constraint optimization, and none are for our application. Can the reviewer please clarify how these references are related and why they provided them? We would welcome a discussion and will cite the papers if we come to understand their relevance, but we do not believe that citing unrelated application classes of decomposition is sufficient to establish a lack of novelty.

The introduction emphasizes time-sensitive applications, including disaster response, transient scientific phenomena, and opportunistic observations, yet the experiments use predefined requests and candidate observation tasks without addressing changing communication topologies or unavailable information. Please clarify the information and communication limitations assumed by the distributed architecture, its operating conditions, and how the current experiments support its advantages for practical satellite coordination. Please specify the sampling rules used to select observation targets and the complete procedure for generating experimental instances. How do these choices ensure physically valid observation opportunities and representative operational workloads? How faithfully does the model capture practical satellite operations? Since the evaluation relies on simulated instances, its effectiveness on real operational data and its practical applicability remain insufficiently established.

Our experiments are explicitly modeled after the operational scenarios that will be tested as part of NASA's FAME mission in 2027, as stated in the introduction. Our simulation framework is the same exact one that NASA uses for simulating that mission. The evaluation uses a constellation of 60 low-Earth-orbit satellites, with concrete models of orbital configurations, sensor capabilities, onboard memory, downlink opportunities, and observation windows. Efficient scheduling on static instances is a key capability to ultimately adapt to dynamic scenarios. The speed of our solver supports application to the dynamic setting because it is faster than the (typical) arrival time difference between consecutive requests.

The simulator propagates satellite trajectories using Keplerian orbital approximations and computes candidate observation opportunities from orbital geometry and visibility constraints. These are physically grounded observation opportunities. The local scheduling models additionally incorporate real operational constraints involving observation timing, slewing, memory, and downlink capacity.

Section 6 already describes the experimental setup in detail, including the constellation configuration, satellite capabilities, ground stations, observation horizon, and target generation.

Simulation is an essential, ubiquitous step in evaluating algorithms intended for autonomous spacecraft operations. It allows controlled, repeatable comparison of alternative coordination methods before deployment in a real mission.

Could the reviewer clarify the specific aspects of the simulation they consider insufficiently faithful to the intended operational setting?

AuthorsOpenReview ↗

Author response (3/3)

Please define what scalability means in this work and explain which design choices enable it. Given the limited application coverage, how well does the proposed framework perform on other large-scale problems?

We clearly define what scalability is throughout the paper. We will repeat this definition here for the reviewer: we wish to solve large distributed optimization problems in terms of the number of agents, variables, and constraints while managing limited resources.

Our methods address this challenge in two complementary ways. The online learning algorithms perform efficient decentralized search using local utility evaluations and neighbor communication. The decomposition framework reduces the complexity of global coordination by allowing rich local optimization problems to be solved independently and incorporating their outcomes through only pricing.

Scalability is evaluated in two complementary settings. The graph coloring experiments already vary problem sizes and network structures. The satellite experiments evaluate the complete decomposition framework on large-scale, real-world scheduling scenarios. While all our techniques are very general to DCOP, we already tackle the canonical DCOP benchmark of graph coloring and a real-world application of satellite scheduling. Other applications are beyond the scope of our work.

Reviewer_KbZyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies large-scale DCOPs that decompose into a high-level assignment/allocation problem and rich local scheduling problems. The authors propose iterative pricing, a decomposition framework where a high-level assignment DCOP is coupled to independent local solvers through assignment-specific prices. They also revisit the connection between DCOPs and potential games and evaluate regret-matching variants and FTRL as lightweight incomplete DCOP solvers. Numerical simulations are conducted on graph coloring and large-scale decentralized satellite scheduling.

Critical strengths

S1. Satellite constellation scheduling is a compelling large-scale DCOP application, and the two-level decomposition, global assignment plus local scheduling, is natural and practically relevant.

S2. The iterative pricing provides a generic interface between a DCOP allocator and arbitrary local solvers (MILP, CP, heuristic, simulator).

S3. The results of numerical simulations are good.

Critical weaknesses

W1. The proposed iterative pricing algorithm is essentially a heuristic price-update loop. The no-regret guarantees of the assignment DCOP solver do not imply convergence of the two-level procedure, feasibility of the returned schedule, or near-optimality. Considering that the experiments are numerical simulations, such a heuristic algorithm is a weak contribution.

W2. The robustness to incomplete local solvers is unclear. A heuristic scheduler may leave schedulable requests unselected and permanently raise prices. The authors should distinguish feasibility-preservation claims from solution-quality claims and report local-solver termination statuses, optimality gaps, and timing statistics beyond the stated millisecond-scale runtimes.

W3. The optimization problem in Section 5.2 seems to have no constraints coupling different requests. Each request can therefore be allocated independently to an eligible satellite with the highest positive assignment value, or left unassigned if all values are negative. This gives a straightforward exact solution. Consequently, employing a general-purpose iterative DCOP solver is unnecessary. The paper must compare against an exact per-request allocation baseline to prove that the reported performance gains stem from solving a genuinely difficult allocation problem, rather than from the incidental exploration benefits of online-learning algorithms.

W4. Although message counts and typical millisecond-scale local solves are reported, end-to-end runtime and scaling across constellation sizes are not. Given approximately 15.8 times NSS's message count, matched-runtime and matched-communication comparisons would better illustrate the practical tradeoff acknowledged by the authors.

Questions for authors

W1-W4.

2 comments
AuthorsOpenReview ↗

Author response (1/2)

We thank reviewer KbZy for their review. We hope to clarify any confusions regarding our approach and hope they find the responses to their questions sufficient to increase their assessment.

W1. The proposed iterative pricing algorithm is essentially a heuristic price-update loop. The no-regret guarantees of the assignment DCOP solver do not imply convergence of the two-level procedure, feasibility of the returned schedule, or near-optimality. Considering that the experiments are numerical simulations, such a heuristic algorithm is a weak contribution.

We disagree that the heuristic nature of iterative pricing constitutes a weakness of the contribution. The motivation for our work is precisely that large-scale DCOPs, such as COSP, are computationally intractable to solve optimally using general-purpose complete methods at the scales of interest. The satellite scheduling instances considered contain complex operational constraints involving orbital visibility, slewing, memory, and downlink opportunities. Representing and optimizing these constraints jointly in a monolithic DCOP leads to extremely large and dense constraint graphs. Practical approaches must trade exact optimality guarantees for computational scalability via heuristic methods.

Indeed, this is the motivation behind the extensive literature on incomplete DCOP algorithms, including DSA, MGM, GDBA, and Maxsum, which we compare against. Our contribution is to improve this algorithmic paradigm through modern online-learning methods and a new iterative pricing framework that incorporates complex local optimization without representing all operational constraints in the high-level DCOP.

The reviewer's statement concerning feasibility is also incorrect. Feasibility of the returned schedule does not depend on convergence or no-regret guarantees.

W2. The robustness to incomplete local solvers is unclear. A heuristic scheduler may leave schedulable requests unselected and permanently raise prices. The authors should distinguish feasibility-preservation claims from solution-quality claims and report local-solver termination statuses, optimality gaps, and timing statistics beyond the stated millisecond-scale runtimes.

An incomplete local solver may indeed return a feasible but suboptimal schedule, which can influence subsequent prices and potentially degrade solution quality. However, this does not compromise the feasibility of the returned schedule nor does it weaken our contribution. Suboptimal solvers within any framework will produce suboptimal solutions.

This distinction between feasibility and solution quality is important. Our framework guarantees the former, while evaluating the latter empirically. All local solvers terminate at optimality with the default OR-Tools optimality gap. The average solver time is 4.930 milliseconds.

W3. The optimization problem in Section 5.2 seems to have no constraints coupling different requests. Each request can therefore be allocated independently to an eligible satellite with the highest positive assignment value, or left unassigned if all values are negative. This gives a straightforward exact solution. Consequently, employing a general-purpose iterative DCOP solver is unnecessary. The paper must compare against an exact per-request allocation baseline to prove that the reported performance gains stem from solving a genuinely difficult allocation problem, rather than from the incidental exploration benefits of online-learning algorithms.

This is an intentional property of the decomposition, not a limitation. The purpose of the framework is to relax the computationally expensive scheduling constraints and recover coordination through iterative feedback from local optimizers.

The underlying COSP remains a difficult combinatorial optimization problem. Although requests may be independently allocated for fixed prices, the schedules are coupled through satellite resource constraints. These scheduling outcomes subsequently affect assignment-specific prices, which in turn influence future allocation decisions. Thus, the computational difficulty lies in coordinating allocation and scheduling, not in solving the relaxed allocation problem at any single iteration.

Furthermore, the allocation mechanism must be able to operate in a distributed setting. Each satellite maintains local assignment utilities, and determining the highest-utility satellite for each request requires coordination among the relevant agents.

More fundamentally, our contribution is the use of distributed online-learning methods and iterative pricing to search for high-quality solutions, while avoiding the computational expense of explicitly representing all local scheduling constraints in a global DCOP.

We will add a per-request allocation baseline to the final paper. Those new experiments show that this achieves 47.1% of requests fulfilled, which is significantly outperformed by all the other methods.

AuthorsOpenReview ↗

Author response (2/2)

W4. Although message counts and typical millisecond-scale local solves are reported, end-to-end runtime and scaling across constellation sizes are not. Given approximately 15.8 times NSS's message count, matched-runtime and matched-communication comparisons would better illustrate the practical tradeoff acknowledged by the authors.

Our experimental evaluation already includes two complementary domains. We conduct extensive experiments on graph-coloring DCOP benchmarks across random and scale-free network structures, varying the number of agents from 10 to 100. These experiments directly examine the behavior and scalability of our online learning methods across different problem sizes and constraint structures.

Our satellite scheduling experiments deliberately use a 60-satellite constellation modeled after the scale and operational characteristics of the upcoming NASA FAME mission, which is intended to demonstrate multiagent autonomous satellite operations in space. This is not an arbitrarily selected simulation size. It reflects a concrete operational scenario and provides a practically relevant evaluation of our framework on large-scale scheduling instances with realistic orbital and resource constraints.

If we constructed artificial smaller and larger instances using the real satellite data, and ran scalability experiments as a function of the number of satellites and the number of requests, would the reviewer then recommend acceptance of the paper? If so, we can try hard to get that done by the end of the rebuttal period.

Reviewer_tXqvOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper addresses large-scale distributed constraint optimization through two complementary approaches: adapting regret-matching and related online-learning algorithms into decentralized search methods, and introducing an iterative-pricing framework that couples high-level task allocation with independent local scheduling solvers. Prices increase for assignments that local solvers cannot fulfill, guiding subsequent allocations while prioritizing difficult requests locally. Experiments show competitive performance on graph-coloring benchmarks and strong results on simulated 60-satellite scheduling problems: iterative pricing with context-based IR-PRM fulfills 99.2% of observation requests, compared with roughly 87% for the baselines, although it requires substantially more communication. The framework is a coordination heuristic without a global optimality guarantee.

Critical strengths
  1. The framework separates global task allocation from complex local scheduling. When an assigned request cannot be scheduled, its price increases, discouraging that assignment globally while raising its priority locally. This mechanism incorporates local scheduling difficulties into coordination without expanding the DCOP to represent every physical constraint.
  2. The learning updates use counterfactual local utilities and neighbor communication, avoiding the pseudo-tree dependency of earlier context-based regret methods. The empirical justification is strong within the tested satellite setting: context-based IR-PRM with pricing achieves 99.2% request fulfillment, versus roughly 87% for the baselines. The context ablations further support the importance of the interaction between the learning dynamics and pricing feedback.
Critical weaknesses
  1. The allocation formulation does not justify the complexity of the proposed learning machinery. Once scheduling constraints move into local solvers, the stated allocation problem separates across requests: each request independently selects its most attractive satellite or remains unassigned. The paper does not identify additional coupling that makes this step a difficult DCOP. A direct per-request allocation baseline is therefore needed to establish what regret learning contributes beyond the pricing mechanism.
  2. Monotonically increasing prices can permanently discard useful assignments. Consider two satellites, each able to schedule one request: one request requires the first satellite, while another can use either. If both initially reach the first satellite and its scheduler keeps the flexible request, a sufficiently large price increase can exclude the inflexible request permanently, even though completing both is feasible. Increasing its local priority cannot help once the allocator stops assigning it. The stopping condition accepts this incomplete outcome, and the algorithm supplies neither a recovery mechanism nor an approximation guarantee.
Questions for authors
  1. How does pricing recover from unfavorable early allocations? Can increasing penalties permanently suppress assignments needed for a better joint schedule? Exploring price decreases, capped penalties, or explicit reassignment recovery could help establish robustness beyond the tested instances.
  2. What coupling remains in the high-level allocation problem? As formulated, requests appear independently assignable once local scheduling constraints are removed. Could you compare against direct per-request allocation to isolate the benefit of regret learning?
1 comment

We thank reviewer tXqv for their review. We hope to clarify any confusions. If the reviewer finds our response sufficient, we encourage them to increase their score to reflect the positive assessment of our work. Also, we were a bit surprised by the overall score of 2 given that the reviewer’s component scores were all 3’s.

How does pricing recover from unfavorable early allocations? Can increasing penalties permanently suppress assignments needed for a better joint schedule? Exploring price decreases, capped penalties, or explicit reassignment recovery could help establish robustness beyond the tested instances.

Iterative pricing is a heuristic procedure and does not provide a worst-case approximation guarantee, as explicitly discussed in Section 5.2. The reviewer identifies a possible failure mode when prices increase rapidly. However, this behavior depends on the pricing step size, which is a tunable parameter of our framework.

A large step size can penalize an initially unsuccessful assignment and discourage its future selection. Smaller step sizes allow penalties to accumulate more gradually, reducing the impact of individual scheduling failures on subsequent allocation decisions. This tradeoff is precisely why we include the extensive step-size sensitivity analysis in Appendix F.3 (Figure A11), which examines solution quality across different values of alpha. The results demonstrate that the choice of step size affects performance and that its appropriate value depends on the underlying allocation algorithm.

We also emphasize that our approach is an incomplete DCOP search method. Like other incomplete DCOP algorithms, it prioritizes computational efficiency and empirical solution quality rather than guaranteeing recovery from every suboptimal decision. Introducing exhaustive backtracking or explicitly incorporating all scheduling constraints would undermine the scalability advantages motivating our decomposition.

Most importantly, the worst-case counterexample does not manifest in the empirical performance. Our framework fulfills 99.2% of observation requests across the evaluated satellite scheduling instances, compared with approximately 87% for the existing baselines. Since fulfilling every request provides an upper bound on the optimum, the reported fulfillment rate also provides a direct certificate of near-optimal performance on these instances.

What coupling remains in the high-level allocation problem? As formulated, requests appear independently assignable once local scheduling constraints are removed. Could you compare against direct per-request allocation to isolate the benefit of regret learning?

This question highlights the main motivation of our decomposition method. The relaxation of removing lots of coupling constraints is intentional and is precisely the central motivation for our decomposition framework to relieve complexity. The original COSP formulation contains complex inter-satellite coordination constraints, making direct distributed constraint optimization computationally intractable at the scales considered. Our framework avoids explicitly representing these constraints in the high-level DCOP, instead coupling allocation decisions with independent local scheduling problems through iterative pricing.

The coupling between allocation and scheduling has not disappeared: it is handled through the iterative price updates. These prices incorporate feedback from the local schedulers, allowing the high-level allocation procedure to adapt to scheduling constraints without explicitly encoding them. While the allocation objective is separable across requests for fixed prices, the resulting schedules and subsequent price updates are not independent across requests. The difficulty is in coordinating these interacting levels, rather than in solving the relaxed objective at a single iteration.

We will add a per-request allocation baseline to the final paper. Those new experiments show that this achieves 47.1% of requests fulfilled, which is significantly outperformed by all the other methods.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.