On the relationship between the value function and the efficient frontier of a mixed integer linear optimization problem

In this study, we investigate the connection between the efficient frontier (EF) of a general multiobjective mixed integer linear optimization problem (MILP) and the so-called restricted value function (RVF) of a closely related single-objective MILP. In the first part of the paper, we detail the mathematical structure of the RVF, including characterizing the set of points at which it is differentiable, the gradients at such points, and the subdifferential at all nondifferentiable points. We then show that the EF of the multiobjective MILP is comprised of points on the boundary of the epigraph of the RVF and that any description of the EF suffices to describe the RVF and vice versa. Because of the close relationship of the RVF to the EF, we observe that methods for constructing the so-called value function (VF) of an MILP and methods for constructing the EF of a multiobjective optimization problem are effectively interchangeable. Exploiting this observation, we propose a generalized cutting-plane algorithm for constructing the EF of a multiobjective MILP that arises from an existing algorithm for constructing the classical MILP VF. The algorithm identifies the set of all integer parts of solutions on the EF. We prove that the algorithm converges finitely under a standard boundedness assumption and comes with a performance guarantee if terminated early.

1. We use \(\inf \) rather than \(\min \) because the definition of the RVF below introduces the possibility of MILPs with irrational right-hand sides for which attainment of the optimal value is not guaranteed.

2. This is obviously equivalent to \(\partial z_\textrm{LP}(\hat{\zeta }) = \{g\in \mathbb {R}^{\ell }\;:\; z_\textrm{LP}(\zeta ) \ge g^{\top }(\zeta - \hat{\zeta }) + z_\textrm{LP}(\hat{\zeta }),\ \forall \zeta \in \mathbb {R}^{\ell }\}\), since \(z_\textrm{LP}(\zeta )=+\infty \) for \(\zeta \not \in \mathcal {C}_\textrm{LP}\).

3. In the multiobjective optimization literature, the corresponding multiobjective LP is sometimes referred to as a slice problem (Belotti et al. 2013).

Authors and Affiliations

1. Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, USA

   Samira Fallah & Ted K. Ralphs

2. School of Electrical Engineering, Computing and Mathematical Sciences, Curtin University, Perth, WA, Australia

   Natashia L. Boland

Corresponding author

Correspondence to Samira Fallah.

Conflict of interest

The authors declare that they do not have any identifiable conflicting financial interests or personal relationships that could have potentially influenced the findings presented in this paper.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

An instance of RLPVF

Example 6

In Fig. 6, we plot an instance of (RLPVF) obtained from Example 1 by setting \((x_1, x_2)=(0, 0)\). In the plot, the affine functions associated with each extreme point of \({{\mathcal {P}}}_{D}\) are shown for a part of the finite domain. For this example, the dual problem (D-RLPVF) can be expressed as

and we have that the set of extreme points, \(\mathcal {E}\), and the set of extreme rays, \(\mathcal {R}\), of \({{\mathcal {P}}}_{D}\) are

As expected, the function defined by (RLPVF) is a polyhedral function with the nondifferentiable points being those at which the optimal basis changes.

The RLPVF associated with Example 1 when \((x_1, x_2)=(0, 0)\)

Full size image

Not all affine pieces are needed to describe the function and a minimal description is as follows. The finite domain is \(\mathcal {C}_\textrm{LP}= [-55.464, +\infty )\) and for \(\zeta \in \mathcal {C}_\textrm{LP}\), we have

Observe that the gradients of the RLPVF are precisely the optimal dual solutions corresponding to the parametric constraints. At points of nondifferentiability (the breakpoints), the directional derivatives in direction d (in this case, we have \(d \in \{1, -1\}\)) of the RLPVF are given by \(d^\top u\), where u is one of the alternative optimal dual solutions corresponding to the parametric constraint.

The LP frontiers of Example 1

The entire EF for Example 1 is shown below in Fig. 7. The bounding functions associated with each integer vector of Example 1 are illustrated in Fig. 8. To highlight the detail in the bottom right parts of the frontiers more clearly, an enlarged view is presented in Fig. 9.

The whole EF associated with Example 1

Full size image

The LP frontiers. Brown is for \((x_1,x_2)=(0,0)\). Green is for \((x_1,x_2)=(1,0)\). Red is for \((x_1,x_2)=(1,1)\). Blue is for \((x_1,x_2)=(0,1)\). Note the axes are unequally scaled. (Color figure online)

Full size image

The (truncated at the left) LP frontiers. Brown is for \((x_1,x_2)=(0,0)\). Green is for \((x_1,x_2)=(1,0)\). Red is for \((x_1,x_2)=(1,1)\). Blue is for \((x_1,x_2)=(0,1)\). (Color figure online)

Full size image

Proofs regarding the structure of RVF

Here, we present the detailed proofs of results from Sect. 3, along with the statements of and proofs for supporting lemmas and propositions.

Proposition C.1

For \(\zeta \in \mathcal {C}_\textrm{LP}\), we have that

for all \(d \in \mathbb {R}^{\ell }\).

Proof

We let \(\zeta \in \mathcal {C}_\textrm{LP}\) and \(d \in \mathbb {R}^{\ell }\) be given and consider \(\nabla _d z_\textrm{LP}(\zeta )\). There are two cases.

1. (i)

   If \(d \in \delta ^-(\zeta )\), then we have already seen that \(\nabla _d z_\textrm{LP}(\zeta ) = +\infty \), since \(z_\textrm{LP}(\zeta + \epsilon d) = +\infty \) for all \(\epsilon > 0\). Equivalently, we have that \({\text {proj}}_u (OPT(\zeta + \epsilon d)) = \emptyset \) and thus \(\max _{u\in {\text {proj}}_u (OPT(\zeta ))} u^{\top }d = +\infty \), proving the result in this first case.

2. (ii)

   If \(d \not \in \delta ^-(\zeta )\), by (D-RLPVF), there exists \(\epsilon > 0\) such that \(z_\textrm{LP}(\zeta + \epsilon d) < +\infty \). As such, there exists \((\hat{u}, \hat{v})\in \mathcal {E}\) such that

   $$\begin{aligned} z_\textrm{LP}(\zeta +td) = (\zeta +td)^{\top } \hat{u} + \beta ^{\top } \hat{v}, \qquad \forall t\in [0,\epsilon ]. \end{aligned}$$

   (C1)

   Thus \(\nabla _d z_\textrm{LP}(\zeta ) = \hat{u}^{\top }d\). Note that by taking \(t=0\) we have that \(\hat{u} \in {\text {proj}}_u (OPT(\zeta ))\). Now suppose, for the sake of contradiction, that \(\overline{u}^{\top }d > \hat{u}^{\top }d\) for some \(\overline{u}\in {\text {proj}}_u (OPT(\zeta ))\). Then by (2), there must exist \((u, v) \in \mathcal {E}\) with \(u\in {\text {proj}}_u (OPT(\zeta ))\) and \(u^{\top }d > \hat{u}^{\top }d\). But then for any \(t\in (0,\epsilon ]\), we have

   $$\begin{aligned} \begin{aligned} (\zeta +td)^{\top } u+ \beta ^{\top } v = z_\textrm{LP}(\zeta ) + td^{\top } u > z_\textrm{LP}(\zeta ) + td^{\top } \hat{u}&=\zeta ^{\top }\hat{u}+\beta ^{\top } \hat{v} + td^{\top } \hat{u}\\&=z_\textrm{LP}(\zeta +td), \end{aligned} \end{aligned}$$

   where the final equality follows from (C1), which contradicts (D-RLPVF) at \(\zeta +td\). The result follows.

\(\square \)

Proof of Prosition 3.2

The result follows from lemmas C.2, C.3, and C.4, which together show containment and reverse containment of \({\text {proj}}_u (OPT(\zeta ))\) and \(\partial z_\textrm{LP}(\zeta )\). Lemma C.3 is a known result needed to prove Lemma C.4, which we prove here again because part of the proof is referred to later. \(\square \)

Lemma C.2

For all \(\zeta \in \mathcal {C}_\textrm{LP}\), we have that

Proof

Let \(\hat{\zeta }\in \mathcal {C}_\textrm{LP}\) and \(\hat{u}\in {\text {proj}}_u (OPT(\hat{\zeta }))\) be given. We show that \(\hat{u}\in \partial z_\textrm{LP}(\hat{\zeta })\). Let \(\hat{v}\) be such that \((\hat{u},\hat{v})\in {{\mathcal {P}}}_{D}\) and \(\hat{\zeta }^{\top }\hat{u}+ \beta ^{\top }\hat{v} = z_\textrm{LP}(\hat{\zeta })\). Such \(\hat{v}\) must exist by the definitions of \({\text {proj}}_u (OPT(\hat{\zeta }))\). Then for any \(\zeta \in \mathcal {C}_\textrm{LP}\), we have

It follows directly that \(\hat{u}\in \partial z_\textrm{LP}(\hat{\zeta })\). Since \(\hat{\zeta }\) was chosen arbitrarily, the result follows. \(\square \)

Lemma C.3

(Ralphs and Hassanzadeh 2014)

Proof

By Proposition 3.1, \(z_\textrm{LP}\) is a polyhedral function, so its epigraph, given by

is a polyhedron. By the definition of the subdifferential, for any \(\hat{\zeta }\in \mathcal {C}_\textrm{LP}\) and subgradient \(g \in \partial z_\textrm{LP}(\hat{\zeta })\), the hyperplane

is a hyperplane that supports epi \(z_\textrm{LP}\) at \(\zeta = \hat{\zeta }\) and the inequality

is satisfied by all \((\zeta , w)\in {\text {epi}}z_\textrm{LP}\), with equality attained at \((\hat{\zeta },z_\textrm{LP}(\hat{\zeta }))\).

The proof also makes use of the extreme points and extreme rays of the dual LP feasible set. Recall that \(\mathcal {E}\) and \(\mathcal {R}\) are the (finite) sets of extreme points and extreme rays of \({{\mathcal {P}}}_{D}\), respectively. Recall that for \(\zeta \in \mathcal {C}_\textrm{LP}\), we have that

and that by LP duality, we have

\(\square \)

Lemma C.4

For all \(\zeta \in \mathcal {C}_\textrm{LP}\),

Proof

Let \(\hat{\zeta }\in \mathcal {C}_\textrm{LP}\) and \(g\in \partial z_\textrm{LP}(\hat{\zeta })\) be given. Then by Lemma C.3 (and (C4)), it must be that \((\hat{\zeta }, z_\textrm{LP}(\hat{\zeta }))\) is an optimal solution of the LP

which has LP dual

where the \(\gamma \) is the vector of dual variables associated with the first set of constraints, and \(\lambda \) is the vector of dual variables associated with the second set of constraints. Recall that \((\hat{\zeta },z_\textrm{LP}(\hat{\zeta }))\) is an optimal solution of (C5) and let \((\lambda ^*,\gamma ^*)\) be an optimal solution of (C6). Then taking

we have that \((u^* + e^*, v^* + h^*) \in {{\mathcal {P}}}_{D}\) and also that \( \hat{\zeta }^\top (u^* + e^*) = z_\textrm{LP}(\hat{\zeta }) - \beta ^\top (v^* + h^*)\). And finally, since the constraints state that \(g = u^* + e^*\), we have that \(g \in {\text {proj}}_u (OPT(\hat{\zeta }))\). Since \(\hat{\zeta }\) was arbitrary, the result follows. \(\square \)

Corollary C.5

\(z_\textrm{LP}(\zeta )\) is differentiable at \(\zeta \) if and only if \(\zeta \in {\text {int}}\mathcal {C}_\textrm{LP}\) and the dual problem (D-RLP) has a unique optimal solution.

Proof

For \(\zeta \in {\text {int}}\mathcal {C}_\textrm{LP}\), \({\text {proj}}_u (OPT(\zeta ))\) consists of a singleton if and only if (D-RLP) has a unique optimum. By Proposition 3.2, the subdifferential \(\partial z_\textrm{LP}(\zeta )\) is also a singleton if and only if the dual problem given in (D-RLP) has a unique optimum. The result follows. \(\square \)

Proposition C.6

The restricted value function (RVF) z is a lower semi-continuous, nonincreasing function that is composed of a minimum of a finite number of polyhedral functions.

Proof

The RVF is the minimum of a finite number of functions, all of which are polyhedral by Proposition 3.1. The lower semi-continuity property can be established using a proof similar to that presented in Nemhauser and Wolsey (1988). The nonincreasing property of the VF follows from the fact that it is the minimum of a set of nonincreasing functions and must therefore be nonincreasing itself. \(\square \)

Proof of Proposition 3.5

Let \(d \in \mathbb {R}^{\ell }\), and a minimal description \(\mathcal {S}_{\min }\) of z be given. By Theorem 3.4, z is the minimum of a finite set of functions, \(\overline{z}(\cdot ;\ x_I)\), for each \(x_I\in \mathcal {S}_{\min }\), which is a finite set. Furthermore, by Proposition 3.1, each of these functions is polyhedral. Thus, Proposition G.1 (in Appendix G), which is a general result about functions that are the minimum of a finite number of polyhedral functions, applies and yields the first part.

The second part follows by substituting the formula for the directional derivative of the bounding function from Proposition C.1. \(\square \)

Lemma C.7

For any \(\zeta \in \mathcal {C}\) and any minimal description \(\mathcal {S}_{\min }\), there exists \(\epsilon >0\) such that

where \(B(\zeta ;\ \epsilon )\) denotes the open ball of radius \(\epsilon \) centered on \(\zeta \).

Proof

Let \(\mathcal {S}_{\min }\) be given as per Theorem 3.4 and let \(\zeta \in \mathcal {C}\). Recall that by Theorem 3.4,

Define

Here, the bounding functions \(\overline{z}(\cdot ;\ x_I)\) for \(x_I\in S^*_I(\zeta )\cap \mathcal {S}_{\min }\) are those that are both active at \(\zeta \) and included in the given minimal description of the RVF provided by \(\mathcal {S}_{\min }\). Using the notation just introduced, the inequality (C8) simply says \(z(\zeta ') \ge \alpha (\zeta ')\). Now suppose that (C8) does not hold. Since the inequality trivially holds for \(\zeta ' \not \in \mathcal {C}\) (\(z(\zeta ')=+\infty \) in that case), then this means that there is some \(\zeta '\in B(\zeta ;\ \epsilon ) \cap \mathcal {C}\) such that for every \(\epsilon >0\), there exists \(x_I\in \mathcal {S}_{\min }\) with \(\overline{z}(\zeta ';\ x_I)<\alpha (\zeta ')\). This is because \(z(\zeta ')=\overline{z}(\zeta ';\ x_I)\) for some \(x_I\in \mathcal {S}_{\min }\), by (C9). Since there are only a finite number of \(x_I\in \mathcal {S}_{\min }\), and each bounding function \(\overline{z}(\cdot ;\, x_I)\) is polyhedral, actually there must exist one \(\hat{x}_I\in \mathcal {S}_{\min }\) so that for all \(\epsilon >0\), some \(\zeta '\in B(\zeta ;\ \epsilon )\) has \(\overline{z}(\zeta ';\ \hat{x}_I)<\alpha (\zeta ')\). Now \(\overline{z}(\cdot ;\ \hat{x}_I)\) is continuous on its finite domain, which is a closed set, so it must be that \(\overline{z}(\zeta ;\ \hat{x}_I)\le \alpha (\zeta )\). But \(\alpha (\zeta ) = z(\zeta )\le \overline{z}(\zeta ;\ \hat{x}_I)\). So it must be that \(\overline{z}(\zeta ;\ \hat{x}_I)=z(\zeta )\), and \(\hat{x}_I\in \mathcal {S}^*_I(\zeta )\). But then \(\hat{x}_I\in \mathcal {S}^*_I(\zeta )\cap \mathcal {S}_{\min }\), so in fact \(\overline{z}(\zeta ';\ \hat{x}_I)\ge \alpha (\zeta ')\) for all \(\zeta '\in \mathbb {R}^{\ell }\), and we obtain a contradiction. The result follows. \(\square \)

Proof of Proposition 3.7

Let \(\mathcal {S}_{\min }\) be a minimal description of the RVF, and consider \(\zeta \in \mathcal {C}\). Let \(g\in \partial _L z(\zeta )\). Then there exists \(\epsilon >0\) such that

Let \(x_I\in S^*_I(\zeta )\) be chosen arbitrarily. Now for any \(\zeta '\in B(\zeta ;\ \epsilon )\),

where the first inequality follows from the definition of z, the second since g is a local subgradient of z at \(\zeta \), and the final equality follows since \(x_I\in S^*_I(\zeta )\). Thus g is also a local subgradient of \(\overline{z}(\cdot ;\ x_I)\) at \(\zeta \). But \(\overline{z}(\cdot ;\ x_I)\) is a (RLPVF), and so is a convex function over a convex finite domain. Hence

Since \(x_I\) was chosen arbitrarily from \(S^*_I(\zeta )\), we have proved that

To prove containment in the opposite direction, let

By Lemma C.7, there must exist \(\epsilon >0\) so that (C8) holds. Choose \(\zeta '\in B(\zeta ;\ \epsilon )\) arbitrarily. Then, by (C8),

and so there exists some \(x_I\in S^*_I(\zeta )\cap \mathcal {S}_{\min }\) with

where the second inequality follows since \(g\in \partial \overline{z}(\zeta ;\ x_I)\) and the final equality follows since \(x_I\in S^*_I(\zeta )\). Thus \(g\in \partial _L z(\zeta )\) and it must be that

Hence

The result follows by Proposition 3.2. \(\square \)

Theorem 4.1 with \(C^{1:\ell } x = \zeta \)

As mentioned in Sect. 4, we can have another representation of Theorem 4.1. Consider the RVF \(z': \mathbb {R}^{\ell } \rightarrow \mathbb {R}\cup \{\pm \infty \}\) as

where

It is worth noting that the only distinction here is that we have an equality sign for the constraints that serve as our objectives. We formalize the relationship between the RVF and the EF through the following theorem.

Theorem D.1

The following statements hold for \(X_\textrm{MO}\) and the (RVF\('\)) \(z'\).

1. (a)

   If \((x_I,x_C) \in X_\textrm{MO}\) is an efficient solution (equivalently, \(C_I x_I + C_C x_C\) is an NDP), then \((\zeta , c^0x_I+c^0x_C)\) is a point on the boundary of the epigraph of \(z'\) for \(\zeta = C_I^{1:\ell } x_I + C_C^{1:\ell } x_C\).

2. (b)

   If \((\zeta , z'(\zeta ))\) is a point on the boundary of the epigraph of \(z'\) and \(\nabla _d z'(\zeta ) > 0\) for all \(d \in \mathbb {R}^{\ell }_-{\setminus }\{\textbf{0}\}\) for which \(\nabla _d z'(\zeta )\) exists, then there exists an efficient solution \((x_I,x_C) \in X_\textrm{MO}\) that yields \(z'(\zeta )\) and satisfies \(C_I^{1:\ell } x_I + C_C^{1:\ell } x_C = \zeta \).

Proof

The proofs for Part (a) and Part (b) are in accordance with the proofs for Part 1 and Part 2 with the exception of the portion designated by \(\Leftarrow \) in Theorem 4.1. \(\square \)

Here we have a very similar proposition compared to Proposition C.6 as follows.

Proposition D.2

The restricted value function (RVF) is a lower semi-continuous function and decreasing over \(\mathcal {C}\) where the optimal dual value is negative. Furthermore, it is comprised of a minimum of a finite number of polyhedral functions.

Proof

The proof for the property of semi-continuity and being a minimum of a finite number of polyhedral functions is the same as that in Proposition C.6. The decreasing property is straightforward; with negative optimal dual values, the VF is decreasing.\(\square \)

Therefore, in the steps of the algorithm, although we have equality for the constraints with the parametric RHS, i.e., the constraints that serve as our objectives, we must have negative dual variables \(u \in \mathbb {R}_{-}^{\ell }\), which relates to the constraints with the parametric RHS. In this case, the algorithm generates that part of the VF, which is decreasing and is the same as the related EF. As a result, the VF algorithm remains unchanged in this scenario.

Proofs of correctness for the RVF algorithm

The following lemmas are used to prove the correctness of the RVF algorithm, given in Theorem 5.1. We start with the following simple observation.

Lemma E.1

For all \((\hat{x}_I,\hat{x}_C)\in X_\textrm{MO}\), we have that

Proof

The bounding function (CR) associated with \(\hat{x}_I\) is equivalently expressed as

The result follows as \((\hat{x}_I,\hat{x}_C)\) is feasible for the problem above for \(\zeta =C^{1:\ell }_I\hat{x}_I + C^{1:\ell }_C\hat{x}_C\). \(\square \)

The following lemma helps to establish that the integer parts added to \(\mathcal {S}^k\) by the algorithm eventually suffice to describe the whole VF.

Lemma E.2

At iteration k of the algorithm, \(\theta ^{k+1} = \max _{\zeta \in \mathcal {C}} \bar{z}^k(\zeta )-z(\zeta )\).

Proof

Let \(\zeta ^*=\arg \max _{\zeta \in \mathcal {C}} (\bar{z}^k(\zeta )-z(\zeta ))\) and denote \(\zeta ^{k+1} = C^{1:\ell }_Ix^{k+1}_I + C^{1:\ell }_Cx^{k+1}_C\). Since \(\zeta ^*\in \mathcal {C}\) there must exist \((\hat{x}_I,\hat{x}_C)\in X_\textrm{MO}\) with \(\hat{\zeta }:= C^{1:\ell }_I\hat{x}_I + C^{1:\ell }_C\hat{x}_C\le \zeta ^*\) and \(z(\zeta ^*)=c^0_I\hat{x}_I + c^0_C\hat{x}_C = z(\hat{\zeta })\). Further, since \(\bar{z}^k\) is nonincreasing, \(\bar{z}^k(\hat{\zeta })\ge \bar{z}^k(\zeta ^*)\), and hence

The last of these inequalities follows from the fact that \(\zeta ^{k+1} \in \mathcal {C}\). Since

it follows that

Finally, by the definition of \(\theta ^{k+1}\), we have

and the result follows. \(\square \)

The crucial property for establishing termination of the algorithm is that as long as \(\bar{z}^k \not = z\), then in iteration k, we are guaranteed to produce a point not already contained in \(\mathcal {S}^k\). This is established in the lemma below, which states that unless the optimal value of the optimization problem in (7) is zero, the integer part of the solution obtained is not contained in \({{\mathcal {S}}}^k\).

Lemma E.3

Any optimal solution \((x_I^{k+1}, x_C^{k+1})\) to the optimization problem in (7) having optimal value \(\theta ^{k+1} > 0\) has the property that \(x_I^{k+1} \not \in {{\mathcal {S}}}^k\).

Proof

We show the contrapositive of the lemma as follows. Let \((x_I^{k+1}, x_C^{k+1})\) solve the optimization problem in (7) having optimal value \(\theta ^{k+1}\) and suppose that \(x_I^{k+1} \in {{\mathcal {S}}}^k\). Then

where the first inequality follows from (6), since \(x^{k+1}_I\in \mathcal {S}^k\), and the second inequality follows from Lemma E.1, since \((x_I^{k+1}, x_C^{k+1})\in X_\textrm{MO}\). It thus follows, by the definition of \(\theta ^{k+1}\) and \(x^{k+1}\), that

as required to obtain the contrapositive. \(\square \)

Proof of the nonempty stability region of the integer part in each iteration

In this appendix, we show the details of the proof that the integer part added to \(\mathcal {S}^k\) in iteration k has a nonempty stability region at the time it is added. Note, however, that this stability region may end up being redundant by the end of the algorithm. First, we show that the true VF \(z(\zeta ^*)=c^0_I x_I^{k+1} + c^0_C x_C^{k+1}\) whenever \((x_I^{k+1}, x_C^{k+1})\) solves the optimization problem (7) and \(\zeta ^*=C_I^{1:\ell } x_I^{k+1} + C^{1:\ell }_C x_C^{k+1}\).

Lemma F.1

If \((x_I^{k+1}, x_C^{k+1})\) is defined by (7) then \(z(\zeta ^*)=c^0_I x_I^{k+1} + c^0_C x_C^{k+1}\) where \(\zeta ^*=C_I^{1:\ell } x_I^{k+1} + C^{1:\ell }_C x_C^{k+1}\).

Proof

Let \((x_I^{k+1}, x_C^{k+1})\) be defined by (7) and suppose, for the sake of contradiction, that \(z(C_I^{1:\ell } x_I^{k+1} + C^{1:\ell }_C x_C^{k+1})\ne c^0_I x_I^{k+1} + c^0_C x_C^{k+1}\). Then there must exist \((\hat{x}_I,\hat{x}_C)\) a solution of the optimization problem that defines the RVF, \(z(C_I^{1:\ell } x_I^{k+1} + C^{1:\ell }_C x_C^{k+1})\), given by

and it must be that

Now since \(\bar{z}^k\) is nonincreasing, and, by definition, \((\hat{x}_I,\hat{x}_C)\) satisfies

it must be that

Thus

and \((\hat{x}_I,\hat{x}_C)\) must be a feasible solution for the optimization problem in (7) having better objective value than \((x_I^{k+1}, x_C^{k+1})\), which is a contradiction. \(\square \)

Next, we justify our claim that converting to a (strong) efficient solution via (8) again yields a solution to (7). We omit formal proof that the resulting solution must be efficient for (MO-MILP) since this is a straightforward and well-known result from multiobjective optimization.

Lemma F.2

If \((x_I^{k+1}, x_C^{k+1})\) is defined by (7) and \((\hat{x}_I,\hat{x}_C)\) solves (8) then \((\hat{x}_I,\hat{x}_C)\) is also an optimal solution for the optimization problem in (7).

Proof

Let \((x_I^{k+1}, x_C^{k+1})\) be defined by (7) and suppose \((\hat{x}_I,\hat{x}_C)\) solves (8). Then \((\hat{x}_I,\hat{x}_C)\in X_\textrm{MO}\), so is feasible for the optimization problem in (7). Furthermore,

so

and

Since \(\bar{z}^k\) is nonincreasing it must thus be that

and so

Since \((\hat{x}_I,\hat{x}_C)\) is feasible for the optimization problem in (7) and has at least as good an objective value as that of \((x_I^{k+1}, x_C^{k+1})\), it must also solve the optimization problem in (7). \(\square \)

These two lemmas combine to prove that the integer part added to \(\mathcal {S}^k\) at each iteration k of the algorithm has a nonempty stability region.

Proposition F.3

If \(x_I^{k+1}\) is added to \(\mathcal {S}^k\) in iteration k of the RVF Algorithm then its stability region \(\mathcal {C}(x_I^{k+1})\) is nonempty.

Proof

By Lemmas F.1 and F.2, if \(x_I^{k+1}\) is added to \(\mathcal {S}^k\) in iteration k of the RVF Algorithm, then \(x_C^{k+1}\) found in the process has \(c^0_Ix_I^{k+1} + c^0_Cx_C^{k+1}=z(\zeta )\) where \(\zeta =C_I^{1:\ell } x_I^{k+1} + C^{1:\ell }_C x_C^{k+1}\). But by the characterization of the VF as the minimum of a finite set of bounding functions (as per Theorem 3.4), we have that

where the latter inequality follows by Lemma E.1, since \((x_I^{k+1},x_C^{k+1})\in X_\textrm{MO}\). Thus it must be that \(z(\zeta ) = \bar{z}(\zeta ;\ x_I^{k+1})\), so \(\zeta \in \mathcal {C}(x_I^{k+1})\) and the stability region \(\mathcal {C}(x_I^{k+1})\) is nonempty, as required. \(\square \)

Directional derivatives of the minimum of polyhedral functions

Here, we describe the directional derivatives of a function formed by taking the minimum of a finite set of polyhedral functions. We are particularly interested in functions defined over the extended reals.

The properties we identify here are for any such function; they are not specific to VFs. We think it is very likely that the material we provide here has already been published. However we have been unable to locate a source for it, so include it for the sake of completeness.

First, we give definitions and conventions for directional derivatives of functions defined over the extended reals. Then we briefly review the properties of polyhedral functions, before giving our main result on the directional derivatives of the minimum of a finite set of polyhedral functions.

Consider \(f:\mathbb {R}^n\rightarrow \mathbb {R}\cup \{+\infty \}\), a function defined over the extended reals that is bounded below, and so cannot have the value \(-\infty \). We refer to the set of points \(x\in \mathbb {R}^n\) for which \(f(x)<+\infty \) as the finite domain of f. We are interested in functions with closed finite domain. The directional derivative of f at the point \(x\in \mathbb {R}^n\) in direction \(d\in \mathbb {R}^n\) is denoted by \(\nabla _df(x)\) and is defined by

We take \(\nabla _df(x)=0\) if \(f(x)=+\infty \) (meaning x is not in the finite domain of f). If \(f(x) < +\infty \) and there exists \(\epsilon >0\) such that \(f(x+td)=+\infty \) for all \(t\in (0,\epsilon )\), then we say x is on the boundary of the finite domain of f and d points out of it. In this case, \(\nabla _df(x) = +\infty \).

We now turn our attention to the case of a function defined as the minimum of a finite set of polyhedral functions.

Say \(z^k:\mathbb {R}^n\rightarrow \mathbb {R}\cup \{+\infty \}\) is a given polyhedral function for each \(k=1,\dots ,K\), which means that the epigraph over its finite domain is a polyhedron. A property of a polyhedral function is that for any point x and direction d, one of the following cases must hold:

1. 1.

   x is not in the finite domain of \(z^k\), in which case \(\nabla _d z^k(x)=0\),

2. 2.

   x is on the boundary of the finite domain of \(z^k\) and d points out of it, in which case \(\nabla _d z^k(x)=+\infty \), or

3. 3.

   there exists \(\epsilon >0\) such that \(x+td\) is in the finite domain of \(z^k\) for all \(t\in [0,\epsilon ]\), and, furthermore, \(\epsilon \) may be taken to be sufficiently small that all points in the line segment defined as \(\{x+td:\; 0\le t \le \epsilon \}\) lie on the same facet of the polyhedron created by the epigraph of \(z^k\) over its finite domain. In this case, there exists \(a\in \mathbb {R}^n\) and \(b\in \mathbb {R}\) such that \(z^k(x+td)=a^{\top }(x+td)+b\) for all \(t\in [0,\epsilon ]\). Note that a and b depend on x and d, but not on \(\epsilon \), and it follows that \(\nabla _d z^k(x)=a^{\top }d\).

It is also helpful to observe that the finite domain of a polyhedral function must itself be a polyhedron, which is closed.

Let \(z:\mathbb {R}^n\rightarrow \mathbb {R}\cup \{+\infty \}\) be defined to be

Since each function \(z^k\) bounds z from above, we call \(z^k\) a bounding function. Define

to be the index set of the bounding functions that are active at x. Clearly, the finite domain of z is the union of the finite domains of its bounding functions, so is the union of a finite collection of closed sets, and hence is closed.

It is useful to observe that in the case that x is in the finite domain of z and d does not point out of it, then it may be that there is a jump, or discontinuity, in z when moving away from x in the direction d. In other words, for such x and d, it may be that

In such a case, there must exist \(k\in \{1,\dots ,K\}\) and \(\epsilon > 0\) so that \(z(x+td)=z^k(x+td)\) for all \(t\in (0,\epsilon )\), where, importantly, \(t=0\) is not included in this interval. So

and it follows that \(\nabla _d z(x) = +\infty \).

Whether or not z has a discontinuity when moving away from x in direction d, the structure of z as a minimum of a finite set of polyhedral functions ensures that when x is in the finite domain of z and d does not point out of it, there must exist \(k\in \{1,\dots ,K\}\), \(a\in \mathbb {R}^n\) and \(b\in \mathbb {R}\) defining a facet of the epigraph of \(z^k\) over its finite domain, and \(\epsilon >0\) sufficiently small so that

We say that the facet of \(z^k\) defined by (a, b) yields z when moving away from x in direction d.

We now give the main result.

Proposition G.1

For any point \(x\in \mathbb {R}^n\) and any direction \(d\in \mathbb {R}^n\),

Proof

Let the point \(x\in \mathbb {R}^n\) and direction \(d\in \mathbb {R}^n\) be given. There are three main cases.

\(\underline{{\text {Case 1}}:\,x\,{\text {is not in the finite domain of}}\,z.}\)

In this case, \(\nabla _d z(x)= 0\). Furthermore, since \(z(x)=+\infty \), it follows from the definition of z that \(z^k(x)=+\infty \), and hence \(\nabla _d z^k(x)= 0\), for all \(k=1,\dots ,K\). The result follows.

\(\underline{{\text {Case 2}}:\,x\,{\text {is in the boundary of the finite domain of}}\,z\,{\text {and}}\,d\,{\text {points out of it.}}}\)

This means that there exists \(\epsilon >0\) so that \(z(x+td)=+\infty \) for all \(t\in (0,\epsilon )\). By the definition of z, it must be that for all \(k=1,\dots ,K\), \(z^k(x+td)=+\infty \) for all \(t\in (0,\epsilon )\). Now for all \(k\in \kappa ^*(x)\), x is in the finite domain of the bounding function \(z^k\), since \(z^k(x)=z(x) < +\infty \). Thus \(\nabla _d z^k(x)=+\infty \) and the result follows.

\(\underline{{\text {Case 3. there exists}}\, \epsilon >0 \,{\text {such that}}\,z(x+td)<+\infty \,{\text {for all}}\,t\in [0,\epsilon ).}\)

Note that \(t=0\) is included in the definition of this case, since x not in the finite domain of z was covered in Case 1. Assume, without loss of generality, that \(k=1\) is the index of the bounding function having a facet that yields z when moving away from x in direction d. Thus there must exist \(\epsilon '>0\), \(a\in \mathbb {R}^n\) and \(b\in \mathbb {R}\) such that

Let \(k^*\) denote the minimizer of \(\nabla _d z^k(x)\) over \(k\in \kappa ^*(x)\). Note that \(\nabla _d z^1(x) = a^{\top }d\), which is finite. So \(1\in \kappa ^*(x)\) implies \(\nabla _d z^{k^*}(x)\) is finite. Thus if \(\nabla _d z^{k^*}(x)=+\infty \) it must be that \(1\not \in \kappa ^*(x)\). Hence

and \(\nabla _d z(x)=+\infty =\nabla _d z^{k^*}(x)\), as required. Now consider the case that \(\nabla _d z^{k^*}(x)\) is finite. By the properties of polyhedral functions discussed above, there must exist \(\epsilon ''>0\), \(\hat{a}\in \mathbb {R}^n\) and \(\hat{b}\in \mathbb {R}\) such that \(z^{k^*}(x+td)=\hat{a}^{\top }(x+td)+\hat{b}\) for all \(t\in [0,\epsilon '')\), so \(\nabla _d z^{k^*}(x)=\hat{a}^{\top }d\). To summarize, we have

Now suppose, for the sake of contradiction, that \(\hat{a}^{\top }d \ne a^{\top }d\). Define \(\epsilon '''\) by

Observe that \(\epsilon '''>0\) since \(1\in \kappa ^*(x)\) implies \(\hat{a}^{\top }d =\nabla _d z^{k^*}(x)\le \nabla _d z^1(x) = a^{\top }d\), so the case \(\hat{a}^{\top }d > a^{\top }d\) implies that \(1\not \in \kappa ^*(x)\), and so \(z^1(x) > z(x)\). Then for \(0<t<\epsilon '''\) we have that

Now \(z(x)=\hat{a}^{\top } x + \hat{b}\) since \(k^*\in \kappa ^*(x)\), and by continuity of \(z^1\), we also have \(z^1(x)=a^{\top }x+b\). Substituting these in, we obtain

which is equivalently written as

Since \(t>0\), \(t <\epsilon '\) and \(t<\epsilon ''\), it must be that

which contradicts the definition of z. Thus it must be that \(\hat{a}^{\top }d = a^{\top }d\), as required. \(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions