Search papers, labs, and topics across Lattice.
This paper introduces a decision-aware approximation method for reducing the number of focal elements in mass functions used in evidential combinatorial optimization, focusing on preserving decision quality rather than mere closeness to the original mass function. The authors demonstrate that their approach significantly reduces decision flips compared to traditional representation-aware compression, particularly in scenarios involving minimal shortest paths. Experimental results reveal that the decision-aware compressor maintains decision integrity more effectively, indicating a substantial improvement in decision-making under uncertainty.
Decision-aware approximations can drastically reduce decision flips in combinatorial optimization, outperforming traditional methods by preserving decision quality over mere representation fidelity.
Reducing the number of focal elements of a mass function is classically driven by an intrinsic distance, such as Jaccard or Jousselme, that keeps the approximation close to the original as a body of evidence. We consider instead the case where the mass function feeds a linear combinatorial optimisation problem with evidential costs. What should then be preserved is not the closeness of the two mass functions, but the quality of the decision they induce. We introduce a decision-aware approximation that targets the regret of the decision: one decides with the cheaper approximation and is evaluated under the true mass function. On a minimal shortest path, the distance-optimal approximation flips the decision while a decision-aware merge preserves it, and this occurs on a non-negligible fraction of random instances. We prove a one-point bound that localises the regret at the true optimum, turn it into an exact dynamic program for the scalar case, and extend it to an online version that prunes focal elements before the final cost is known. In experiments the decision-aware compressor flips the decision less often than representation-aware compression, for both the linear criterion and a non-linear proxy read-out.
