Decision-Focused Clustering

Modern platforms often need to make personalized decisions for a large number of instances, repeatedly solving the same optimization problem with different instance-specific parameters. When the number of distinct decisions is limited, a natural approach is to group instances into clusters and assign a shared decision to all instances within each cluster. Standard clustering methods such as $k$-means, however, group instances according to geometric similarity, which need not preserve downstream decision quality. We propose Decision-Focused Clustering (DFC) for linear downstream optimization problems, which forms clusters based directly on the quality of the decisions shared within each cluster. To formalize this objective, we introduce a decision loss that measures the regret of using the decision optimized for one cost vector when the true cost vector is another. Since the resulting clustering problem is NP-hard, we develop an alternating optimization algorithm that iteratively updates cluster representatives and instance assignments. We further establish theoretical convergence guarantees for the proposed algorithm. We evaluate our framework on synthetic shortest-path and portfolio optimization problems and a real-world courier dispatching problem, covering decision problems with different feasible-set structures, including polyhedral and strongly convex settings. Compared with \(k\)-means, DFC consistently achieves lower decision loss in all three application settings.