Hypergraph Optimization Problems: Why is the Objective Function Linear?

Aleksandar Pekec

December 1996


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

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.