Primal Construction of Integer Programming Value Functions

Seth Brown Rice University, Department of Computational and Applied Mathematics Wenxin Zhang Tsinghua University, Department of Industrial Engineering Temitayo Ajayi Rice University, Department of Computational and Applied Mathematics The University of Texas MD Anderson Cancer Center, Department of Radiation Oncology Andrew J. Schaefer [email protected] Rice University, Department of Computational and Applied Mathematics

A Gilmore-Gomory Construction of Integer Programming Value Functions

Abstract

In this paper, we analyze how sequentially introducing decision variables into an integer program (IP) affects the value function and its level sets. We use a Gilmore-Gomory approach to find parametrized IP value functions over a restricted set of variables. We introduce the notion of maximal connected subsets of level sets - volumes in which changes to the constraint right-hand side have no effect on the value function - and relate these structures to IP value functions and optimal solutions.

Keywords— Value function, level set, parametrized optimization

1 Introduction

Given a constraint matrix $\mathbf{A}\in\mathbb{Z}^{m\times n}_{+}$ and objective coefficients $\mathbf{c}\in\mathbb{Z}^{n}$ , the integer programming (IP) value function represents the optimal objective value of an IP parametrized by the right-hand side. Let $\mathbf{b}\in\mathbb{Z}^{m}_{+}$ be a component-wise upper bound on permissible right-hand sides. Define $\mathcal{B}\coloneqq\bigtimes\limits_{i=1}^{m}[0,b_{i}]$ . Given $\bm{\beta}\in\mathcal{B}$ , the parametrized IP, IP( $\bm{\beta}$ ), and its value function, $z:\mathcal{B}\to\mathbb{R}$ , are defined by

\displaystyle z(\bm{\beta})\coloneqq\max\limits_{\mathbf{x}}\left\{\mathbf{c}^{\top}\mathbf{x}:\mathbf{A}\mathbf{x}\leq\bm{\beta},\ \mathbf{x}\in\mathbb{Z}^{n}_{+}\right\}.

(IP(

\bm{\beta}

))

Note that because of the nonnegativity of $\mathbf{A}$ and $\mathbf{b}$ , without loss of generality we assume $\mathbf{c}$ is also nonnegative. Denote the $j^{th}$ column vector of the matrix $\mathbf{A}$ by $\mathbf{a}_{j}$ . We assume that $\mathbf{a}_{j}\neq\mathbf{0}$ and $\mathbf{a}_{j}\leq\mathbf{b}$ , for all $j\in\{1,\dots,n\}$ . Note that $z(\bm{\beta})=z(\lfloor\bm{\beta}\rfloor)$ for all $\bm{\beta}\in\mathcal{B}$ , and that each parametrized IP is feasible because $\mathbf{0}$ is a feasible solution for each $\bm{\beta}\in\mathcal{B}$ , and the IPs are bounded because $\mathbf{A}$ is nonnegative with no zero columns.

Studying the value function of the parametrized IP is particularly useful in cases where IP( $\bm{\beta}$ ) must be solved many times for different right-hand sides, such as in bilevel programming, where IP( $\bm{\beta}$ ) in the form of the follower problem has its right-hand side depend on the leader problem decisions. Similarly, in stochastic programming, IP( $\bm{\beta}$ ) in the form of the second-stage problem is dependent on both the first-stage decisions and the resolution of uncertain values. Parametrized solution approaches to these problems can be found in, e.g., [11, 19] for bilevel optimization, and [15, 1, 9] for stochastic optimization.

Early work on parametrized IP focuses on value functions and their construction. [5] provide bounds on the variation of the value function relative to the variation of the right-hand sides for both mixed-integer programs (MIPs) and IPs. [6] show that IP value functions are Gomory functions, and [4] generalizes this result for MIPs. [10] use the connection between IP value functions and Gomory functions to produce a primal-dual algorithm for solving 0-1 IPs. [20] provides a doubly recursive procedure using Chvátal functions to construct the value function of a conic integer linear program.

More recent work focuses on the construction and applications of value functions. [14] provide an algorithm for constructing value functions for MIPs. Value functions have also been incorporated into solution approaches for two-stage stochastic integer programs [13, 17]. Various value function approaches have also been applied to the solution of mixed-integer bilevel programs. [16] use a generalized MIP value function, which takes both the objective function coefficients and the constraint right-hand side as arguments, to solve both stochastic and multifollower bilevel MIPs. [3] use Gomory, Chvátal, and Jeroslow functions, as well as value functions, to analyze the representability of mixed-integer bilevel programs.

Some of our results are analogous to the Gilmore-Gomory approach for knapsack problems [7], which uses dynamic programming to recursively determine the value function of a one- or two-dimensional knapsack IP. Our method focuses on one variable at each step; in contrast, the approach in [7] considers all variables at each recursive level.

Thus far, level sets of the value function, along with related topics, such as level-set-minimal vectors, have been sparsely studied. [9] use minimal tenders in a stochastic programming solution approach. [18] introduce the notion of level-set-minimal vectors and use them to represent the value functions of the first and second stage of a stochastic program. [2] relate level-set-minimal vectors to the linear programming relaxation gap functions. The stability regions discussed in [8] are similar to the value function level sets discussed in our work, but [8] use a parametrization of the objective function to study changes to optimal solutions, not the objective value.

In this paper, we examine the properties of the level sets of IP value functions in detail, especially the connections among these level sets as primal variables are added to a problem. We develop a primal construction of the IP value function, in constrast to dual approaches, for example, using Chvátal or Gomory functions [6]. A primal approach enables us to analyze the behavior of restricted versions of the IP. Our contributions are as follows:

1.

We analyze the IP value function over subsets of primal variables, including how the value function’s level sets change as primal variables are added iteratively to the formulation in a Gilmore-Gomory-type procedure.
2.

We characterize the structure of level sets of IPs. We show how the level sets of a restricted IP relate to the level sets when a new variable is included.
3.

We introduce the notion of maximal connected subsets of level sets and demonstrate several properties of these subsets. These results can be used to determine common optimal solutions within a maximal connected subset.

Our key results include:

•

A sufficient condition for a right-hand side to be level-set minimal (\threfdown);
•

A recursive approach to construct variable-restricted value functions (\threfgenstepup);
•

Additional connectedness properties of maximally-connected level sets and lattices (\threfCsteppro and \threfMC_Adjacent).

2 Level Sets of the IP Value Function

For any $\alpha\in\mathbb{R}$ , the level set $S(\alpha)$ of the value function $z$ is the set of right-hand sides over which the function takes on the value $\alpha$ : $S(\alpha)\coloneqq\left\{\bm{\beta}\in\mathcal{B}\,|\,z(\bm{\beta})=\alpha\right\}$ . If $S(\alpha)=\emptyset$ , then for all $\bm{\beta}\in\mathcal{B}$ , $z(\bm{\beta})\neq\alpha$ . In particular, under our assumptions, for all $\alpha\in(-\infty,0)\cup(z(\mathbf{b}),\infty)$ , $S(\alpha)=\emptyset$ . We examine the structure of level sets of IPs and develop properties of level sets over subsets of the primal variables. We focus on the case of adding or removing a single primal variable at a time, but these results can also be extended to sets of primal variables.

Define the restricted value function, $z_{k}(\bm{\beta})$ , with respect to the parametrized IP over the first $k\in\{1,...,n\}$ variables, IP ${}_{k}(\bm{\beta})$ , as

\displaystyle z_{k}(\bm{\beta})\coloneqq\max\limits_{\mathbf{x}}\left\{\sum_{j=1}^{k}c_{j}x_{j}:\sum_{j=1}^{k}\mathbf{a}_{j}x_{j}\leq\bm{\beta},\ \mathbf{x}\in\mathbb{Z}^{k}_{+}\right\}.

(IP

{}_{k}(\bm{\beta}

))

Define $S_{k}(\alpha)\coloneqq\left\{\bm{\beta}\in\mathcal{B}\,|\,z_{k}(\bm{\beta})=\alpha\right\}$ and $\mathrm{opt}_{k}(\bm{\beta})\coloneqq\arg\max\limits_{\mathbf{x}}\left\{\sum_{j=1}^{k}c_{j}x_{j}:\sum_{j=1}^{k}\mathbf{a}_{j}x_{j}\leq\bm{\beta},\ \mathbf{x}\in\mathbb{Z}^{k}_{+}\right\}$ .

2.1 Properties of Restricted Value Functions

We apply fundamental properties of the IP value function to restricted value functions.

Proposition 1.

[21]\thlabelelementary Basic properties of the restricted value functions $z_{k}$ , for $k=1,\dots,n,$ include:

(1)

$z_{k}(\mathbf{a}_{j})\geq c_{j}$ for $j=1,\dots,k$ .
(2)

$z_{k}$ is nondecreasing over $\mathcal{B}$ .
(3)

$z_{k}$ is superadditive over $\mathcal{B}$ ; i.e., for all $\bm{\beta}_{1}$ , $\bm{\beta}_{2}\in\mathcal{B}$ , $\bm{\beta}_{1}+\bm{\beta}_{2}\in\mathcal{B}$ , $z_{k}(\bm{\beta}_{1})+z_{k}(\bm{\beta}_{2})\leq z_{k}(\bm{\beta}_{1}+\bm{\beta}_{2})$ .

Proposition 2.

[12]\thlabelIPCS Given $k\in\{1,...,n\}$ , if $\mathbf{x}^{*}$ $\in\mathrm{opt}_{k}(\bm{\beta})$ , then for all $\mathbf{x}\in\mathbb{Z}_{+}^{k}$ such that $\mathbf{x}\leq$ $\mathbf{x}^{*}$ , $z_{k}(\sum_{j=1}^{k}\mathbf{a}_{j}x_{j})=\sum_{j=1}^{k}c_{j}x_{j}$ and $z_{k}(\sum_{j=1}^{k}\mathbf{a}_{j}x_{j})+z_{k}(\bm{\beta}-\sum_{j=1}^{k}\mathbf{a}_{j}x_{j})=z_{k}(\bm{\beta})$ .

\thref

IPCS is often referred to as IP complementary slackness.

Lemma 1.

\thlabel

nondecreasingbetweeniterations For all $k\in\{2,...,n\}$ , if $\bm{\beta}\in S_{k-1}(\alpha_{1})$ and $\bm{\beta}\in S_{k}(\alpha_{2})$ , then $\alpha_{2}\geq\alpha_{1}$ .

\thref

nondecreasingbetweeniterations states that $z_{k}(\bm{\beta})$ increases monotonically with $k$ for fixed $\bm{\beta}$ - as more variables become available, the value of the restricted problem can only improve.

Lemma 2.

\thlabel

notOptimal Given $k\in\{2,...,n\}$ , $\mathbf{x}\in\mathbb{Z}^{k}_{+}$ such that $\sum_{j=1}^{k}\mathbf{a}_{j}x_{j}\leq\mathbf{b}$ , let $\alpha=\sum_{j=1}^{k}c_{j}x_{j}$ . If $S_{k}(\alpha)=\emptyset$ , then ${\mathbf{x}}\notin\mathrm{opt}_{k}(\sum_{j=1}^{k}\mathbf{a}_{j}{x}_{j})$ .

Hence, \threfnotOptimal gives a necessary condition for optimality. Let $\mathbf{e}_{i}$ indicate the $i$ th unit vector.

Proposition 3.

\thlabel

schaeferoriginal Given $k\in\{2,...,n\}$ and $\bm{\beta}\in\mathcal{B}$ , let $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bm{\beta})$ . We have:

(1)

For all $t\in\mathbb{Z}_{+}$ such that $t\leq x^{*}_{k}$ , $z_{k}(\bm{\beta})=z_{k}(\bm{\beta}-t\mathbf{a}_{k})+z_{k}(t\mathbf{a}_{k})=z_{k-1}(\bm{\beta}-\mathbf{a}_{k}x^{*}_{k})+c_{k}{x}_{k}^{*}$ . Further, $\mathbf{x}^{*}-t\mathbf{e}_{k}\in\mathrm{opt}_{k}(\bm{\beta}-t\mathbf{a}_{k})$ , and if $\bm{\beta}\in S_{k}(\alpha)$ , then $\bm{\beta}-t\mathbf{a}_{k}\in S_{k}(\alpha-tc_{k})$ .
(2)

If $\bm{\beta}\in S_{k}(\alpha)$ , then $\bm{\beta}-\mathbf{a}_{k}x^{*}_{k}\in S_{k-1}(\alpha-c_{k}x^{*}_{k})$ .
(3)

If $\bm{\beta}\in S_{k}(\alpha)$ and $S_{k-1}(\alpha)=\emptyset$ , then $x^{*}_{k}>0$ .

Proof.

Statements (1)-(2) follow from \threfIPCS. For (3), suppose that $x^{*}_{k}=0$ . By (2), $\bm{\beta}\in S_{k-1}(\alpha)$ , which is a contradiction. ∎

\thref

schaeferoriginal demonstrates how the structure of optimal solutions can determine members of level sets over a restricted set of primal variables. In particular, \threfschaeferoriginal shows the impact on the value of a particular $\bm{\beta}$ after removing a primal variable from the restricted problem. In addition, given $\bm{\beta}$ and $k$ , and given $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bm{\beta})$ , for any feasible solution $\mathbf{x}\leq\mathbf{x}^{*}$ \threfIPCS implies ${\mathbf{x}}\in\mathrm{opt}_{k}(\sum_{j=1}^{k}\mathbf{a}_{j}x_{j})$ .

2.2 Level-Set-Minimal Vectors

Level-set-minimal vectors represent the efficient frontiers for the corresponding level sets and can be used to construct the boundaries of a value function’s level sets.

Definition 1.

[18]\thlabelminimal A vector $\bm{\beta}\in\mathcal{B}$ is level-set-minimal with respect to $z:\mathcal{B}\rightarrow\mathbb{R}$ if $z(\bm{\beta}-\delta\mathbf{e}_{i})<z(\bm{\beta})$ for all $\delta>0$ for all $i\in\{1,\dots,m\}$ such that $\bm{\beta}-\delta\mathbf{e}_{i}\in\mathcal{B}$ . For all $k\in\{1,...,n\}$ , $\bar{\mathbf{B}}_{k}\subset\mathbb{Z}^{m}_{+}$ is the set of level-set-minimal vectors with respect to $z_{k}$ . Further, $\bar{\mathbf{B}}=\bar{\mathbf{B}}_{n}$ is the set of level-set-minimal vectors with respect to $z$ .

We define $\bar{\mathcal{B}}$ , the component-wise integral subset of the domain of $z$ , as $\bar{\mathcal{B}}\coloneqq\mathcal{B}\cap\mathbb{Z}^{m}_{+}$ .

Remark 1.

Note that if $\bm{\beta}\in\bar{\mathcal{B}}$ , \threfminimal can be simplified as $\bm{\beta}$ is level-set-minimal if $z(\bm{\beta}-\mathbf{e}_{i})<z(\bm{\beta})$ for all $i\in\{1,...,m\}$ such that $\bm{\beta}-\mathbf{e}_{i}\in\bar{\mathcal{B}}$ .

Determining whether a vector is level-set-minimal is NP-complete ([18]). Thus, we provide a variety of necessary and sufficient conditions to verify whether a right-hand side is level-set-minimal.

\thref

equal states that the set of level-set-minimal vectors is a subset of the image of $\mathbf{A}$ over $\mathbb{Z}^{n}_{+}$ , which implies that all optimal solutions of a level-set-minimal vector are tight at all constraints. Note that for any $\bm{\beta}_{1},\bm{\beta}_{2}\in\mathbb{R}^{m}$ , we say that $\bm{\beta}_{1}\lneq\bm{\beta}_{2}$ if $\bm{\beta}_{1}\leq\bm{\beta}_{2}$ , and $\bm{\beta}_{1}\neq\bm{\beta}_{2}$ .

Lemma 3.

\thlabel

equal Given $k\in\{1,...,n\}$ , for all $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ and all $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bm{\beta})$ , $\sum_{j=1}^{k}\mathbf{a}_{j}x^{*}_{j}=\bm{\beta}$ .

\thref

LSMiter provides a sufficient condition under which a level-set-minimal vector with $k-1$ variables maintains level-set-minimality with $k$ variables.

Proposition 4.

\thlabel

LSMiter Let $\bm{\beta}\in\bar{\mathbf{B}}_{k-1}$ . If for all $\bar{\bm{\beta}}\lneq\bm{\beta}$ and all $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bar{\bm{\beta}})$ , $x^{*}_{k}=0$ , then $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ .

Note that there are some conditions under which $\bm{\beta}\in\bar{\mathbf{B}}_{k-1}$ and $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ but there exists $\bar{\bm{\beta}}\lneq\bm{\beta}$ with $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bar{\bm{\beta}})$ , $x^{*}_{k}>0$ . For example, if $\mathbf{a}_{k-1}=\mathbf{a}_{k}$ and $c_{k-1}=c_{k}$ , then $\bar{\mathbf{B}}_{k-1}=\bar{\mathbf{B}}_{k}$ , but any $\bar{\bm{\beta}}$ with $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bar{\bm{\beta}})$ , $x^{*}_{k}=0$ , $x^{*}_{k-1}>0$ will also have $\mathbf{x}^{*}-\mathbf{e}_{k-1}+\mathbf{e}_{k}$ as an optimal solution.

Parametrized IP 2.2 is used in examples throughout. Note that the constraint right-hand side upper bound, $\mathbf{b}$ , is specified for each example, or $\mathcal{B}$ is given to be unbounded above.

	$\displaystyle\max\limits_{\mathbf{x}}\$	$\displaystyle 2x_{1}+3x_{2}+4x_{3}+3x_{4}+3x_{5}+6x_{6}$
	s.t.	$\displaystyle\begin{pmatrix}1&2&1&1&1&2\\ 1&1&2&1&3&2\end{pmatrix}\mathbf{x}\leq\bm{\beta},\ \mathbf{x}\in\mathbb{Z}^{6}_{+}.$		(EXIP $(\bm{\beta})$ )

Example 1.

\thlabel

exExampleIP Consider 2.2 with $\mathbf{b}=(3,4)^{\top}$ , and $\bm{\beta}=(3,3)^{\top}\in\bar{\mathbf{B}}_{4}$ . For all $\bar{\bm{\beta}}\lneq\bm{\beta}$ and for all $\mathbf{x}^{*}\in\mathrm{opt}_{5}(\bar{\bm{\beta}})$ , $x^{*}_{5}=0$ . As such, $\bm{\beta}\in\bar{\mathbf{B}}_{5}$ . ∎

\thref

LSMlinind uses a linear independence relationship among a subset of primal variables to provide a necessary condition for level-set-minimal vectors.

Proposition 5.

\thlabel

LSMlinind If $\bm{\beta}\notin\bar{\mathbf{B}}_{k-1}$ , $\mathbf{a}_{1},\dots,\mathbf{a}_{k}$ are linearly independent, and $\bm{\beta}$ and $\mathbf{a}_{k}$ are linearly independent, then for all $t\in\mathbb{Z}_{+}$ such that $\bm{\beta}+t\mathbf{a}_{k}\in\mathcal{B}$ , $\bm{\beta}+t\mathbf{a}_{k}\notin\bar{\mathbf{B}}_{k}$ .

\thref

LSMiter,LSMlinind provide conditions for which a right-hand side is level-set-minimal as primal variables are added. In contrast, \threfschaefer gives a sufficient condition such that a right-hand side is level-set-minimal as primal variables are removed.

Proposition 6.

\thlabel

schaefer If $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ and $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bm{\beta})$ , then $\bm{\beta}-\mathbf{a}_{k}x^{*}_{k}\in\bar{\mathbf{B}}_{k-1}.$

Proof.

Suppose $\bm{\beta}-\mathbf{a}_{k}x^{*}_{k}\not\in\bar{\mathbf{B}}_{k-1}$ , then there exists $\bm{\pi}\in\bar{\mathbf{B}}_{k-1}$ such that $\bm{\pi}\lneq\bm{\beta}-\mathbf{a}_{k}x^{*}_{k}$ and $z_{k-1}(\bm{\pi})=z_{k-1}(\bm{\beta}-\mathbf{a}_{k}x^{*}_{k})$ . Let $\bar{\mathbf{x}}\in\mathrm{opt}_{k-1}(\bm{\pi})$ . Because $\bm{\pi}\lneq\bm{\beta}-\mathbf{a}_{k}x^{*}_{k},$ and $\sum\limits_{j=1}^{k-1}c_{j}\bar{x}_{j}=z_{k-1}(\bm{\pi})=z_{k-1}(\bm{\beta}-\mathbf{a}_{k}x^{*}_{k}),$ we have $\bar{\mathbf{x}}\in\mathrm{opt}_{k-1}(\bm{\beta}-\mathbf{a}_{k}x^{*}_{k})$ . Moreover, ( $x^{*}_{1},\dots,x^{*}_{k-1})^{\top}$ is a feasible solution to IP ${}_{k-1}(\bm{\beta}-\mathbf{a}_{k}x^{*}_{k})$ , which implies that $\sum\limits_{j=1}^{k-1}c_{j}\bar{x}_{j}\geq\sum\limits_{j=1}^{k-1}c_{j}x^{*}_{j}$ .

Let $\hat{\mathbf{x}}=(\bar{x}_{1},\dots,\bar{x}_{k-1},x^{*}_{k})^{\top}$ . Then $\sum\limits_{j=1}^{k}c_{j}\hat{x}_{j}=\sum\limits_{j=1}^{k-1}c_{j}\bar{x}_{j}+c_{k}x^{*}_{k}\geq\sum\limits_{j=1}^{k}c_{j}x^{*}_{j}$ , and because $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bm{\beta}),\hat{\mathbf{x}}\in\mathrm{opt}_{k}(\bm{\beta})$ . However, $\sum\limits_{j=1}^{k}\mathbf{a}_{j}\hat{x}_{j}=\sum\limits_{j=1}^{k-1}\mathbf{a}_{j}\bar{x}_{j}+\mathbf{a}_{k}x^{*}_{k}=\bm{\pi}+\mathbf{a}_{k}x^{*}_{k}\lneq\bm{\beta}$ , which implies that $\bm{\beta}\not\in\bar{\mathbf{B}}_{k}$ , a contradiction. ∎

Example LABEL:exExampleIP (continued).

In (EXIP), if $\mathbf{b}=(3,4)^{\top}$ , then $\bm{\beta}=(3,3)^{\top}\in\bar{\mathbf{B}}_{3}$ , and $(0,1,1)^{\top}\in\mathrm{opt}_{3}(\bm{\beta})$ . Hence, $(3,3)^{\top}-\mathbf{a}_{3}=(2,1)^{\top}\in\bar{\mathbf{B}}_{2}$ . ∎

Proposition 7.

\thlabel

down If $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\sum_{j=1}^{k}\mathbf{a}_{j}x^{*}_{j})$ and $\sum_{j=1}^{k}\mathbf{a}_{j}x_{j}^{*}\in\bar{\mathbf{B}}_{k}$ , then for all $\mathbf{x}\in\mathbb{Z}_{+}^{k}$ such that $\mathbf{x}\lneq\mathbf{x}^{*}$ , we have $\sum_{j=1}^{k}\mathbf{a}_{j}{x}_{j}\in\bar{\mathbf{B}}_{k}$ .

Proof.

Suppose there exists $\mathbf{x}^{1}\lneq{\mathbf{x}^{*}}$ such that $\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{1}_{j}\not\in\bar{\mathbf{B}}_{k}.$ Then there exists $\mathbf{x}^{2}\in\mathrm{opt}_{k}(\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{1}_{j})$ such that $\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{2}_{j}\lneq\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{1}_{j}$ . Let $\mathbf{x}^{3}=\mathbf{x}^{2}+({\mathbf{x}^{*}}-\mathbf{x}^{1})$ . Then, $\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{3}_{j}=\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{2}_{j}+\sum\limits_{j=1}^{k}\mathbf{a}_{j}{x}^{*}_{j}-\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{1}_{j}\lneq\sum\limits_{j=1}^{k}\mathbf{a}_{j}{x}_{j}^{*}.$ Because $\mathbf{x}^{2}\in\mathrm{opt}_{k}(\sum\limits_{j=1}^{k}\mathbf{a}_{k}x^{1}_{j})$ , $\sum\limits_{j=1}^{k}c_{j}x^{3}_{j}=\sum\limits_{j=1}^{k}c_{j}(x^{2}_{j}+{x}^{*}_{k}-x^{1}_{j})\geq\sum\limits_{j=1}^{k}c_{j}{x}^{*}_{j}$ , and because ${\mathbf{x}^{*}}\in\mathrm{opt}_{k}(\sum\limits_{j=1}^{k}\mathbf{a}_{j}{x}^{*}_{j}),\mathbf{x}^{3}\in\mathrm{opt}_{k}(\sum\limits_{j=1}\mathbf{a}_{j}{x}^{*}_{j})$ . However, $\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{3}_{j}\lneq\sum\limits_{j=1}^{k}\mathbf{a}_{j}{x}^{*}_{j}$ , which contradicts \threfequal. ∎

Proposition 8.

\thlabel

anotinB Let $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ . If $\mathbf{a}_{j}\notin\bar{\mathbf{B}}_{k}$ , then for all $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bm{\beta})$ , $x^{*}_{j}=0$ .

Corollary 1.

\thlabel

relationship $\bar{\mathbf{B}}_{k}\subseteq\left\{\bm{\beta}\in\bar{\mathcal{B}}\,|\,\bm{\beta}=\hat{\bm{\beta}}+t\mathbf{a}_{k},\hat{\bm{\beta}}\in\bar{\mathbf{B}}_{k-1},t\in\mathbb{Z}_{+}\right\}$ .

Propositions 7 and 8 state sufficient and necessary conditions, respectively, to ensure that subsets of right-hand sides are all level-set-minimal. \threfdown requires a known optimal solution and generalizes a result of [18], who prove the case of $k=n$ . In contrast, \threfanotinB relies on the value function.

Proposition 9.

\thlabel

downt If there exists $t\in\mathbb{Z}_{+}$ such that $\bm{\beta}+t\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ and $z_{k}(\bm{\beta}+t\mathbf{a}_{k})=z_{k}(\bm{\beta})+tc_{k}$ , then for all $s\leq t,s\in\mathbb{Z}_{+}$ , $\bm{\beta}+s\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ .

Proof.

Suppose there exists $s<t,s\in\mathbb{Z}_{+}$ such that $\bm{\beta}+s\mathbf{a}_{k}\notin\bar{\mathbf{B}}_{k}$ . Then there exists $\bm{\pi}\lneq\bm{\beta}+s\mathbf{a}_{k}$ such that $z_{k}(\bm{\pi})=z_{k}(\bm{\beta}+s\mathbf{a}_{k})$ . Then by superadditivity,

z_{k}(\bm{\pi}+(t-s)\mathbf{a}_{k})\geq z_{k}(\bm{\pi})+(t-s)c_{k}=z_{k}(\bm{\beta}+s\mathbf{a}_{k})+(t-s)c_{k}\geq z_{k}(\bm{\beta})+tc_{k}=z_{k}(\bm{\beta}+t\mathbf{a}_{k}).

Because $\bm{\pi}\lneq\bm{\beta}+s\mathbf{a}_{k}$ , $\bm{\pi}+(t-s)\mathbf{a}_{k}\lneq\bm{\beta}+t\mathbf{a}_{k}$ , and $z_{k}(\bm{\pi}+(t-s)\mathbf{a}_{k})\geq z_{k}(\bm{\beta}+t\mathbf{a}_{k})$ , then by monotonicity, $z_{k}(\bm{\beta}+(t-s)\mathbf{a}_{k})\geq z_{k}(\bm{\beta}+t\mathbf{a}_{k})$ , so that $\bm{\beta}+t\mathbf{a}_{k}\notin\bar{\mathbf{B}}_{k}$ , a contradiction. ∎

Remark 2.

If $\bm{\beta}\in\bar{\mathbf{B}}_{k-1}$ and $\bm{\beta}\notin\bar{\mathbf{B}}_{k}$ , then for all $t\in\mathbb{Z}_{+}$ such that $\bm{\beta}+t\mathbf{a}_{k}\in\bar{\mathcal{B}}$ , either

(1)

$\bm{\beta}+t\mathbf{a}_{k}\notin\bar{\mathbf{B}}_{k}$ ; or
(2)

$\bm{\beta}+t\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ , $z_{k}(\bm{\beta}+t\mathbf{a}_{k})>z_{k}(\bm{\beta})+tc_{k}$ . Further, there exist $\hat{\bm{\beta}}\in\bar{\mathbf{B}}_{k},\,\hat{t}\in\mathbb{Z}_{+}$ such that $\bm{\beta}+t\mathbf{a}_{k}=\hat{\bm{\beta}}+\hat{t}\mathbf{a}_{k}$ and $z_{k}(\bm{\beta}+t\mathbf{a}_{k})=z_{k}(\hat{\bm{\beta}})+\hat{t}c_{k}$ .

Therefore, level-set-minimal vectors can be obtained by adding primal variables and the corresponding columns of $\mathbf{A}$ to the problem one at a time.

2.3 Order of Primal Decision Variables

We have shown a number of properties of value functions and level-set-minimal vectors when we introduce variables $x_{k}$ for a given ordering ( $k=1,2,\dots,n$ ) one at a time. However, if the ordering provided is arbitrary, then at each step $k$ , it must first be determined if $\mathbf{a}_{k}$ should be added into the problem, or if it is strictly dominated by other variables and can be excluded from consideration. Here, we consider which variables are necessary to include to obtain an optimal solution; note that the order in which the decision variables are added can influence the construction of the level sets.

Lemma 4.

[21]\thlabel¿0 If $z_{n}(\mathbf{a}_{j})>c_{j}$ , then for all $\bm{\beta}\in\mathcal{B}$ and all $\mathbf{x}^{*}\in\mathrm{opt}_{n}(\bm{\beta})$ , $x^{*}_{j}=0$ .

By \thref¿0 and \threfanotinB, only vectors $\mathbf{a}_{j}\in\bar{\mathbf{B}}$ such that $z_{n}(\mathbf{a}_{j})=c_{j}$ are necessary to find an optimal solution for a given right-hand side.

Lemma 5.

\thlabel

LSMkton Suppose $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ and $z_{k}(\mathbf{a}_{k})=c_{k}$ , for some $k\in\{1,\dots,n\}$ . Further suppose that for all $\hat{k}\in\mathbb{Z}_{+}$ such that $k<\hat{k}\leq n$ , we have $\mathbf{a}_{k}-\mathbf{a}_{\hat{k}}\not\in\mathcal{B}$ . Then, $z_{n}(\mathbf{a}_{k})=c_{k}$ and $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{n}$ .

By \threfLSMkton, the columns of $\mathbf{A}$ should be ordered such that $\mathbf{a}_{1}\lneq\mathbf{a}_{2}\lneq\dots\mathbf{a}_{n}$ . Some of these columns cannot be compared with each other, in which case it is sufficient to ensure that for all $k,\hat{k}\in\mathbb{N}$ where $k<\hat{k}\leq n$ , $\mathbf{a}_{k}-\mathbf{a}_{\hat{k}}\notin\mathcal{B}$ . By ordering the variables in this manner, it is sufficient to check if $z_{k}(\mathbf{a}_{k})=c_{k}$ and $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ to evaluate whether or not to add variable $k$ to the set during the $k^{th}$ step. By \threfnondecreasingbetweeniterations, to check if $z_{k}(\mathbf{a}_{k})=c_{k}$ , we first check if $z_{k-1}(\mathbf{a}_{k})\leq c_{k}$ , then if $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ .

\thref

altvalue demonstrates the possible relationships between $z_{k-1}(\mathbf{a}_{k})$ and $z_{k}(\mathbf{a}_{k})$ , and the impact of this on the membership of $\mathbf{a}_{k}$ in $\bar{\mathbf{B}}_{k}$ .

Proposition 10.

\thlabel

altvalue Exactly one of the following holds:

(i)

$z_{k-1}(\mathbf{a}_{k})<c_{k}$ . Then $z_{k}(\mathbf{a}_{k})=c_{k}$ and $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ .
(ii)

$z_{k-1}(\mathbf{a}_{k})=c_{k}$ . Then $z_{k}(\mathbf{a}_{k})=c_{k}$ .
(iii)

$z_{k-1}(\mathbf{a}_{k})>c_{k}$ . Then $z_{k}(\mathbf{a}_{k})=z_{k-1}(\mathbf{a}_{k})$ .

Thus, $z_{k}(\mathbf{a}_{k})=\max\left\{z_{k-1}(\mathbf{a}_{k}),c_{k}\right\}$ . In addition, if $z_{k-1}(\mathbf{a}_{k})\geq c_{k}$ , $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ if and only if $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k-1}$ .

Example LABEL:exExampleIP (continued).

In (EXIP), with $\mathbf{b}=(3,3)^{\top}$ :

(i)

$z_{3}(\mathbf{a}_{3})=4$ and $z_{2}(\mathbf{a}_{3})=2$ , so $\mathbf{a}_{3}\in\bar{\mathbf{B}}_{3}$ ,
(ii)

$z_{5}(\mathbf{a}_{5})=3$ , $z_{4}(\mathbf{a}_{5})=3$ , and $\mathbf{x}^{*}=\mathbf{e}_{4}\in\mathrm{opt}_{4}(\mathbf{a}_{5})$ has $\sum_{j=1}^{4}\mathbf{a}_{j}x^{*}_{j}<\mathbf{a}_{5}$ , so $\mathbf{a}_{5}\notin\bar{\mathbf{B}}_{5}$ , and
(iii)

$z_{6}(\mathbf{a}_{6})=6$ and $\mathrm{opt}_{5}(\mathbf{a}_{6})=\{2\mathbf{e}_{4}\}$ , so for all $\mathbf{x}\in\mathrm{opt}_{5}(\mathbf{a}_{6})$ , $\sum_{j=1}^{5}\mathbf{a}_{j}x^{*}_{j}=\mathbf{a}_{6}$ , so $\mathbf{a}_{6}\in\bar{\mathbf{B}}_{6}$ . ∎

\thref

genstepup generalizes \threfaltvalue to relationships between $z_{k-1}(\bm{\beta})$ and $z_{k}(\bm{\beta})$ for arbitrary fixed $\bm{\beta}$ ; in particular, \threfgenstepup suggests a Gilmore-Gomory approach for solving IP $(\bm{\beta})$ or IP ${}_{k}(\bm{\beta})$ . The classic Gilmore-Gomory recursion is ([12]):

z(\bm{\beta})=\max\left\{z(\bm{\beta}-\mathbf{a}_{j})+c_{j}\,|\,j\in\{1,...,n\},\mathbf{a}_{j}\leq\bm{\beta}\right\}.

Proposition 11.

\thlabel

genstepup Given $\bm{\beta}\in\mathcal{B}$ , $z_{k}(\bm{\beta})=\max\limits_{\ell}\left\{z_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})+\ell c_{k}\,|\,\ell\mathbf{a}_{k}\leq\bm{\beta},\ell\in\mathbb{Z}_{+}\right\}$ .

Proof.

Suppose $z_{k}(\bm{\beta})>\max\limits_{\ell}\left\{z_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})+\ell c_{k}\,|\,\ell\mathbf{a}_{k}\leq\bm{\beta},\ell\in\mathbb{Z}_{+}\right\}$ ; equivalently, there exists $\mathbf{x}^{*}$ such that $\sum_{j=1}^{k}\mathbf{a}_{j}x_{j}^{*}\leq\bm{\beta}$ and $\sum_{j=1}^{k}c_{j}x_{j}^{*}>\max\limits_{\ell\in\mathbb{Z}_{+}:\,\ell\mathbf{a}_{k}\leq\bm{\beta}}z_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})+\ell c_{k}$ . Then $\sum_{j=1}^{k-1}x_{j}^{*}c_{j}>\max\limits_{\ell\in\mathbb{Z}_{+}:\,\ell\mathbf{a}_{k}\leq\bm{\beta}}z_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})+c_{k}(\ell-x_{k}^{*})\geq z_{k-1}(\bm{\beta}-x_{k}^{*}\mathbf{a}_{k})$ , a contradiction. On the other hand, suppose $z_{k}(\bm{\beta})<\max\limits_{\ell}\left\{z_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})+\ell c_{k}:\ell\mathbf{a}_{k}\leq\bm{\beta},\ \ell\in\mathbb{Z}_{+}\right\}$ ; that is, there exists $\ell\in\mathbb{Z}_{+}$ such that $\ell\mathbf{a}_{k}\leq\bm{\beta}$ and $z_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})+\ell c_{k}>z_{k}(\bm{\beta})$ . Let $\mathbf{x}^{*}\in\mathrm{opt}_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})$ , and define $\mathbf{x}^{\prime}\in\mathbb{Z}^{k}$ as $x^{\prime}_{j}=x^{*}_{j}$ for $j\in\{1,\dots,k-1\}$ and $x^{\prime}_{k}=\ell$ . Then $\mathbf{x}^{\prime}$ is feasible for IP ${}_{k}(\bm{\beta})$ ; thus, $z_{k}(\bm{\beta})\geq\sum\limits_{j=1}^{k}c_{j}x^{\prime}_{j}=z_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})+\ell c_{k}>z_{k}(\bm{\beta})$ , a contradiction. We conclude that $z_{k}(\bm{\beta})=\max\limits_{\ell\in\mathbb{Z}_{+}:\,\ell\mathbf{a}_{k}\leq\bm{\beta}}z_{k-1}(\bm{\beta}-\ell\mathbf{a}_{k})+\ell c_{k}$ . ∎

The key differences between the two approaches are that \threfgenstepup focuses on a single variable from the problem at each level of the recursion, while all variables remain present throughout the Gilmore-Gomory approach given in [12]. In addition, the number of problems generated by \threfgenstepup depends on the maximum number of $\mathbf{a}_{k}$ which can be removed from $\bm{\beta}$ , while the number of problems generated by the classic recursion is equal to the number of columns less than or equal to $\bm{\beta}$ in a component-wise sense.

3 Maximal Connected Level Sets of the IP Value Function

A level set of the IP value function may consist of multiple subsets of the hyperrectangle $\mathcal{B}$ that are not connected (see \threfTstep and Figures 3 and 3). Hence, the structure of optimal solutions may vary greatly within the same level set. Having access to connected subsets of level sets for the recourse value function in these problems could allow for optimization with respect to a connected set of right-hand sides in each subset as a subproblem with fixed second-stage value and known allowable variability with respect to those bounds. We explore connected subsets of level sets, and in particular, we define and discuss properties of maximal connected subsets of level sets. Maximal connected level lattices (MC-level lattices) are MC-level sets intersected with the lattice $\mathbb{Z}^{m}_{+}$ . Note that because we are interested in the connections between sets of right-hand sides, we assume throughout this section that $\mathcal{B}=\mathbb{R}^{m}_{+}$ (or, equivalently, that each component of $\mathbf{b}$ is positive infinity). The removal of this assumption affects only \threfMC_Adjacent, which does not necessarily hold for MC-level sets that intersect an upper boundary plane of $\mathcal{B}$ .

Definition 2.

\thlabel

ivcurve Given $\bm{\beta}_{1}$ , $\bm{\beta}_{2}\in\mathcal{B}$ , a continuous function $d:[0,1]\to\mathcal{B}$ is a continuous isovalue curve from $\bm{\beta}_{1}$ to $\bm{\beta}_{2}$ if $d(0)=\bm{\beta}_{1}$ , $d(1)=\bm{\beta}_{2}$ , and $z(d(t))=z(\bm{\beta}_{1})$ for all $t\in[0,1]$ .

Given disjoint connected subsets $M_{1},M_{2}\subset[0,1]$ , we say that $M_{1}$ precedes $M_{2}$ in the ordering of $[0,1]$ if for any $t_{1}\in M_{1}$ , $t_{2}\in M_{2}$ , $t_{1}<t_{2}$ .

Definition 3.

\thlabel

Tstep For all ${\bm{\beta}}\in\mathcal{B}$ , define the MC-level set $T({{\bm{\beta}}})\coloneqq\left\{\bar{\bm{\beta}}\in\mathcal{B}\,|\right.$ there exists a continuous isovalue curve $d$ from ${\bm{\beta}}$ to $\left.\bar{\bm{\beta}}\right\}$ . For all ${\bm{\beta}\in}$ $\bar{\mathcal{B}}$ , define the MC-level lattice $C({\bm{\beta}})\coloneqq T({\bm{\beta}})\cap\mathbb{Z}^{m}_{+}$ .

Example LABEL:exExampleIP (continued).

In (EXIP), with $\mathcal{B}$ unbounded above, $T((1,1)^{\top})$ is the unbounded set $\left\{\bm{\beta}\,|\,\bm{\beta}_{1}\geq 1,\ 1\leq\bm{\beta}_{2}<2\right\}$ , and $C((1,1)^{\top})=\left\{(v,1)\,|\,v\in\mathbb{N}\right\}$ . ∎

Lemma 6.

\thlabel

easyiso Given $\bm{\beta}_{1}\in\mathcal{B}$ , $\bm{\beta}_{2}\in T(\bm{\beta}_{1})$ , there exists an isovalue curve $d^{\prime}:[0,1]\to\mathcal{B}$ from $\bm{\beta}_{1}$ to $\bm{\beta}_{2}$ such that $\lfloor d^{\prime}(\zeta)\rfloor=\lfloor d^{\prime}(\theta)\rfloor$ implies $\lfloor d^{\prime}(\zeta)\rfloor=\lfloor d^{\prime}(\eta)\rfloor$ for all $0\leq\zeta<\eta<\theta\leq 1$ - that is, $\lfloor d^{\prime}\rfloor$ takes on any given value for at most a single connected subset of $[0,1]$ .

Definition 4.

Given $\bm{\beta}_{1},\bm{\beta}_{2}\in\mathbb{Z}^{m}_{+}$ , $\bm{\beta}_{1}$ and $\bm{\beta}_{2}$ are adjacent if there exists $j\in\{1,...,m\}$ such that $\bm{\beta}_{1}-\bm{\beta}_{2}=\pm\mathbf{e}_{j}$ .

\thref

Csteppro shows that there exists a sequence of adjacent points in an MC-level lattice which connects any two of its members.

Proposition 12.

\thlabel

Csteppro Given ${\bm{\beta}}\in\bar{\mathcal{B}}$ and $\bm{\beta}_{1}$ , $\bm{\beta}_{2}\in C({\bm{\beta}})$ , there exists a finite sequence of points, $V=\left\{v_{1}=\bm{\beta}_{1},...,v_{r}=\bm{\beta}_{2}\right\}$ , such that for all $i\in\{1,...,r\}$ , $v_{i}\in C({\bm{\beta}})$ and for all $i\in\{1,...,r-1\}$ , $v_{i}$ and $v_{i+1}$ are adjacent.

Proof.

By \threfTstep and \threfeasyiso, there must exist a continuous isovalue curve $d^{\prime}:[0,1]\to\mathcal{B}$ from $\bm{\beta}_{1}$ to $\bm{\beta}_{2}$ for which $\lfloor d^{\prime}\rfloor$ takes on any given value for at most a single connected subset of $[0,1]$ . Let $\Gamma=\left\{\bm{\gamma}^{1}=\bm{\beta}_{1},...,\bm{\gamma}^{s}=\bm{\beta}_{2}\right\}$ be the ordered sequence of values taken on by $\lfloor d^{\prime}\rfloor$ , so that $\lfloor d(t_{i})\rfloor=\bm{\gamma}^{i}$ , $\lfloor d(t_{j})\rfloor=\bm{\gamma}^{j}$ , $t_{i},t_{j}\in[0,1]$ , and $i<j$ collectively imply $t_{i}<t_{j}$ . Let $\mathbf{M}=\{M_{1},...,M_{s}\}$ be the ordered sequence of connected subsets of $[0,1]$ corresponding to the members of $\Gamma$ - that is, for any $i\in\{1,\dots,s\}$ , $t\in M_{i}$ is equivalent to $\lfloor d^{\prime}(t)\rfloor=\bm{\gamma}^{i}$ . Denote the closure of $M_{i}$ as $\overline{M}_{i}$ , and define the singleton $\tau_{i}$ such that $\{\tau_{i}\}=\overline{M}_{i}\cap\overline{M}_{i+1}$ ; because the members of $\mathbf{M}$ are disjoint and ordered, and their union is $[0,1]$ , distinct $\tau_{i}$ will exist for each $i\in\{1,...,s-1\}$ . Note that either $\tau_{i}\in M_{i}$ or $\tau_{i}\in M_{i+1}$ , and that since $d^{\prime}$ is a continuous function over a bounded domain, each component of $d^{\prime}$ is also bounded, so that $\Gamma$ is finite. Further, since $d^{\prime}$ is continuous, $\|\bm{\gamma}^{i+1}-\bm{\gamma}^{i}\|_{\infty}=1$ for all $i\in\{1,...,s-1\}$ .

Suppose there exists $i\in\{1,...,s-1\}$ for which for some $j\in\{1,...,m\}$ , $\bm{\gamma}^{i+1}_{j}>\bm{\gamma}^{i}_{j}$ and for some $k\in\{1,...,m\}$ , $\bm{\gamma}^{i}_{k}>\bm{\gamma}^{i+1}_{k}$ . There are two possibilities:

Case 1: Suppose that both $M_{i}$ and $M_{i+1}$ include more than a single point. Since $d^{\prime}$ is continuous, there must exist $\epsilon>0$ such that for all $t\in(\tau_{i}-\epsilon,\tau_{i})$ , $\lfloor d^{\prime}(t)\rfloor=\bm{\gamma}^{i}$ and for all $t\in(\tau_{i},\tau_{i}+\epsilon)$ , $\lfloor d^{\prime}(t)\rfloor=\bm{\gamma}^{i+1}$ . For any $t$ such that $\lfloor d^{\prime}(t)\rfloor=\bm{\gamma}^{i}$ , we must have $(\bm{\gamma}^{i+1}-d^{\prime}(t))_{j}>0$ , so by the continuity of $d^{\prime}$ , we must have $d^{\prime}(\tau_{i})_{j}=\bm{\gamma}^{i+1}_{j}$ . Similarly, for any $t$ such that $\lfloor d^{\prime}(t)\rfloor=\bm{\gamma}^{i+1}$ , we must have $(\bm{\gamma}^{i}-d^{\prime}(t))_{k}>0$ , so that by the continuity of $d^{\prime}$ , we must have $d^{\prime}(\tau_{i})_{k}=\bm{\gamma}^{i}_{k}$ . However, this implies that $\tau_{i}\notin M_{i}\cup M_{i+1}$ , a contradiction.

Case 2: Suppose on the other hand that $M_{i}$ is a singleton; then $M_{i}=\{\tau_{i}\}$ . Observe that, because $M_{i}\cap M_{i+1}=\emptyset$ , if $M_{i+1}$ is a single point, $\overline{M_{i+1}}\cap\overline{M_{i}}=\emptyset$ . This contradicts the continuity of $d^{\prime}$ ; thus, $M_{i+1}$ contains more than a single point. Fix $\epsilon>0$ such that $(\tau_{i},\tau_{i}+\epsilon)\subseteq M_{i+1}$ . For any $\delta\in(0,\epsilon)$ , $d^{\prime}(\tau_{i}+\delta)_{j}\geq\lfloor d^{\prime}(\tau_{i}+\delta)_{j}\rfloor=\bm{\gamma}^{i+1}_{j}=\bm{\gamma}^{i}_{j}+1$ . By continuity, $d^{\prime}(\tau_{i})_{j}=\lim\limits_{t\to\tau_{i}^{+}}d^{\prime}(t)_{j}\geq\gamma^{i}_{j}+1=\lfloor d^{\prime}(\tau_{i})_{j}\rfloor+1>d^{\prime}(\tau_{i})_{j}$ , a contradiction. An analogous argument leads to a similar contradiction when $M_{i+1}$ is a singleton. Thus, we conclude that for all $i\in\{1,\dots,s\},$ either $\gamma^{i}\leq\gamma^{i+1}$ or $\gamma^{i}\geq\gamma^{i+1}$ .

Define $\hat{\bm{\gamma}}^{j}$ such that $\hat{\bm{\gamma}}^{j}_{k}=\mathbbm{1}_{k\leq j}\bm{\gamma}^{i}_{k}+\mathbbm{1}_{k>j}\bm{\gamma}^{i+1}_{k}$ for all $k\in\{1,...,m\}$ , and for all $j\in\{0,...,m\}$ . Then for all $j\in\{0,...,m\}$ , $\bm{\gamma}^{i}\leq\hat{\bm{\gamma}}^{j}\leq\bm{\gamma}^{i+1}$ or $\bm{\gamma}^{i}\geq\hat{\bm{\gamma}}^{j}\geq\bm{\gamma}^{i+1}$ , and for all $j\in\{0,...,m-1\}$ , either $\hat{\bm{\gamma}}^{j}-\hat{\bm{\gamma}}^{j+1}=\pm\mathbf{e}_{j}$ or $\hat{\bm{\gamma}}^{j}-\hat{\bm{\gamma}}^{j+1}=\mathbf{0}$ . By the monotonicity of the value function, $\hat{\bm{\gamma}}^{j}\in C(\bm{\beta})$ for all $j\in\{0,...,m\}$ . Inserting $\left\{\hat{\bm{\gamma}}^{1},...,\hat{\bm{\gamma}}^{m-1}\right\}$ in $\Gamma$ between $\bm{\gamma}^{i}$ and $\bm{\gamma}^{i+1}$ for each $i\in\{1,...,s-1\}$ , then removing sequentially adjacent duplicate values, will yield a sequence $V$ satisfying the conditions of the proposition statement. ∎

\thref

finseq shows an analogous result for any pair of points in an MC-level set.

Corollary 2.

\thlabel

finseq Given ${\bm{\beta}}\in\mathcal{B}$ , $\bm{\beta}_{a}$ and $\bm{\beta}_{b}\in T({\bm{\beta}})$ , there exists a finite sequence of points,
$\left\{\bm{\gamma}^{0}=\bm{\beta}_{a},...,\bm{\gamma}^{r}=\bm{\beta}_{b}\right\}$ , such that $\bm{\gamma}^{i}\in T({\bm{\beta}})$ and $|\bm{\gamma}^{i+1}-\bm{\gamma}^{i}|=\lambda_{i}\mathbf{e}_{j}$ for all $i$ , where $\lambda_{i}\in(0,1]$ for all $i$ and $\mathbf{e}_{j}$ is a unit vector for $j\in\{1,...,m\}$ .

Note that other than the steps necessary to move from $\bm{\beta}_{a}$ and $\bm{\beta}_{b}$ to the nearest isovalue lattice points, all the intermediate points in the above sequence may be made to be lattice points, as can be seen in Figure 1.

Refer to caption — Figure 1: An isovalue path from $\bm{\beta}_{a}$ to $\bm{\beta}_{b}$

Definition 5.

\thlabel

adjhc An $m$ -dimensional unit hypercube $H$ is anchored if all of its vertices are in $\mathbb{Z}^{m}$ . In particular, $H(\bm{\beta})$ , $\bm{\beta}\in\mathbb{Z}^{m}$ , is the anchored unit hypercube with $\bm{\beta}$ as its vertex with all components minimal.

Definition 6.

The open-ceiling unit hypercube anchored at $\bm{\beta}\in\bar{\mathcal{B}}$ is defined as $G(\bm{\beta})\coloneqq$ $\{\bar{\bm{\beta}}\in$ $\mathcal{B}\,|\,\lfloor\bar{\bm{\beta}}\rfloor=\bm{\beta}\}$ .

Remark 3.

Given an open-ceiling unit hypercube $G(\bm{\beta})$ , the closure of $G(\bm{\beta})$ is $H(\bm{\beta})$ .

Definition 7.

Two anchored $m-dimensional$ unit hypercubes $H_{1}$ and $H_{2}$ are adjacent if $H_{1}\cap H_{2}$ is an anchored unit hypercube of dimension $m-1$ .

\thref

MC_Adjacent shows that the closure of any MC-level set can be written as the union of a set of $m$ -dimensional unit hypercubes anchored at integer points.

Proposition 13.

\thlabel

MC_Adjacent Given $\bm{\beta}\in\mathcal{B}\subset\mathbb{R}^{m}$ , there exists a unique set $P$ of anchored unit hypercubes of dimension $m$ with integer-valued vertex coordinates such that $\bigcup\limits_{H\in P}H=\overline{T(\bm{\beta})}$ , the closure of $T(\bm{\beta})$ . Further, for all pairs $H_{1}$ , $H_{2}\,\in P$ , there exists a finite sequence $U=\{U_{1},...,U_{t}\}$ of hypercubes in $P$ such that $U_{1}=H_{1}$ , $U_{t}=H_{2}$ , and $U_{i}$ and $U_{i+1}$ are adjacent for all $i\in\{1,...,t-1\}$ .

Proof.

Fix $\bm{\beta}^{\prime}\in T(\bm{\beta})$ . Then the open-ceiling unit hypercube $G(\lfloor\bm{\beta}^{\prime}\rfloor)$ is a subset of $T(\bm{\beta})$ , and $\bm{\beta}^{\prime}\in G(\lfloor\bm{\beta}^{\prime}\rfloor)$ . As such, there exists a unique countable set $Q$ of $m$ -dimensional open-ceiling anchored unit hypercubes, $Q\coloneqq\{Q_{r}\}_{r\in R}$ , where $R$ is the index set for $Q$ , such that $T(\bm{\beta})=\bigcup\limits_{r\in R}Q_{r}$ - that is, for all $\bar{\bm{\beta}}\in T(\bm{\beta})$ , there exists $r\in R$ such that $Q_{r}=G(\lfloor\bar{\bm{\beta}}\rfloor)$ . Let $P=\{\overline{Q_{r}}\}_{r\in R}$ , and observe that $\overline{T(\bm{\beta})}=\bigcup\limits_{r\in R}\overline{Q_{r}}$ - that is, $P$ is a unique set of $m$ -dimensional anchored unit hypercubes whose union is the closure of $T(\bm{\beta})$ .

Next, fix $H_{1}$ , $H_{2}$ in $P$ . Let $\bm{\beta}_{1}$ and $\bm{\beta}_{2}$ anchor $H_{1}$ and $H_{2}$ , respectively. Let $V=\{v_{1}=\bm{\beta}_{1},...,v_{s}=\bm{\beta}_{2}\}$ be the sequence of adjacent points whose existence is guaranteed by \threfCsteppro given $\bm{\beta}_{1}$ and $\bm{\beta}_{2}$ as input points to connect, and define a finite sequence $U=\{H(v_{1}),...,H(v_{s})\}$ , where $H(v_{1})=H_{1}$ and $H(v_{s})=H_{2}$ . Since each of these points is in $T(\bm{\beta})$ , the $m$ -dimensional hypercube anchored at each point is a subset of $\overline{T(\bm{\beta})}$ and thus is an element of $P$ . Further, since $v_{i}-v_{i+1}$ is a unit vector for all $i$ , $H(v_{i})\cap H(v_{i+1})$ is a unit anchored hypercube of dimension $m-1$ , so $H(v_{i})$ and $H(v_{i+1})$ are adjacent for all $i\in\{1,...,s-1\}$ . ∎

\thref

MC_Adjacent shows that the closure of an MC-level set can be constructed using anchored unit hypercubes of dimension $m$ . In addition, given any two anchored unit hypercubes in that closure, we can find a finite sequence of adjacent anchored unit hypercubes connecting the two. In Figure 3, there is a sequence of adjacent dark squares between any two dark squares, since $T(\bm{\beta}_{1})=T(\bm{\beta}_{2})$ . On the other hand, in Figure 3, although the closures of $T(\bm{\beta}_{4})$ and $T(\bm{\beta}_{5})$ intersect, they do not actually share a point - and therefore there is no sequence of isovalue adjacent squares from $T(\bm{\beta}_{4})$ to $T(\bm{\beta}_{5})$ .

We next demonstrate some membership properties of MC-level sets based on level-set minimal vectors.

Corollary 3.

\thlabel

segment Given $\bar{\bm{\beta}}\in\mathcal{B}$ , for all $\hat{\bm{\beta}}\in\mathcal{B}$ such that $z(\bar{\bm{\beta}})=z(\hat{\bm{\beta}})$ and $\hat{\bm{\beta}}\geq\bar{\bm{\beta}}$ , we have $\hat{\bm{\beta}}\in T(\bar{\bm{\beta}})$ .

Proof.

By the monotonicity of $z$ , $z(\hat{\bm{\beta}})=z(\bar{\bm{\beta}})\leq z(\bm{\beta}^{\prime})\leq z(\hat{\bm{\beta}})$ , for all $\bm{\beta}^{\prime}\in\left\{\bm{\beta}\ |\ \bm{\beta}=\lambda\bar{\bm{\beta}}+(1-\lambda)\hat{\bm{\beta}},\lambda\in(0,1)\right\}$ because $\bm{\beta}^{\prime}\in(\bar{\bm{\beta}},\hat{\bm{\beta}})$ . As such, $d(t)\coloneqq t\bar{\bm{\beta}}+(1-t)\hat{\bm{\beta}}$ is a continuous isovalue curve from $\bar{\bm{\beta}}$ to $\hat{\bm{\beta}}$ , so $\hat{\bm{\beta}}\in T(\bar{\bm{\beta}})$ . ∎

Proposition 14.

\thlabel

LSMcor For any $\bar{\bm{\beta}}\in\mathcal{B}$ , $\bm{\beta}\in T(\bar{\bm{\beta}})$ if and only if $z(\bm{\beta})=z(\bar{\bm{\beta}})$ and there exists $\hat{\bm{\beta}}\in$ $\bar{\mathbf{B}}$ $\cap T(\bar{\bm{\beta}})$ such that $\hat{\bm{\beta}}\leq\bm{\beta}$ .

Corollary 4.

\thlabel

LSMseq Let $\bar{\bm{\beta}}\in\bar{\mathbf{B}}$ such that there exists $\hat{\bm{\beta}}\in\bar{\mathbf{B}}\cap T(\bar{\bm{\beta}})$ , $\hat{\bm{\beta}}\neq\bar{\bm{\beta}}$ . Then there exists a sequence $V=\{v_{1},...,v_{s}\}$ of distinct vectors in $\bar{\mathbf{B}}\cap T(\bar{\bm{\beta}})$ such that $\bar{\bm{\beta}}=v_{1}$ , $\hat{\bm{\beta}}=v_{s}$ , and for all $i\in\{1,...,s-1\}$ , there exists $\bm{\beta}_{i}\in T(\bar{\bm{\beta}})$ such that $v_{i}\lneq\bm{\beta}_{i}$ and $v_{i+1}\lneq\bm{\beta}_{i}$ .

\thref

LTstepdownt discusses the relationship between a sequence of right-hand sides when “stepping down” towards MC-level sets with smaller function value.

Remark 4.

\thlabel

optstat For any ${\bm{\beta}}\in\mathcal{B}$ , let $\mathbf{x}^{*}\in\mathrm{opt}({\bm{\beta}})$ . Then for all $\bar{\bm{\beta}}\in T({\bm{\beta}})$ such that $\bar{\bm{\beta}}\geq{\bm{\beta}}$ , $\mathbf{x}^{*}\in\mathrm{opt}(\bar{\bm{\beta}})$ .

Proposition 15.

\thlabel

LTstepdownt For any $\bar{\bm{\beta}}\in$ $\bar{\mathbf{B}}$ such that $z(\bar{\bm{\beta}})>0$ , given ${\mathbf{x}}^{*}\in\mathrm{opt}(\bar{\bm{\beta}})$ and $\bm{\beta}\in T(\bar{\bm{\beta}})$ such that $\bar{\bm{\beta}}\leq\bm{\beta}$ , then for all $j$ such that ${x}^{*}_{j}>0$ and all $t\leq{x}^{*}_{j}$ , $\bm{\beta}-t\mathbf{a}_{j}\in T(\bar{\bm{\beta}}-t\mathbf{a}_{j})$ .

Proof.

Note that if $\bm{\beta}=\bar{\bm{\beta}}$ the result holds trivially. Suppose there exists $\hat{\bm{\beta}}\in T(\bar{{\bm{\beta}}})$ , $\bar{\bm{\beta}}\lneq\hat{\bm{\beta}}$ , such that there exists $t:\,1\leq t\leq{x}^{*}_{j}$ for which $\hat{\bm{\beta}}-t\mathbf{a}_{j}\notin T(\bar{\bm{\beta}}-t\mathbf{a}_{j})$ . Then there exists $\bm{\pi}\in\bar{\mathbf{B}}$ such that $\bar{\bm{\beta}}-t\mathbf{a}_{j}\lneq\bm{\pi}\leq\hat{\bm{\beta}}-t\mathbf{a}_{j}$ and $z(\bar{\bm{\beta}}-t\mathbf{a}_{j})<z(\bm{\pi})=z(\hat{\bm{\beta}}-t\mathbf{a}_{j})$ . Let $\hat{\mathbf{x}}\in\mathrm{opt}(\bm{\pi})$ . Then $z(\hat{\bm{\beta}})\geq z(\bm{\pi}+t\mathbf{a}_{j})\geq z(\bm{\pi})+tc_{j}$ . However, by \threfequal and \threfdown, $z(\bar{\bm{\beta}}-t\mathbf{a}_{j})=z(\bar{\bm{\beta}})-tc_{j}=z(\hat{\bm{\beta}})-tc_{j}$ , a contradiction since we have now claimed that $z(\hat{\bm{\beta}})-tc_{j}<z(\bm{\pi})\leq z(\hat{\bm{\beta}})-tc_{j}$ . ∎

Example LABEL:exExampleIP (continued).

In (EXIP), with $\mathcal{B}$ unbounded above, $(1,1)^{\top}\in\bar{\mathbf{B}}_{6}$ and $z((1,1)^{\top})=3$ , with the unique optimal solution $\mathbf{e}_{4}$ . Further, $(2,1)^{\top},(3,1)^{\top}\in T((1,1)^{\top})$ . So by \threfLTstepdownt, $(1,0)^{\top},(2,0)^{\top}\in T((0,0)^{\top})$ . ∎

\thref

bk=b indicates that if, for any $k\in\{1,...,n\}$ , $\bar{\mathbf{B}}_{k}=\bar{\mathcal{B}}$ , then for all $k^{\prime}\geq k$ , all MC-level sets will be unit hypercubes.

Proposition 16.

\thlabel

bk=b If there exists $k\in\{1,\dots,n\}$ such that $\bar{\mathbf{B}}_{k}=\bar{\mathcal{B}}$ , then for all $\hat{k}\geq k,\hat{k}\in\{1,\dots,n\}$ , $\bar{\mathbf{B}}_{\hat{k}}=\bar{\mathcal{B}}$ .

Acknowledgments

The authors would like to thank the referee and associate editor for their thorough and valuable input. The authors would also like to thank Eric Antley, David Mildebrath, Saumya Sinha, and Silviya Valeva of Rice University for their helpful comments. This research was supported in part by National Science Foundation, USA grants CMMI-1826323 and CMMI-1933373.

References

Ahmed et al. [2004] S. Ahmed, M. Tawarmalani, and N. V. Sahinidis. A finite branch-and-bound algorithm for two-stage stochastic integer programs. Mathematical Programming, 100(2):355–377, 2004.
Ajayi et al. [2020] T. Ajayi, C. Thomas, and A. J. Schaefer. The gap function: Evaluating integer programming models over multiple right-hand sides. Operations Research (To appear), 2020.
Basu et al. [2021] A. Basu, C. T. Ryan, and S. Sankaranarayanan. Mixed-integer bilevel representability. Mathematical Programming, 185:163–197, 2021.
Blair [1995] C. E. Blair. A closed-form representation of mixed-integer program value functions. Mathematical Programming, 71(2):127–136, 1995.
Blair and Jeroslow [1977] C. E. Blair and R. G. Jeroslow. The value function of a mixed integer program: I. Discrete Mathematics, 19(2):121–138, 1977.
Blair and Jeroslow [1982] C. E. Blair and R. G. Jeroslow. The value function of an integer program. Mathematical Programming, 23(1):237–273, 1982.
Gilmore and Gomory [1966] P. C. Gilmore and R. E. Gomory. The theory and computation of knapsack functions. Operations Research, 14(6):1045–1074, 1966.
Kılınç-Karzan et al. [2009] F. Kılınç-Karzan, A. Toriello, S. Ahmed, G. Nemhauser, and M. Savelsbergh. Approximating the stability region for binary mixed-integer programs. Operations Research Letters, 37(4):250–254, 2009.
Kong et al. [2006] N. Kong, A.J. Schaefer, and B. Hunsaker. Two-stage integer programs with stochastic right-hand sides: A superadditive dual approach. Mathematical Programming, 108(2):275–296, Sep 2006.
Llewellyn and Ryan [1993] D. C. Llewellyn and J. Ryan. A primal dual integer programming algorithm. Discrete Applied Mathematics, 45(3):261 – 275, 1993.
Lozano and Smith [2017] L. Lozano and J. C. Smith. A value-function-based exact approach for the bilevel mixed-integer programming problem. Operations Research, 65(3):768–786, 2017.
Nemhauser and Wolsey [1988] G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Wiley-Interscience. John Wiley & Sons, 1988.
Özaltın et al. [2012] O. Y. Özaltın, O. A. Prokopyev, and A. J. Schaefer. Two-stage quadratic integer programs with stochastic right-hand sides. Mathematical Programming, 133(1):121–158, Jun 2012.
Ralphs and Hassanzadeh [2014] T. K. Ralphs and A. Hassanzadeh. On the value function of a mixed integer linear optimization problem and an algorithm for its construction. COR $@$ L Technical Report 14T–004, 2014.
Schultz et al. [1998] R. Schultz, L. Stougie, and M. H. Van Der Vlerk. Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis. Mathematical Programming, 83(1-3):229–252, 1998.
Tavaslıoğlu et al. [2019] O. Tavaslıoğlu, O. A. Prokopyev, and A. J. Schaefer. Solving stochastic and bilevel mixed-integer programs via a generalized value function. Operations Research, 67(6):1659–1677, 2019.
Trapp and Prokopyev [2015] A. C. Trapp and O. A. Prokopyev. A note on constraint aggregation and value functions for two-stage stochastic integer programs. Discrete Optimization, 15:37–45, 2015.
Trapp et al. [2013] A. C. Trapp, O. A. Prokopyev, and A. J. Schaefer. On a level-set characterization of the value function of an integer program and its application to stochastic programming. Operations Research, 61(2):498–511, 2013.
Wang and Xu [2017] L. Wang and P. Xu. The watermelon algorithm for the bilevel integer linear programming problem. SIAM Journal on Optimization, 27(3):1403–1430, 2017.
Williams [1996] H. P. Williams. Constructing the value function for an integer linear programme over a cone. Computational Optimization and Applications, 6(1):15–26, 1996.
Wolsey [1981] L. A. Wolsey. Integer programming duality: Price functions and sensitivity analysis. Mathematical Programming, 20(1):173–195, 1981.

Appendix

Omitted Proofs

Lemma LABEL:equal. Given $k\in\{1,...,n\}$ , for all $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ and all $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bm{\beta})$ , $\sum_{j=1}^{k}\mathbf{a}_{j}{x}^{*}_{j}=\bm{\beta}$ .

Proof.

Suppose $\sum_{j=1}^{k}\mathbf{a}_{j}{x}^{*}_{j}\lneq\bm{\beta}$ . Then $z_{k}(\sum_{j=1}^{k}\mathbf{a}_{j}{x}^{*}_{j})=z_{k}(\bm{\beta})$ , which contradicts $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ . ∎

Proposition LABEL:LSMiter. Let $\bm{\beta}\in\bar{\mathbf{B}}_{k-1}$ . If for all $\bar{\bm{\beta}}\lneq\bm{\beta}$ and all $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\bar{\bm{\beta}})$ , ${x}^{*}_{k}=0$ , then $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ .

Proof.

Let $\bm{\beta}\in S_{k}(\alpha)$ . Suppose $\bm{\beta}\notin\bar{\mathbf{B}}_{k}$ . Then there exists $\hat{\bm{\beta}}\lneq\bm{\beta}$ such that $\hat{\bm{\beta}}\in S_{k}(\alpha)$ . Let ${\mathbf{x}^{*}}\in\mathrm{opt}_{k}(\hat{\bm{\beta}})$ , with ${x}^{*}_{k}=0$ . Then by \threfschaeferoriginal, $\hat{\bm{\beta}}\in S_{k-1}(\alpha)$ , which implies $z_{k-1}(\hat{\bm{\beta}})=\alpha$ . However, because $z_{k}({\bm{\beta}})=\alpha$ , by \threfnondecreasingbetweeniterations, we have $z_{k-1}(\bm{\beta})\leq\alpha$ . Because $z_{k-1}$ is nondecreasing, we must have $z_{k-1}(\bm{\beta})=\alpha$ , so that $\bm{\beta}\notin\bar{\mathbf{B}}_{k-1}$ , a contradiction. ∎

Proposition LABEL:LSMlinind. If $\bm{\beta}\notin\bar{\mathbf{B}}_{k-1}$ , $\mathbf{a}_{1},\dots,\mathbf{a}_{k}$ are linearly independent, and $\bm{\beta}$ and $\mathbf{a}_{k}$ are linearly independent, then for all $t\in\mathbb{Z}_{+}$ such that $\bm{\beta}+t\mathbf{a}_{k}\in\mathcal{B}$ , $\bm{\beta}+t\mathbf{a}_{k}\notin\bar{\mathbf{B}}_{k}$ .

Proof.

Suppose $\bm{\beta}+t\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}.$ Because $\bm{\beta}\not\in\bar{\mathbf{B}}_{k-1}$ , there exists $\bm{\pi}\lneq\bm{\beta}$ such that $z_{k-1}(\bm{\beta})=z_{k-1}(\bm{\pi})$ . Let $x^{1}\in\mathrm{opt}_{k-1}(\bm{\pi})$ , then $(x^{1}_{1},\dots,x^{1}_{k-1},t)^{\top}$ is a feasible solution for IP ${}_{k}(\bm{\beta}+t\mathbf{a}_{k})$ . Let $\mathbf{x}^{2}\in\mathrm{opt}_{k}(\bm{\beta}+t\mathbf{a}_{k})$ ; then by \threfequal, we have $\sum\limits_{j=1}^{k}\mathbf{a}_{j}x^{2}_{j}=\bm{\beta}+t\mathbf{a}_{k}$ , and because $\mathbf{a}_{1},\dots\mathbf{a}_{k}$ are linearly independent, $x^{2}_{k}=t$ and $\sum\limits_{j=1}^{k-1}\mathbf{a}_{j}x^{2}_{j}=\bm{\beta}$ .

The vector $(x^{2}_{1},\dots,x^{2}_{k-1})^{\top}$ is feasible for IP ${}_{k-1}(\bm{\beta}$ ); hence $\sum\limits_{j=1}^{k-1}c_{j}x^{2}_{j}\leq\sum\limits_{j=1}^{k-1}c_{j}x_{j}^{1}$ . This implies that $\sum\limits_{j=1}^{k}c_{j}x^{2}_{j}=\sum\limits_{j=1}^{k-1}c_{j}x^{2}_{j}+c_{k}t\leq\sum\limits_{j=1}^{k-1}c_{j}x^{1}_{j}+tc_{k}$ . Because $\mathbf{x}^{2}\in\mathrm{opt}_{k}(\bm{\beta}+t\mathbf{a}_{k})$ , and $(x^{1}_{1},\dots,x^{1}_{k-1},t)$ is feasible for IP ${}_{k}(\bm{\beta}+t\mathbf{a}_{k})$ , $(x^{1}_{1},\dots,x^{1}_{k-1},t)\in\mathrm{opt}_{k}(\bm{\beta}+t\mathbf{a}_{k})$ . However, $\sum\limits_{j=1}^{k-1}\mathbf{a}_{j}x^{1}_{j}+t\mathbf{a}_{k}=\bm{\pi}+t\mathbf{a}_{k}\lneq\bm{\beta}+t\mathbf{a}_{k},$ which contradicts $\bm{\beta}+t\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ . Hence, $\bm{\beta}+t\mathbf{a}_{k}\not\in\bar{\mathbf{B}}_{k}$ . ∎

Proposition LABEL:anotinB. Let $\bm{\beta}\in\bar{\mathbf{B}}_{k}$ . If $\mathbf{a}_{j}\notin\bar{\mathbf{B}}_{k}$ , then for all ${\mathbf{x}^{*}}\in\mathrm{opt}_{k}(\bm{\beta})$ , ${x}^{*}_{j}=0$ .

Proof.

Suppose first that ${\mathbf{x}^{*}}=\mathbf{e}_{j}$ . Then by \threfequal, $\mathbf{a}_{j}\in\bar{\mathbf{B}}_{k}$ , a contradiction.
Suppose on the other hand that $\|{\mathbf{x}^{*}}\|_{1}\geq 2$ , with ${x}^{*}_{j}\neq 0$ . Let $\hat{\mathbf{x}}=\mathbf{e}_{j}\lneq{\mathbf{x}^{*}}$ . Then by \threfdown, $\sum_{i=1}^{k}\mathbf{a}_{i}\hat{x}_{i}=\mathbf{a}_{j}\in\bar{\mathbf{B}}_{k}$ , also a contradiction. ∎

Corollary LABEL:relationship. $\bar{\mathbf{B}}_{k}\subseteq\left\{\bm{\beta}\in\bar{\mathcal{B}}\,|\,\bm{\beta}=\hat{\bm{\beta}}+t\mathbf{a}_{k},\hat{\bm{\beta}}\in\bar{\mathbf{B}}_{k-1},t\in\mathbb{Z}_{+}\right\}$ .

Proof.

Suppose $\bar{\bm{\beta}}\in\bar{\mathbf{B}}_{k}$ , then \threfequal implies that there exists ${\mathbf{x}^{*}}\in\mathrm{opt}_{k}(\bar{\bm{\beta}})$ such that $\sum\limits_{j=1}^{k}\mathbf{a}_{j}{x}^{*}_{j}=\bar{\bm{\beta}}.$ By \threfschaefer, $\bar{\bm{\beta}}-\mathbf{a}_{k}{x}^{*}_{k}\in\bar{\mathbf{B}}_{k-1}$ ; hence, $\bar{\bm{\beta}}\in\left\{\bm{\beta}\in\bar{\mathcal{B}}\,|\,\bm{\beta}=\hat{\bm{\beta}}+t\mathbf{a}_{k},\hat{\bm{\beta}}\in\bar{\mathbf{B}}_{k-1},t\in\mathbb{Z}_{+}\right\}$ . ∎

Lemma LABEL:LSMkton. Suppose $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ and $z_{k}(\mathbf{a}_{k})=c_{k}$ , for some $k\in\{1,\dots,n\}$ . Further suppose that for all $\hat{k}\in\mathbb{Z}_{+}$ such that $k<\hat{k}\leq n$ , we have $\mathbf{a}_{k}-\mathbf{a}_{\hat{k}}\not\in\mathcal{B}$ . Then, $z_{n}(\mathbf{a}_{k})=c_{k}$ and $\mathbf{a}_{k}\in\bar{\mathbf{B}}$ .

Proof.

Suppose $z_{n}(\mathbf{a}_{k})\neq c_{k}$ . Then $\mathbf{e}_{k}\notin\mathrm{opt}_{n}(\mathbf{a}_{k})$ and there exists $\mathbf{x}^{*}\in\mathrm{opt}_{n}(\mathbf{a}_{k})$ such that $\sum_{j=1}^{n}\mathbf{a}_{j}x^{*}_{j}\leq\mathbf{a}_{k},\,x^{*}_{k}=0$ . Therefore, there exists $\hat{k}\neq k$ such that $x^{*}_{\hat{k}}\neq 0$ , then $\mathbf{a}_{\hat{k}}\leq\mathbf{a}_{k}$ , which contradicts $\mathbf{a}_{k}-\mathbf{a}_{\hat{k}}\notin\mathcal{B}$ .

Suppose $\mathbf{a}_{k}\notin\bar{\mathbf{B}}$ . Then there exists $\bm{\pi}\lneq\mathbf{a}_{k}$ such that $z_{n}(\bm{\pi})=z_{n}(\mathbf{a}_{k})=c_{k}$ . Since there does not exist $\hat{k}\in\{k+1,...,n\}$ such that $\mathbf{a}_{\hat{k}}\leq\mathbf{a}_{k}$ , it follows that there does not exist $\hat{k}\in\{k+1,...,n\}$ such that $\mathbf{a}_{\hat{k}}\leq\bm{\pi}$ , and this indicates $z_{k}(\bm{\pi})=c_{k}$ , which is a contradiction of the assumption that $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ . ∎

Proposition LABEL:altvalue. Exactly one of the following holds:

(i)

$z_{k-1}(\mathbf{a}_{k})<c_{k}$ . Then $z_{k}(\mathbf{a}_{k})=c_{k}$ and $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ .
(ii)

$z_{k-1}(\mathbf{a}_{k})=c_{k}$ . Then $z_{k}(\mathbf{a}_{k})=c_{k}$ .
(iii)

$z_{k-1}(\mathbf{a}_{k})>c_{k}$ . Then $z_{k}(\mathbf{a}_{k})=z_{k-1}(\mathbf{a}_{k})$ .

Thus, $z_{k}(\mathbf{a}_{k})=\max\{z_{k-1}(\mathbf{a}_{k}),c_{k}\}$ . In addition, if $z_{k-1}(\mathbf{a}_{k})\geq c_{k}$ , $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ if and only if $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k-1}$ .

Proof.

(i)

Suppose $z_{k-1}(\mathbf{a}_{k})<c_{k}$ . The vector $\mathbf{e}_{k}$ is feasible for IP ${}_{k}(\mathbf{a}_{k})$ with value $c_{k}$ . Suppose there exists $\mathbf{x}^{*}\in\mathrm{opt}_{k}(\mathbf{a}_{k})$ such that $\sum_{j=1}^{k}c_{j}x_{j}^{*}>c_{k}$ . Then $\mathbf{x}_{k}^{*}=0$ , contradicting $z_{k-1}(\mathbf{a}_{k})<c_{k}$ . Similarly, there cannot exist $\bm{\beta}\lneq\mathbf{a}_{k}$ such that $z_{k}(\bm{\beta})\geq c_{k}$ , so $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ .
(ii)

Suppose $z_{k-1}(\mathbf{a}_{k})=c_{k}$ . Then by analogous reasoning to (i), $z_{k}(\mathbf{a}_{k})=c_{k}$ .
(iii)

Suppose $z_{k-1}(\mathbf{a}_{k})>c_{k}$ . Then by analogous reasoning to (i), $z_{k}(\mathbf{a}_{k})=z_{k-1}(\mathbf{a}_{k})$ .

Next assume $z_{k-1}(\mathbf{a}_{k})\geq c_{k}$ . If $\mathbf{a}_{k}\notin\bar{\mathbf{B}}_{k-1}$ , then $\mathbf{a}_{k}\notin\bar{\mathbf{B}}_{k}$ . On the other hand, if $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k-1}$ , by analogous reasoning to (i), there cannot exist $\bm{\beta}\lneq\mathbf{a}_{k}$ such that $z_{k}(\bm{\beta})\geq z_{k}(\mathbf{a}_{k})$ , so $\mathbf{a}_{k}\in\bar{\mathbf{B}}_{k}$ . ∎

Lemma LABEL:easyiso. Given $\bm{\beta}_{1}\in\mathcal{B}$ , $\bm{\beta}_{2}\in T(\bm{\beta}_{1})$ , there exists an isovalue curve $d^{\prime}:[0,1]\to\mathcal{B}$ from $\bm{\beta}_{1}$ to $\bm{\beta}_{2}$ such that $\lfloor d^{\prime}(\zeta)\rfloor=\lfloor d^{\prime}(\theta)\rfloor$ implies $\lfloor d^{\prime}(\zeta)\rfloor=\lfloor d^{\prime}(\eta)\rfloor$ for all $0\leq\zeta<\eta<\theta\leq 1$ - that is, $\lfloor d^{\prime}\rfloor$ takes on any given value for at most a single connected subset of $[0,1]$ .

Proof.

Given a continuous isovalue curve $d:[0,1]\to\mathcal{B}$ from $\bm{\beta}_{1}$ to $\bm{\beta}_{2}$ , we define the set $\mathcal{S}(d)$ as the set of values in $\bar{\mathcal{B}}$ which are given by $\lfloor d\rfloor$ for multiple, non-connected subsets of $[0,1]$ . In particular, $\mathcal{S}(d)=\left\{\bm{\gamma}^{1},...,\bm{\gamma}^{r}\right\}\subset\bar{\mathcal{B}}$ , so that for all $\bm{\gamma}^{i}\in\mathcal{S}(d)$ , there exist $0\leq\zeta^{i}<\eta^{i}<\theta^{i}\leq 1$ for which $\lfloor d(\zeta^{i})\rfloor=\lfloor d(\theta^{i})\rfloor=\bm{\gamma}^{i}\neq\lfloor d(\eta^{i})\rfloor$ , and so that for any $\bm{\gamma}\in T(\bm{\beta}_{1})$ but not in $\mathcal{S}(d)$ , for any $0\leq\zeta<\eta<\theta\leq 1$ , $\lfloor d(\zeta)\rfloor=\lfloor d(\theta)\rfloor=\bm{\gamma}$ implies $\lfloor d(\eta)\rfloor=\bm{\gamma}$ . Note that since any particular continuous isovalue curve $d$ is continuous and has a bounded domain, each component of $d$ is also bounded, so $\mathcal{S}(d)$ is finite. Let $\bar{d}:[0,1]\to\mathcal{B}$ be a continuous isovalue curve from $\bm{\beta}_{1}$ to $\bm{\beta}_{2}$ such that $|\mathcal{S}(\bar{d})|$ is minimized. Suppose the statement does not hold; then $|\mathcal{S}(\bar{d})|>0$ . Without loss of generality, let $\zeta^{1}$ be in the first connected subset of $[0,1]$ for which $\lfloor\bar{d}\rfloor=\bm{\gamma}^{1}$ and let $\theta^{1}$ be in the last connected subset of $[0,1]$ for which $\lfloor\bar{d}\rfloor=\bm{\gamma}^{1}$ . Note however that $\left\{\bm{\beta}^{\prime}\in\mathcal{B}\,|\,\lfloor\bm{\beta}^{\prime}\rfloor=\bm{\gamma}^{1}\right\}$ is a convex set over which $z$ is constant, and $\{\bar{d}(\theta^{1}),\bar{d}(\zeta^{1})\}\subset T(\beta_{1})$ , so the line segment from $\bar{d}(\zeta^{1})$ to $\bar{d}(\theta^{1})$ must be a subset of $T(\bm{\beta}_{1})$ . Thus, consider $\hat{d}:[0,1]\to\mathcal{B}$ :

\hat{d}(t)\coloneqq\left\{\begin{array}[]{ll}\bar{d}(t)&t\in[0,1]\setminus[\zeta^{1},\theta^{1}]\\ \frac{t-\zeta^{1}}{\theta^{1}-\zeta^{1}}\bar{d}(\zeta^{1})+\frac{\theta^{1}-t}{\theta^{1}-\zeta^{1}}\bar{d}(\theta^{1})&t\in[\zeta^{1},\theta^{1}]\end{array}\right..

Observe that $\hat{d}$ as defined is a continuous isovalue curve from $\bm{\beta}_{1}$ to $\bm{\beta}_{2}$ and $\mathcal{S}(\hat{d})$ has at most $|\mathcal{S}(\bar{d})|-1$ members, a contradiction, so there exists $d^{\prime}$ for which $\mathcal{S}(d^{\prime})=\emptyset$ . ∎

Corollary LABEL:finseq. Given ${\bm{\beta}}\in\mathcal{B}$ , $\bm{\beta}_{a}$ and $\bm{\beta}_{b}\in T({\bm{\beta}})$ , there exists a finite sequence of points,
$\left\{\bm{\gamma}^{0}=\bm{\beta}_{a},...,\bm{\gamma}^{r}=\bm{\beta}_{b}\right\}$ , such that $\bm{\gamma}^{i}\in T({\bm{\beta}})$ and $|\bm{\gamma}^{i+1}-\bm{\gamma}^{i}|=\lambda_{i}\mathbf{e}_{j}$ for all $i$ , where $\lambda_{i}\in(0,1]$ for all $i$ and $\mathbf{e}_{j}$ is a unit vector for $j\in\{1,...,m\}$ .

Proof.

Note that $\lfloor\bm{\beta}_{a}\rfloor$ and $\lfloor\bm{\beta}_{b}\rfloor$ are both in $T(\bm{\beta})$ . If $s$ and $t$ are the number of fractional components of $\bm{\beta}_{a}$ and $\bm{\beta}_{b}$ , respectively, then the first $s$ members of the sequence after $\bm{\beta}_{a}$ can be defined as the component by component rounding down of $\bm{\beta}_{a}$ , so that $\bm{\gamma}^{s}=\lfloor{\bm{\beta}_{a}}\rfloor$ . The same can be done for the last $t$ members of the sequence, so that $\bm{\gamma}^{r-t}=\lfloor\bm{\beta}_{b}\rfloor$ . These first $s$ and final $t$ terms are all in $T(\bm{\beta})$ , and there is a finite number of them. Then by \threfCsteppro, there exists a finite sequence from $\bm{\gamma}^{s}$ to $\bm{\gamma}^{r-t}$ in $C(\bm{\beta})$ , so prepending the first $s$ terms and appending the final $t$ terms to that sequence will yield the desired result. ∎

Proposition LABEL:LSMcor. For any $\bar{\bm{\beta}}\in\mathcal{B}$ , $\bm{\beta}\in T(\bar{\bm{\beta}})$ if and only if $z(\bm{\beta})=z(\bar{\bm{\beta}})$ and there exists $\hat{\bm{\beta}}\in$ $\bar{\mathbf{B}}$ $\cap T(\bar{\bm{\beta}})$ such that $\hat{\bm{\beta}}\leq\bm{\beta}$ .

Proof.

By definition of $T(\bm{\beta})$ , if $z(\bm{\beta})\neq z(\bar{\bm{\beta}})$ , then $\bm{\beta}\not\in T(\bar{\bm{\beta}})$ . Suppose $z(\bm{\beta})=z(\bar{\bm{\beta}})$ but there does not exist level-set-minimal $\hat{\bm{\beta}}\leq\bm{\beta}$ in the same MC-level set as $\bar{\bm{\beta}}$ . Note that there must exist at least one $\tilde{\bm{\beta}}\leq\bm{\beta}$ which is level-set-minimal and for which $\tilde{\bm{\beta}}\in T(\bm{\beta})$ . However, there is no continuous curve from $\bar{\bm{\beta}}$ to any such $\tilde{\bm{\beta}}$ ; thus, because there is a continuous curve from $\tilde{\bm{\beta}}$ to $\bm{\beta}$ , there cannot be a continuous curve from $\bar{\bm{\beta}}$ to $\bm{\beta}$ , i.e., $\bm{\beta}\not\in T(\bar{\bm{\beta}})$ . On the other hand, suppose there does exist level-set-minimal $\hat{\bm{\beta}}\leq\bm{\beta}$ in the same MC-level set as $\bar{\bm{\beta}}$ . Then there exists a continuous curve from $\bar{\bm{\beta}}$ to $\hat{\bm{\beta}}$ , and from $\hat{\bm{\beta}}$ to $\bm{\beta}$ , so that there exists a single continuous curve from $\bar{\bm{\beta}}$ to $\bm{\beta}$ , and $\bm{\beta}\in T(\bar{\bm{\beta}})$ . ∎

Corollary LABEL:LSMseq. Let $\bar{\bm{\beta}}\in\bar{\mathbf{B}}$ such that there exists $\hat{\bm{\beta}}\in\bar{\mathbf{B}}\cap T(\bar{\bm{\beta}})$ , $\hat{\bm{\beta}}\neq\bar{\bm{\beta}}$ . Then there exists a sequence $V=\{v_{1},...,v_{s}\}$ of distinct vectors in $\bar{\mathbf{B}}\cap T(\bar{\bm{\beta}})$ such that $\bar{\bm{\beta}}=v_{1}$ , $\hat{\bm{\beta}}=v_{s}$ , and for all $i\in\{1,...,s-1\}$ , there exists $\bm{\beta}_{i}\in T(\bar{\bm{\beta}})$ such that $v_{i}\lneq\bm{\beta}_{i}$ and $v_{i+1}\lneq\bm{\beta}_{i}$ .

Proof.

Let $U=\{u_{1},...,u_{t}\}$ be the finite sequence of points in $T(\bar{\bm{\beta}})$ from $\bar{\bm{\beta}}$ to $\hat{\bm{\beta}}$ whose existence is guaranteed by \threfCsteppro. Set $V=\{\bar{\bm{\beta}}\}$ initially, and set $\tilde{\bm{\beta}}=\bar{\bm{\beta}}$ . Let $u_{i}$ be the last member in the ordering of $U$ such that $\tilde{\bm{\beta}}\lneq u_{i}$ . Then $u_{i+1}=u_{i}-\mathbf{e}_{j}$ for some component $j$ , since each member of $U$ differs from the next by a single unit vector, and we must have $u_{i+1}\lneq u_{i}$ since we have assumed that $u_{i}$ is the final vector in the ordering of $U$ for which $\tilde{\bm{\beta}}\lneq u_{i}$ . By \threfLSMcor, there must exist $\bm{\beta}^{\prime}\in\bar{\mathbf{B}}_{n}\cap T(\bar{\bm{\beta}})$ such that $\bm{\beta}^{\prime}\leq u_{i+1}$ . Further, we also have $\bm{\beta}^{\prime}\lneq u_{i}$ , so we can append $\bm{\beta}^{\prime}$ to $V$ . Then update $\tilde{\bm{\beta}}=\bm{\beta}^{\prime}$ and repeat until $\bm{\beta}^{\prime}=\hat{\bm{\beta}}$ is added to $V$ . Since $U$ is finite, the process will complete in finitely many steps. ∎

Proposition LABEL:bk=b. If there exists $k\in\{1,\dots,n\}$ such that $\bar{\mathbf{B}}_{k}=\bar{\mathcal{B}}$ , then for all $\hat{k}\geq k,\hat{k}\in\{1,\dots,n\}$ , $\bar{\mathbf{B}}_{\hat{k}}=\bar{\mathcal{B}}$ .

Proof.

Fix $\hat{k}$ such that $k<\hat{k}\leq n$ (if $k=n$ , the result is immediate). Suppose there exists $\bm{\beta}\in\bar{\mathcal{B}}$ such that $\bm{\beta}\notin\bar{\mathbf{B}}_{\hat{k}}$ . Then there must exist $\bm{\pi}\lneq\bm{\beta}$ such that $z_{\hat{k}}(\bm{\pi})=z_{\hat{k}}(\bm{\beta})$ . By \threfelementary, we have

z_{\hat{k}}(\bm{\pi})=z_{\hat{k}}(\bm{\beta})=z_{\hat{k}}(\bm{\pi}+\bm{\beta}-\bm{\pi})\geq z_{\hat{k}}(\bm{\pi})+z_{\hat{k}}(\bm{\beta}-\bm{\pi}).

Therefore, $z_{\hat{k}}(\bm{\beta}-\bm{\pi})=0$ . By \threfnotOptimal, $0\leq z_{k}(\bm{\beta}-\bm{\pi})\leq z_{\hat{k}}(\bm{\beta}-\bm{\pi})=0$ ; hence, $\bm{\beta}-\bm{\pi}\not\in\bar{\mathbf{B}}_{k}$ , a contradiction. As such, $\bar{\mathbf{B}}_{\hat{k}}=\bar{\mathcal{B}}$ . ∎