BRICS RS-96-50 A. Peke� c: Hypergraph Optimization Problems

BRICS

Basic Research in Computer Science

Hypergraph Optimization Problems: Why is the Objective Function Linear?

Aleksandar Peke� c

BRICS Report Series RS-96-50 ISSN 0909-0878 December 1996 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1996, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through World Wide Web and anonymous FTP:

http://www.brics.dk/
ftp://ftp.brics.dk/pub/BRICS

This document in subdirectory RS/96/50/

Hypergraph Optimization Problems: Why is the Objective Function Linear?

Aleksandar Pekeč

BRICS^{∗}

Department of Computer Science University of Aarhus Ny Munkegade DK-8000 Aarhus C, Denmark

                  http://www.brics.dk/∼pekec/

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.

∗ Basic Research in Computer Science, Centre of the Danish National Research Foundation.

1 Introduction

Many standard combinatorial optimization problems can be formulated as linear 0-1 programming problems, i.e.,

max{w^{T} x : x ∈ H ⊂ {0, 1}^{n}}.  (1)

More generally, any function P : {0, 1}^{n} × R^{n} → R defines an optimization problem

max{P (x; w) : x ∈ H ⊂ {0, 1}^{n}}.  (2)

Another way of formulating this problem is to utilize the obvious one-to-one correspondence between vectors x ∈ {0, 1}^{n} and subsets S ⊆ {1, …, n}: x is the incidence vector of the set S ⊆ {1, …, n} if and only if

x_{i} = 1 ⇔ i ∈ S.

Hence, the set of feasible solutions H can be viewed as a hypergraph on [n] := {1, …, n}, that is, a collection of subsets of [n]. Throughout we will assume that [n] ∉ H. (This assumption is not so restrictive since we can always compare the optimal solution of the problem (2) and P ((1, …, 1)^{T}; w).) In this setup, problem (2) is the problem

max{f_{S}(w) : S ∈ H}  (3)

where H is a hypergraph on [n], w = (w_{1}, …, w_{n})^{T} ∈ R^{n} is a vector of problem parameters (weights associated to elements of [n]), and, for every S ∈ H, f_{S} is a real valued function (f_{S} : R^{n} → R) defined by f_{S}(w) = P (x_{S}; w) where x_{S} stands for the incidence vector of the set S. For example, the family of 2^{n} − 1 functions {f_{S}^{(L)} : R^{n} → R : S ⊂ [n]} defined by f_{S}^{(L)}(w) = ∑_{i∈S} w_{i} defines the objective function P (x; w) = w^{T} x, i.e., the linear 0-1 programming problem. Note that any collection of 2^{n} − 1 functions {f_{S} : R^{n} → R : S ⊂ [n]} defines an objective function P and, hence, the problem (2). For a given objective function P, let F(P) := {f_{S} : R^{n} → R : S ⊂ [n]} (f_{S} are defined as above).

It might not be surprising that, among all possible formulations of problem (2), the linear 0-1 programming problems are the most studied ones. Even this simple case (simple compared to general formulation (2)) is not well understood: there are various choices for H to make problem (1) NPcomplete. (For example, choosing H to be the set of all Hamiltonian cycles of the complete graph on k vertices, n = k(k − 1)/2, gives the traveling salesman problem with edge weights given by w = (w_{1}, …, w_{n})^{T}.)

What seems a bit more surprising is that linear 0-1 programming formulation (1) is used (almost exclusively) as a mathematical model for optimization problems over discrete structures. Choosing an objective function for a problem is a modeling issue and there is no a-priori reason that the objective function must be linear. Is this really accidental or there are some reasons behind widespread use of linear 0-1 programming formulation?

The least one should expect from a satisfactory model is that conclusions that can be drawn from the model are invariant with respect to the choice of an acceptable way to represent problem parameters. For example, in the traveling salesman problem, if w_{1}, …, w_{n} represent edge lengths (or cost of using an edge), then w_{1}, …, w_{n} can be expressed in meters or feet or kilometers or miles or … (US dollars, Danish kroner, Croatian kunas, …) In fact, whenever w_{1}, …, w_{n} are numerical representations of problem data, it is likely that, for any λ > 0, λw_{1}, …, λw_{n} are also acceptable numerical representations of data. This amounts to changing the unit of measurement (e.g., λ = 2.54 describes the change from inches to centimeters, λ = 5.75 describes the change from US dollars to Danish kroner, etc). Hence, it is reasonable to assume that problem (2) satisfies the following property:

∀w ∈ R^{n}, ∀λ > 0 :
P (x^{∗}; w) = max{P (x; w) : x ∈ H}
⇔  (4)
P (x^{∗}; λw) = max{P (x; λw) : x ∈ H}

In other words, the conclusion of optimality (“x^{∗} is an optimal solution”) should be invariant under positive linear scaling of problem parameters w (that is, replacing w by λw, λ > 0).

Remark. Measurement theory provides a mathematical foundation for analysis of how data is measured and how the way data is measured might affect conclusions that can be drawn from a mathematical model. Scales of measurement where everything is determined up to the choice of the unit of measurement (e.g., measurement of mass, time, length, monetary amounts,…) are called ratio scales. In measurement theory terminology, requirement (4) is the requirement that the conclusion of optimality for problem (2) is meaningful if w_{1}, …, w_{n} are measured on a ratio scale. Informally, a statement involving scales of measurement is meaningful if its truth value does not depend on the choice of an acceptable way to measure data related to the statement. (More about measurement theory can be found in [3]. More about applying concept of meaningfulness to combinatorial optimization problems can be found in [2, 4, 5].)

A central question that motivates the work in the paper is whether there exists an objective function P with the following property:

Invariance under Linear Scaling (ILS). For any choice of a nonempty set of feasible solutions H ⊂ {0, 1}^{n}, requirement (4) is satisfied.

Clearly, the answer is: Yes. For example, the linear objective function P (x, w) = w^{T} x has property (ILS).

Are there any other objective functions having property (ILS)? We will argue that, provided that the objective function has some other reasonable properties, the linear objective function is essentially the only objective function having property (ILS). Of course, the key word here is “reasonable”. In order to describe these “reasonable” properties we again turn to the representation of an objective function P by the corresponding family F(P) = {f_{S} : R^{n} → R : S ⊂ [n]}:

Locality (L). It is reasonable to assume that the value f_{S}(w) depends only on the weights corresponding to the elements from S. In other words, changing the weight w_{j} corresponding to any element j ∉ S, will not change the value of f_{S}. More precisely, if

∀S ⊂ [n], ∀j ∉ S : \frac{∂f_{S}}{∂w_{j}} = 0

we will say that the family F(P) (or P) is local (has property L).

Normality (N). The weights w should (in a transparent way) indicate the value of f_{S} for all singletons S. We will say that the family F(P) (or P) is normalized (has property (N)) if, for any singleton {i} and any w ∈ R^{n} f_{{i}}(w) = w_{i} (i.e.,f_{{i}} restricted to the i-th coordinate is the identity function).

The property (N) should not be considered restrictive: if F(P) were not normalized, it would make sense to reformulate the problem by introducing new weights w̄ defined by w̄_{i} := f_{{i}}(w_{i}). Of course, all other f_{S} would need to be redefined: f̄_{S}(w̄) := f_{S}(w).

Completeness (C). For any nonempty S, unbounded change in w should result in unbounded change in f_{S}(w). In fact, we will require that f_{S}(R^{n}) = R. In other words, if for every nonempty S ⊂ [n], f_{S} ∈ F(P) is surjective, we say that F (P) (or P) is complete (has property (C)).

Separability (S). The rate of change of f_{S}(w) with respect to changing w_{i} should depend only on w_{i} (and not on the values of w_{j}, j ≠ i). Furthermore, this dependence should be “smooth”. More precisely, f is separable (has property (S)) if for any i ∈ [n], there exists a function g_{i} : R → R, g_{i} ∈ C^{1}(R), such that

\frac{∂f}{∂w_{i}} (w) = g_{i}(w_{i}).

We say that F(P) (or P) is separable (has property (S)) if every function f_{S} ∈ F(P) is separable.

The separability is arguably the most restrictive of the properties from the point of view of modeling (in the sense that one might argue that there are many problems for which any optimization model with the objective function that has property (S) would not be satisfactory). We will discuss possible variations of all these properties in Section 3.

The main result of this paper is a characterization theorem:

Theorem 1 Let P be the objective function for the problem (2). Suppose that F(P) satisfies (L), (N), (C), and (S). Then P has property (ILS) if and only if every f_{S} ∈ F(P) is linear, that is, if and only if for every S ⊂ [n] there exist constants C_{S,i}, i ∈ S, such that

f_{S}(w) = ∑_{i∈S} C_{S,i}w_{i}.  (5)

2 Proof of the Theorem

We first give a “workable” reformulation of property (ILS).

Proposition 2 P satisfies (ILS) if and only if

∀S, T ⊂ [n], ∀w ∈ R^{n}, ∀λ ∈ R_{+} :
f_{S}(w) ≥ f_{T} (w) ⇔ f_{S}(λw) ≥ f_{T} (λw)  (6)

Proof: Note that (4) can be rewritten as

∀w ∈ R^{n}, ∀λ > 0 :
f_{S^{∗}}(w) = max{f_{S}(w) : S ∈ H}
⇔  (7)
f_{S^{∗}}(λw) = max{f_{S}(λw) : S ∈ H}

Obviously, (6) ⇒ (ILS). Conversely, for any S, T ⊂ [n], we define H = {S, T } which gives (ILS) ⇒ (6).

Homogeneous functions play a central role in the proof of Theorem 1. We say that f : R^{n} → R is a r-homogeneous if for every λ > 0 and every w, f(λw) = λ^{r}f(w).

The plan of the proof is as follows: we will first show that properties (L), (N), (C), and (ILS) imply that every f_{S} in F(P) is 1-homogeneous. Then we will use a well known result about homogeneous functions (Euler’s homogeneity relation) to show that (L) and (S) imply that every f_{S} must be a linear function.

Lemma 3 Let P satisfy (L) and (ILS). Suppose that f_{S_{0}} ∈ F(P) is an r-homogeneous function. Then, for any T ⊂ [n] such that S_{0} ∩ T = ∅ and such that f_{T} (R^{n}) ⊆ f_{S_{0}}(R^{n}), f_{T} is also r-homogeneous.

Proof: We need to show that for any w ∈ R^{n} and any λ ∈ R_{+}

f_{T} (λw_{T}) = λf_{T} (w_{T}).

Since f_{T} (R^{n}) ⊆ f_{S_{0}}(R^{n}), there exists w′ such that

f_{S_{0}}(w′) = f_{T} (w).

Note that S_{0} ∩ T = ∅ implies that we can choose w′ such that w′_{j} = w_{j} for every j ∈ T (because F_{S_{0}} has property (L)). Let w′′ be such that w′′_{i} = w′_{i} for every i ∈ S, w′′_{j} = w_{j} for every j ∉ S. Then, we have

f_{T} (w′′) = f_{T} (w) = f_{S_{0}}(w′) = f_{S_{0}}(w′′)  (8)

where the first and last equality hold because of locality for f_{T} and F_{S_{0}}, respectively. Hence, for any λ > 0,

f_{T} (λw) = f_{T} (λw′′) = f_{S_{0}}(λw′′) = λ^{r}f_{S_{0}}(w′′) = λ^{r}f_{T} (w′′) = λ^{r}f_{T} (w).

The first and the last equality holds because of locality of f_{T} and the construction of w′′, the second one follows from (6), applied to S_{0}, T and w′′, the third one by r-homogeneity of f_{S_{0}}, and the fourth one is just (8).

Lemma 4 Let P satisfy (L), (C), and (ILS). Then for any two non-empty S, T ⊂ [n], f_{S} ∈ F(P) is r-homogeneous if and only if f_{T} ∈ F(P) is r-homo-geneous.

Proof: If S ∩ T = ∅, then this is a direct consequence of Lemma 3 (since f_{S}(R^{n}) = f_{T} (R^{n}) by property (C).

If S ∩ T ≠ ∅, then we use the disjoint case above repeatedly as follows: f_{S} is r-homogeneous if and only if f_{T \S} is r-homogeneous if and only if f_{S\T} is r-homogeneous if and only if f_{T} is r-homogeneous.

Finally, before proving Theorem 1, we need to prove several facts about r-homogeneous functions.

Lemma 5 (Euler’s homogeneity relation, [1]) Let f : R^{n} → R be rhomogeneous and differentiable on the open and connected set D ⊆ R^{n}. Then for any w ∈ D

rf(w) = \frac{∂f(w)}{∂w_{1}}w_{1} + \frac{∂f(w)}{∂w_{2}}w_{2} + … + \frac{∂f(w)}{∂w_{k}}w_{n}.  (9)

Proof: Let G : R_{+} × R^{n} → R and H : R^{n} → R be defined by:

G(λ, w) := f(λw) − λ^{r}f(w) = 0,

H(w) := \frac{∂f(w)}{∂w_{1}}w_{1} + \frac{∂f(w)}{∂w_{2}}w_{2} + … + \frac{∂f(w)}{∂w_{n}}w_{n} − rf(w).

Since

\frac{∂G(λ, w)}{∂λ} = \frac{∂f(λw)}{∂w_{1}}w_{1}+\frac{∂f(λw)}{∂w_{2}}w_{2}+…+\frac{∂f(λw)}{∂w_{n}}w_{n}−rλ^{r−1}f(w)= \frac{1}{λ}H(λw)

we conclude (by setting λ = 1) that H(w) = 0 for all w ∈ D, which is exactly (9).

Lemma 6 Let f : R^{n} → R be an r-homogeneous function satisfying property (S). Then there exist constants C_{i} such that

f(w_{1}, …, w_{n}) = ∑_{i=1}^{n} C_{i}w_{i}^{r}.

Proof: By property (S), there exist functions g_{i} ∈ C^{1}(R), so that Euler’s homogeneity relation (9) can be written as

rf(w) = g(w_{1})w_{1} + g(w_{2})w_{2} + … + g(w_{n})w_{n}.  (10)

Taking the partial derivative with respect to the i-th variable we get:

rg_{i}(w_{i}) = \frac{∂f}{∂w_{i}} (w) = g′(w_{i})w_{i} + g(w_{i})

which must hold for every w_{i}. Hence,

w_{i}g′(w_{i}) − (r − 1)g(w_{i}) = 0, ∀w_{i} ∈ R.

The general solution of this linear homogeneous ordinary differential equation is g(t) = C_{i}t^{r−1} Hence, from (10) we get

f(w) = C_{1}w_{1}^{r} + C_{2}w_{2}^{r} + … + C_{n}w_{n}^{r}.

Proof of Theorem 1: Obviously, any family F(P) where all f_{S} are of the form (5) satisfies relation (6). Hence, by Proposition 2, P has property (ILS). Conversely, suppose that P has property (ILS). Note that (N) implies that f_{S} is 1-homogeneous for any singleton S. Hence, by Lemma 4, we conclude that every f_{T} ∈ F(P) is 1-homogeneous (f_{∅} = 0 by (L) and Lemma 3). Finally, (5) follows from Lemma 6.

3 Discussion

Theorem 1 demonstrates that, if we require that the model satisfy some reasonable criteria (i.e., invariance of the conclusion of optimality under linear scalings of the problem parameters, locality, normality, completeness, and separability), the choice of the objective function is limited to the choice among linear objective functions.

It should be noted that full strength of normality (N) and completeness (C) was not necessary for the proof of the theorem. In fact, one can replace these two properties by the requirement for the existence of an rhomogenous function f_{S} ∈ F(P) and by requiring that

f_{S}(R^{n}) = f_{{1}}(R^{n}) = f_{{2}}(R^{n}) = ⋯ = f_{{n}}(R^{n}) = ⋃_{T ⊂[n]} f_{T} (R^{n}) (11)

holds. Thus we have the following straightforward generalization of Theorem 1:

Theorem 7 Let P be the objective function for the problem (2). Suppose that F(P) satisfies (L), and (S). Furthermore suppose that there exists an r-homogeneous function f_{S} ∈ F(P) and that relation (11) holds. Then P has property (ILS) if and only if for every S ⊂ [n] there exist constants C_{S,i}, i ∈ S, such that

f_{S}(w) = ∑_{i∈S} C_{S,i}w_{i}^{r}.  (12)

Locality (L) and Separability (S) imply that the objective function is smooth (has continuous second partial derivatives). The smoothness was essential in the presented proofs of both Lemma 5 and Lemma 6. It is quite possible that the properties (L) and (S) can be reformulated so that smoothness is not required and that Theorem 7 still holds. As already mentioned, the essence of locality (L) is the requirement that the value of the function f_{S} is independent of the values of w_{i} corresponding to j ∉ S, and the essence of separability (S) is that the rate of change of f_{S} with respect of changing w_{i} depends only on the value of that w_{i}. For example, for any odd p, the function

P (x, w) = (x_{1}w_{1}^{p} + … + x_{n}w_{n}^{p})^{1/p}

does satisfy locality (L), normality (N), completeness (C), and invariance under linear scaling (ILS) but is not separable. So, separability is a necessary property for characterization of linear objective functions.

The objective function defined by (5) is linear, but it is not the objective function of the linear 0-1 programming problem unless all C_{S,i} are equal. Additional (symmetry) properties are needed to ensure that. (Some such properties are presented in [2].)

There are numerous ways to characterize the linear objective function. Our aim was to characterize it by certain properties that seem reasonable from the modeling point of view. The basic property around which we build our characterization is the invariance under linear scalings (ILS). Hence, in describing other “reasonable” properties, we tried to avoid requiring any “nice” behavior with respect to additivity of R^{n} since such property together with (ILS) would strongly indicate that the objective function must have the form of the linear functional on R^{n}. (In our characterization, the additivity is a consequence of 1-homogeneity and separability.) Clearly, our choice of the properties characterizing the linear objective function is subject to discussion. The goal of this paper was not to argue that the characterization of the linear objective functions given by Theorem 1 is better or worse than any other characterization. This paper should only be viewed as an attempt to answer the question from the title: Why is the objective function linear?

Acknowledgement. The support of the National Science Foundation under grant number SES-9211492 to Rutgers University is gratefully acknowledged. I also wish to thank Dr. Fred S. Roberts for helpful comments, and Dr. Devdatt P. Dubhashi for reading preliminary drafts and simplifying the proof of Lemma 4.

References

[1] W. Eichhorn. Functional Equations in Economics. Addison-Wesley, MA, 1978.

[2] A. Pekeč. Limitations on Conclusions from Combinatorial Optimization Models. PhD thesis, Rutgers University, 1996.

[3] F.S. Roberts. Measurement Theory. Addison-Wesley, Reading, MA, 1979.

[4] F.S. Roberts. Meaningfulness of conclusions from combinatorial optimization. Discr. Appl. Math., 29:221–241, 1990.

[5] F.S. Roberts. Limitations of conclusions using scales of measurement. In S.M. Pollock, M.H. Rothkopf, and A. Barnett, editors, Handbooks in OR & MS, volume 6, pages 621–671. North-Holland, NY, 1994.

Recent Publications in the BRICS Report Series

RS-96-50 Aleksandar Peke� c. Hypergraph Optimization Problems: Why is the Objective Function Linear? December 1996. 10 pp.

RS-96-49 Dan S. Andersen, Lars H. Pedersen, Hans H� uttel, and Josva Kleist. Objects, Types and Modal Logics. December 1996. 20 pp. To be presented at the 4th International Workshop on the Foundations of Object-Oriented, FOOL4, 1997.

RS-96-48 Aleksandar Peke� c. Scalings in Linear Programming: Necessary and Suf�cient Conditions for Invariance. December 1996. 28 pp.

RS-96-47 Aleksandar Peke� c. Meaningful and Meaningless Solutions for Cooperative N-person Games. December 1996. 28 pp.

RS-96-46 Alexander E. Andreev and Sergei Soloviev. A Decision Algorithm for Linear Isomorphism of Types with Complexity Cn(log^{2}(n)). November 1996. 16 pp.

RS-96-45 Ivan B. Damg� ard, Torben P. Pedersen, and Birgit P�tzmann. Statistical Secrecy and Multi-Bit Commitments. November 1996. 30 pp.

RS-96-44 Glynn Winskel. A Presheaf Semantics of Value-Passing Processes. November 1996. 23 pp. Extended and revised version of paper appearing in Montanari and Sassone, editors, Concurrency Theory: 7th International Conference, CONCUR ’96 Proceedings, LNCS 1119, 1996, pages 98�114.

RS-96-43 Anna Ing� olfsd� ottir. Weak Semantics Based on Lighted Button Pressing Experiments: An Alternative Characterization of the Readiness Semantics. November 1996. 36 pp. An extended abstract to appear in the proceedings of the 10th Annual International Conference of the European Association for Computer Science Logic, CSL ’96.

RS-96-42 Gerth St�lting Brodal and Sven Skyum. The Complexity of Computing the k-ary Composition of a Binary Associative Operator. November 1996. 15 pp.