The quadratic unconstrained binary optimization (QUBO) is a well-known NP-hard problem that takes an $n\times n$ matrix $Q$ as input and decides an $n$-dimensional 0-1 vector $x$, to optimize a quadratic function. Existing learning-based models that always formulate the solution process as sequential decisions suffer from high computational overload. To overcome this issue, we propose a neural solver called the Value Classification Model (VCM) that formulates the solution process from a classification perspective. It applies a Depth Value Network (DVN) based on graph convolution that exploits the symmetry property in $Q$ to auto-grasp value features. These features are then fed into a Value Classification Network (VCN) which directly generates classification solutions. Trained by a highly efficient model-tailored Greedy-guided Self Trainer (GST) which does not require any priori optimal labels, VCM significantly outperforms competitors in both computational efficiency and solution quality with a remarkable generalization ability. It can achieve near-optimal solutions in milliseconds with an average optimality gap of just 0.362\% on benchmarks with up to 2500 variables. Notably, a VCM trained at a specific DVN depth can steadily find better solutions by simply extending the testing depth, which narrows the gap to 0.034\% on benchmarks. To our knowledge, this is the first learning-based model to reach such a performance.

The scheduling of agile Earth observation satellites is to select a subset of candidate targets each associated with a profit during their visible time windows in order to maximize the collected profits, under some operational constraints. For each pair of two consecutive observations, a transition time is required to perform a rotating movement of the camera, depending on the start times of the two observations. This time-dependency significantly increases the complexity of the scheduling problem. To solve this problem efficiently, we model the time-dependent transition time and prove that it satisfies the first-in–first-out rule and the triangle inequalities rule. On this basis, we develop a novel hybrid heuristic, called “greedy randomized iterated local search” (GRILS). A specific insert operator, including a fast feasibility check and an assignment procedure are specifically designed to address the operational constraints of the scheduling. Extensive experiments on the single satellite instances and multisatellite instances demonstrate that our algorithm outperforms the state-of-the-art algorithms with respect to solution quality and computation time.