Hypergraph Optimization Problems: Why is the Objective Function Linear?

Abstract

Choosing an objective function for an optimization problem is a
modeling issue and there is no a-priori reason that the objective function
must be linear. Still, it seems that linear 0-1 programming formulations
are overwhelmingly used as models for optimization problems
over discrete structures. We show that this is not an accident. Under
some reasonable conditions (from the modeling point of view), the
linear objective function is the only possible one.