Clustered maximum weight clique problem: Algorithms and empirical analysis

We introduce the Clustered Maximum Weight Clique Problem (CCP), a generalization of the Maximum Weight Clique Problem, that models an image acquisition scheduling problem for a satellite constellation. The solution of CCP represents satellite schedules that satisfy customer requests for satellite imagery. Each request has a priority, an area of interest, and a time window. Often, the area of interest is too large to be imaged by one satellite pass and it has to be divided into several smaller images. Each image has one or more opportunities for an acquisition by a satellite.The problem is modeled by a clustered weighted graph. A graph node represents one opportunity for an image acquisition by one satellite. A graph edge indicates that either two opportunities are not in conflict – can both be in a schedule, or two opportunities are not acquiring the same image. Each graph node has a weight that represents the area size of the image. The graph nodes are partitioned into clusters each of which encompasses all the opportunities of one customer request. The priority of the request is captured by the cluster weight. The time window of the request restricts the number of opportunities.The CCP deals with finding a clique of a maximum weight where the weight combines the node weights and the cluster weights. More precisely, the cluster weight is multiplied by the contribution of the sum of the weights of the clique nodes. The contribution is either a linear function or a piece-wise linear function, where the latter is meant to favour finalizing an already partially served customer request.The paper presents several mathematical programming formulations of the CCP and proposes matheuristic solution approaches. The computational study is performed on the clustered adaptations of the DIMACS and BHOSLIB benchmark instances for the Maximum Weight Clique Problem. The achieved results are encouraging.