Question:Are there any complexity measures

in use, that allow one to compare mathematical programming formulations of optimization problems on basis of the number of variables thatmustbe subjected to specific integrality or linearity constraints?

To be more specific, I would be interested in how the number of integer variables grows with the size of a problem and also how the number the other types of variables e.g. continuous or bilinear, grows.

From a theoretical point of view, a formulation with fewer integer or bilinear variables would be better, whereas from a practical point of view, the tradeoff may be more interesting.

The restrictive *must be* for integer or bilinear variables was used to emphasise that the computationally least "expensive" sufficient type of variables has to be assumed in counting the types; totally unimodular problems yield integer solutions without having to constrain any variables to be integral, the same is true for the primal-dual algorithm for matching problems, so for those problems the count for integer variables would have to be zero.

I am hesitant to using the "algorithms" tag, because what I am looking for, is not related to executing a sequence of operations or decisions; "complexity" also doesn't quite seem fit, neither in the temporal nor in the spatial sense.