Cardinality of upper average and its application to network optimization^∗

We propose a new characteristic for counting the number of large outcomes in a data set that are considered to be large with respect to some fixed threshold x. A popular characteristic used for this purpose is the Cardinality of Upper Tail (CUT), which counts the number of outcomes with magnitude larger than the threshold. We propose a similar characteristic called the Cardinality of Upper Average (CUA), defined as the number of largest data points which have average value equal to the threshold. CUA not only assesses the number of outcomes that are large, but also their overall magnitude. CUA also has superior mathematical properties: it is a continuous function of the threshold, its reciprocal is piecewise linear with respect to threshold, and it is directly optimizable via convex and linear programming. This is in contrast to CUT, which does not asses the severity of large outcomes, is discontinuous as a function of threshold, and is such that direct optimization yields numerically difficult nonconvex problems. We show that CUA can be used to formulate meaningful optimization problems containing counters of the largest components of a vector without introduction of binary variables, leading to large improvement in computation speeds. In particular, we apply the CUA concept to create new formulations of network optimization problems involving overloaded nodes or edges, where we aim to minimize the number of most burdened nodes or edges.