- 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
-
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.
-
The proposed method achieves promising empirical results, substantially improving observation request fulfillment over the reported baselines.
Critical weaknesses
-
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.
-
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.
-
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
- 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 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?
- 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.
- 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 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?
- 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
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?
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.
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.
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.
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.