A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization

Historically, research in mathematical optimization, which is arguably the most widely applied theoretical and methodological framework for solving optimization problems, has been primarily focused on “idealized” models aimed at informing the decision process of a single decision maker (DM) facing the problem of making a single set of decisions at a single point in time under perfect information. Techniques for this idealized case are now well developed, with efficient implementations widely available in off-the-shelf software.

In contrast, most real-world applications involve multiple DMs, and decisions must be made at multiple points in time under uncertainty. To allow for this additional complexity, a number of more sophisticated modeling frameworks have been developed, including multistage and multilevel optimization. In line with the recent optimization literature, we use the term multistage optimization to denote the decision process of a single DM over multiple time periods with an objective that factors in the (expected) impact at future stages of the decisions taken at the current stage. With the term multilevel optimization, on the other hand, we refer to game-theoretic decision processes in which multiple DMs with selfish objectives make decisions in turn, competing to optimize their own individual outcomes in the context of settings such as, e.g., economic markets.

Because the distinction between multistage and multilevel optimization problems appears substantial from a modeling perspective, their development has been undertaken independently by different research communities. Indeed, multistage problems have arisen out of the necessity to account for stochasticity, which is done by explicitly including multiple decision stages in between each of which the value of a random variable is realized. Knowledge of the precise values of the quantities that were unknown at earlier stages allows for so-called recourse decisions to be made in later stages in order to correct possible mis-steps taken due to the lack of precise information. On the other hand, multilevel optimization has been developed primarily to model multi-round games (technically known as finite, extensive form games with perfect information in the general case and Stackelberg games in the case of two rounds) in which the decision (or strategy) of a given player at a given round must take into account the reactions of other players in future rounds.

Despite these distinctions, these classes of problems share an important common structure from a mathematical and methodological perspective that makes considering them in a single, unifying framework attractive. It is not difficult to understand the source of this common structure—from the standpoint of an individual DM, the complexity of the decision process comes from uncertainty about the future. From an analytical perspective, the methods we use for dealing with the uncertainty arising from a lack of knowledge of the precise values of input parameters to later-stage decision problems can also be used to address the uncertainty arising from a lack of knowledge of the future actions of another self-interested player. In fact, one way of viewing the outcome of a random variable is as a “decision” made by a DM about whose objective function nothing is known. Both cases require consideration of a set of outcomes arising from either the different ways in which the uncertain future could unfold or from the different possible actions the other players could take. Algorithms for solving these difficult optimization problems must, either explicitly or implicitly, rely on efficient methods for exploring this outcome space. This commonality turns out to be more than a philosophical abstraction. The mathematical connections between multistage and multilevel optimization problems run deep and existing algorithms for the two cases already exhibit common features, as we illustrate in what follows.

In the rest of this paper, we address the broad class of optimization problems that we refer to from here on by the collective name multistage mixed integer linear optimization problems. Such problems allow for multiple decision stages, with decisions at each stage made by a different DM and with each stage followed by the revelation of the value of one or more random variables affecting the available actions at the subsequent stages. Each DM is assumed to have their own objective function for the evaluation of the decisions made at all stages following the stage at which they make their first decision, including stages whose decision they do not control. Importantly, the objective functions of different DMs may (but do not necessarily) conflict. Algorithmically, the focus of such problems is usually on determining an optimal decision at the first stage. At the point in time when later-stage decisions must be made, the optimization problem faced by those DMs has the same form as the one faced by early-stage DMs but, in it, the decisions made at the earlier stages act as deterministic inputs. Note that, while we have assumed different DMs at each stage, it is entirely possible to model scenarios in which a single DM makes multiple decisions over time. From a mathematical standpoint, this latter situation is equivalent to the case in which different DMs share the same objective function and we thus do not differentiate these situations in what follows.

Although the general framework we introduce applies more broadly, we focus here on problems with two decision stages and two DMs, as well as stochastic parameters whose values are realized between the two stages. We further restrict our consideration to the case in which we have both continuous and integer variables but the constraints and objective functions are linear. We refer to these problems as two-stage mixed integer linear optimization problems (2SMILPs). Despite this restricted setting, the framework can be extended to multiple stages and more general forms of constraints and objective functions in a conceptually straightforward way (see, e.g., Section 3.3).

Multilevel and multistage structures, whose two level/stage versions are known as bilevel optimization problems and two-stage stochastic optimization problems with recourse (2SPRs), arise naturally in a vast array of applications of which we touch on only a small sample here.

In the modeling of large organizations with hierarchical decision-making processes, such as corporations and governments, Bard (1983) discusses a bilevel corporate structure in which top management is the leader and subordinate divisions, which may have their own conflicting objectives, are the followers. Similarly, government policy-making can be viewed from a bilevel optimization perspective: Bard et al. (2000) models a government encouraging biofuel production through subsidies to the petro-chemical industry, while Amouzegar and Moshirvaziri (1999) models a central authority that sets prices and taxes for hazardous waste disposal while polluting firms respond by making location-allocation and recycling decisions.

A large body of work exists on interdiction problems, which model competitive games where two players have diametrically opposed goals and the first player has the ability to prevent one or more of the second player’s possible activities (variables) from being engaged in at a non-zero level. Most of the existing literature on these problems has focused on variations of the well-studied network interdiction problem Wollmer (1964); McMasters and Mustin (1970); Ghare et al. (1971); Wood (1993); Cormican et al. (1998); Israeli and Wood (2002); Held and Woodruff (2005); Janjarassuk and Linderoth (2008), in which the lower-level DM is an entity operating a network of some sort and the upper-level DM (or interdictor) attempts to interdict the network as much as possible via the removal (complete or otherwise) of portions (subsets of arcs or nodes) of the network. A more general case which does not involve networks (the so-called linear system interdiction problem) was studied in Israeli (1999) and later in DeNegre (2011). A related set of problems involves an attacker disrupting warehouses or other facilities to maximize the resulting transportation costs faced by the firm (the follower) Church et al. (2004); Scaparra and Church (2008); Zhang et al. (2016). A trilevel version of this problem involves the firm first fortifying the facilities, then the attacker interdicting them, and finally the firm re-allocating customers Church and Scaparra (2006). More abstract graph-theoretical interdiction problems in which the vertices of a graph are removed in order to reduce the graphs’ stability/clique number are studied in Rutenburg (1994); Furini et al. (2019); Coniglio and Gualandi (2017).

Multilevel problems arise in a wide range of industries. For instance, in the context of the electricity industry, Hobbs and Nelson (1992) applies bilevel optimization to demand-side management while Grimm et al. (2016) formulates a trilevel problem with power network expansion investments in the first level, market clearing in the second, and redispatch in the third. Cote et al. (2003); Coniglio et al. (2020b) addresses the capacity allocation and pricing problem for the airline industry. Dempe et al. (2005) presents a model for the natural-gas shipping industry. A large amount of work has been carried out in the context of traffic planning problems, including constructing road networks to maximize users’ benefits Ben-Ayed et al. (1992), toll revenue maximization Labbé et al. (1998), and hazardous material transportation Kara and Verter (2004). For a general review on these problems and for one specialized to price-setting, the reader is referred to Migdalas (1995); Labbé and Violin (2013). More applications arise in chemical engineering and bioengineering in the design and control of optimized systems. For example, Clark and Westerberg (1990) optimizes a chemical process by controlling temperature and pressure (first-stage actions) where the system (second stage) reaches an equilibrium as it naturally minimizes the Gibbs free energy. Burgard et al. (2003) develops gene-deletion strategies (first stage) to allow overproduction of a desired chemical by a cell (second stage). In the area of telecommunication networks, bilevel optimization has been used for modeling the behavior of a networking communication protocol (second-level problem) which the network operator, acting as first-level DM, can influence but not directly control. The case of routing over a TCP/IP network is studied in Amaldi et al. (2013c, b, a, 2014).

The literature on game theory features many works on bilevel optimization problems naturally arising from the computation of Stackelberg equilibria in different settings. Two main variants of the Stackelberg paradigm are typically considered: one in which the followers can observe the action that the leader draws from its commitment and, therefore, the commitment is in pure strategies Stackelberg (2010), and one in which the followers cannot do that directly and, hence, the leader’s commitment can be in mixed strategies Conitzer and Sandholm (2006); von Stengel and Zamir (2010). While most of the works focus on the case with a single leader and a single follower (which leads to a proper bilevel optimization problem), some work has been done on the case with more than two players: see Conitzer and Korzhyk (2011); Basilico et al. (2016, 2017); Coniglio et al. (2017); Basilico et al. (2020); Marchesi et al. (2018); Castiglioni et al. (2019b); Coniglio et al. (2020a) for the single-leader multi-follower case, Smith et al. (2014); Lou and Vorobeychik (2015); Laszka et al. (2016); Lou et al. (2017); Gan et al. (2018) for the multi-leader single-follower case, or Castiglioni et al. (2019a); Pang and Fukushima (2005); Leyffer and Munson (2010); Kulkarni and Shanbhag (2014) for the multi-leader multi-follower case. Practical applications are often found in security games, which correspond to competitive situations where a defender (leader) has to allocate scarce resources to protect valuable targets from an attacker (follower) Paruchuri et al. (2008); Kiekintveld et al. (2009); An et al. (2011); Tamble (2011). Other practical applications are found in, among others, inspection games Avenhaus et al. (1991) and mechanism design Sandholm (2002). The works on the computation of a correlated equilibrium Celli et al. (2019) as well those on Bayesian persuasion Celli et al. (2020), where a leader affects the behavior of the follower(s) by a signal, also fall in this category.

Finally, there are deep connections between bilevel optimization and the algorithmic decision framework that drives branch and bound itself, and it is likely that the study of bilevel optimization problems may lead to improved methods for solving single-level optimization problems. For example, the problem of determining the disjunction whose imposition results in the largest bound improvement within a branch-and-bound framework and the problem of determining the maximum bound-improving inequality are themselves bilevel optimization problems Mahajan (2009); Mahajan and Ralphs (2010); Coniglio and Tieves (2015). The same applies in $n$-ary branching when one looks for a branching decision leading to the smallest possible number of child nodes Lodi et al. (2009); Segundo et al. (2019).

Multistage problems and, in particular, two-stage stochastic optimization problems with recourse, arise in an equally wide array of application areas, including scheduling, forestry, pollution control, telecommunication and finance. Grass and Fischer (2016) surveys literature, applications, and methods for solving disaster-management problems arising in the humanitarian context. Gupta et al. (2007) addresses network-design problems where, in the second stage, after one of a finite set of scenarios is realized, additional edges of the network can be bought, and provides constant-factor approximation algorithms. A number of works address the two-stage stochastic optimization with recourse version of classical combinatorial optimization problems: among others, Dhamdhere et al. (2005) considers the spanning-tree problem, Katriel et al. (2007) the matching problem, and Gendreau et al. (1996); Gørtz et al. (2012) the vehicle routing problem. For references to other areas of applicability, see the books Birge and Louveaux (2011); Kall and Mayer (2010) and, in particular, Wallace and Ziemba (2005).

The first recognizable formulations for bilevel optimization problems were introduced in the 1970s in Bracken and McGill (1973) and this is when the term was also first coined. Beginning in the early 1980s, these problems attracted increased interest. Vicente and Calamai (1994) provide a large bibliography of the early developments.

There is now a burgeoning literature on continuous bilevel linear optimization, but it is only in the past decade that work on the discrete case has been undertaken in earnest by multiple research groups. Moore and Bard (1990) was the first to introduce a framework for general integer bilevel linear optimization and to suggest a simple branch-and-bound algorithm. The same authors also proposed a more specialized algorithm for binary bilevel optimization problems in Bard and Moore (1992). Following these early works, the focus shifted primarily to various special cases, especially those in which the lower-level problem has the integrality property. Dempe (2001) considers a special case characterized by continuous upper-level variables and integer lower-level variables and uses a cutting plane approach to approximate the lower-level feasible region (a somewhat similar approach is adopted in Dempe and Kue (2017) for solving a bilinear mixed integer bilevel problem with integer second-level variables). Wen and Yang (1990) consider the opposite case, where the lower-level problem is a linear optimization problem and the upper-level problem is an integer optimization problem, using linear optimization duality to derive exact and heuristic solutions.

The publication of a general algorithm for pure integer problems in DeNegre and Ralphs (2009) (based on the groundwork laid in a later-published dissertation DeNegre (2011)) spurred renewed interest in developing general-purpose algorithms. The evolution of work is summarized in Table 1, which indicates the types of variables supported in both the first and second stages (C indicates continuous, B indicates binary, and G indicates general integer). The aforementioned network interdiction problem is a special case that continues to receive significant attention, since tractable duality conditions exist for the lower-level problem Wollmer (1964); McMasters and Mustin (1970); Ghare et al. (1971); Wood (1993); Cormican et al. (1998); Israeli and Wood (2002); Held and Woodruff (2005); Janjarassuk and Linderoth (2008).

As for the case of multistage stochastic optimization, the two-stage linear stochastic optimization problem with recourse in which both the first- and second-stage problems contain only continuous variables has been well studied both theoretically and methodologically. Birge and Louveaux (2011); Kall and Mayer (2010) survey the related literature. The integer version of the problem was first considered in the early 1990s by Louveaux and van der Vlerk (1993) for the case of two-stage problems with simple integer recourse. Combining the methods developed for the linear version with the branch-and-bound procedure, Laporte and Louveaux (1993) proposed an algorithm known as the integer L-shaped method where the first-stage problem contains only binary variables. Due to the appealing structural properties of a (mixed) binary integer optimization problem, a substantial amount of literature since then has been considering the case of a two-stage stochastic problem with (mixed) binary variables in one or both stages Sen and Higle (2005); Sherali and Zhu (2006); Gade et al. (2012). The case of two-stage problems with a pure integer recourse has also been frequently visited, see Schultz et al. (1998); Kong et al. (2006). It must be noted that methods such as these, which are typically developed for special cases, often rely on the special structure of the second-stage problem, thus being often not applicable to the two-stage problem with mixed integer restrictions. Algorithms for stochastic optimization problems with integer recourse were proposed by Carøe and Tind (1998) and Sherali and Fraticelli (2002).

Our canonical risk function is a generalization of the risk function traditionally used in defining 2SPRs. As usual, let us now introduce a random variable $U$ over an outcome space $\Omega$ representing the set of possible future scenarios that could be realized between the making of the first- and second-stage decisions. The values of this random variable will be input parameters to the so-called second-stage problem to be defined below.

As is common in the literature on 2SPRs, we assume that $U$ is discrete, i.e., that the outcome space $\Omega$ is finite, so that $\omega\in\Omega$ represents which of a finite number of explicitly enumerated scenarios is actually realized. In practice, this assumption is not very restrictive, as one can exploit any algorithm for the case in which $\Omega$ is assumed finite to solve cases where $\Omega$ is not (necessarily) finite by utilizing a technique for discretization, such as sample average approximation (SAA) Shapiro (2003). As $U$ is discrete in this work, we can associate with it a probability distribution defined by $p\in\mathbb{R}^{|\Omega|}$ such that $0\leq p_{\omega}\leq 1$ and $\sum_{\omega\in\Omega}p_{\omega}=1$.

With this setup, the canonical risk function for $x\in\mathbb{Q}^{n_{1}}$ is

where $\Xi_{\omega}(x)$ is the scenario risk function, defined as

the set

is one member of a family of polyhedra that is parametric w.r.t. the right-hand side vector $\beta\in\mathbb{R}^{m_{2}}$ and represents the second-stage feasibility conditions; and $Y=\mathbb{Z}^{r_{2}}_{+}\times\mathbb{Q}^{n_{2}-r_{2}}_{+}$ represents the second-stage integrality and non-negativity requirements. The deterministic input data defining $\Xi_{\omega}$ are $d^{1},d^{2}\in\mathbb{Q}^{n_{2}}$ and $G^{2}\in\mathbb{Q}^{m_{2}\times n_{2}}$. $A^{2}_{\omega}\in\mathbb{Q}^{m_{2}\times n_{1}}$ and $b^{2}_{\omega}\in\mathbb{Q}^{m_{2}}$ represent the realized values of the random input parameters in scenario $\omega\in\Omega$, i.e., $U(\omega)=(A^{2}_{\omega},b^{2}_{\omega})$.

As indicated in (RF) and (2SRF), the inner optimization problem faced by the second-stage DM is parametric only in its right-hand side, which is determined jointly by the value $\omega$ of the random variable $U$ and by the chosen first-stage solution. It will be useful in what follows to define a family of second-stage optimization problems

that are parametric in the right-hand side $\beta\in\mathbb{R}^{m_{2}}$ (we use “$\inf$” instead of “$\min$” here because, for $\beta\not\in\mathbb{Q}^{m_{2}}$, the minimum may not exist). By further defining

to be the parametric right-hand side that arises when the chosen first-stage solution is $x\in X$ and the realized scenario is $\omega\in\Omega$, we can identify the member of the parametric family defined in (SS) in scenario $\omega\in\Omega$ when the chosen first-stage solution is $x\in X$ as that with feasible region $\mathcal{P}_{2}(\beta^{\omega}(x))\cap Y$. Associated with each $x\in\mathbb{Q}^{n_{1}}$ and $\omega\in\Omega$ is the set of all alternative optimal solutions to the second-stage problem (SS) (we allow for $x\not\in X$ here because such solutions arise when solving certain relaxations), called the rational reaction set and denoted by

For a given $x\in\mathbb{Q}^{n_{1}}$, $\mathcal{R}^{\omega}(x)$ may be empty if $\mathcal{P}_{2}(b^{2}_{\omega}-A^{2}_{\omega}x)\cap Y$ is itself empty or if the second-stage problem is unbounded (we assume in Section 3.2 that this cannot happen, however).

When $|\mathcal{R}^{\omega}(x)|>1$, the second-stage DM can, in principle, choose which alternative optimal solution to implement. We must therefore specify in the definition of the risk function a rule by which to choose one of the alternatives. According to our canonical risk function (RF) and the corresponding scenario risk function (2SRF), the rule is to choose, for each scenario $\omega\in\Omega$, the alternative optimal solution that minimizes $d^{1}y^{\omega}$, which corresponds to choosing the collection $\{y^{\omega}\}_{\omega\in\Omega}$ of solutions to the individual scenario subproblems that minimizes

This is known as the optimistic or semi-cooperative case in the bilevel optimization literature, since it corresponds to choosing the alternative that is most beneficial to the first-stage DM. Throughout the paper, we consider this case unless otherwise specified. In Section 3.3, we discuss other forms of risk function.

Because of the subtleties introduced above, there are a number of ways one could define the “feasible region” of (2SMILP). We define the feasible region for scenario $\omega$ (with respect to both first- and second-stage variables) as

and members of $\mathcal{F}^{\omega}$ as feasible solutions for scenario $\omega$. Note that this definition of feasibility does not prevent having $(x,y^{\omega})\in\mathcal{F}^{\omega}$ but $d^{1}y^{\omega}>\Xi_{\omega}(x)$. This will not cause any serious difficulties, but is something to keep in mind.

We can similarly define the feasible region with respect to just the first-stage variables as

Since $\Xi(x)=\infty$ for $x\in\mathbb{Q}^{n_{1}}$ if the feasible region $\mathcal{P}_{2}(\beta^{\omega}(x))\cap Y$ of the second-stage problem (SS) is empty for some $\omega\in\Omega$, we have that, for $x\in\mathcal{P}_{1}\cap X$, the following are equivalent:

Finally, it will be convenient to define $\mathcal{P}^{\omega}$ to be the feasible region of the relaxation of the deterministic two-stage problem under scenario $\omega\in\Omega$ that is obtained by dropping the optimality requirement for the second-stage variables $y^{\omega}$, as well as any integrality restrictions. Formally, we have:

Later in Section 7, we will use these sets to define a relaxation for the entire problem that will be used as the basis for the development of a branch-and-cut algorithm.

This assumption, which is made for ease of presentation and can be relaxed, results in the boundedness of (2SMILP).

These two assumptions together guarantee that an optimal solution exists whenever (2SMILP) is feasible Vicente et al. (1996). It also guarantees that the convex hull of $\mathcal{F}^{\omega}$ is a polyhedron, which is important for the algorithms we discuss later. Note that, due to the assumption of optimism, we can assume w.l.o.g. that all first-stage variables are linking variables by simply interpreting the non-linking variables as belonging to the second stage. While this may seem conceptually inconsistent with the intent of the original model, it is not difficult to see that the resulting model is mathematically equivalent, since these variables do not affect the second-stage problem and thus, the optimistic selection of values for those variables will be the same in either case.

Before closing this section, we remark that, in this article, we do not allow second-stage variables in the first-stage constraints. While this case can be handled with techniques similar to those we describe in the paper from an algorithmic perspective, it does require a more complicated notation which, for the sake of clarity, we prefer not to adopt. Detailed descriptions of algorithms for this more general case in the bilevel setting are provided in Tahernejad et al. (2016); Bolusani and Ralphs (2020).

With $\Xi$ defined as in (RF), the problem (2SMILP) generalizes several well-known classes of optimization problems.

Among possible notions of duality, the one most relevant to the development of optimization algorithms is one that also has an intuitive interpretation in terms of familiar economic concepts. This theory rests fundamentally on an understanding of the so-called value function, which we introduce below. The value function of an MILP has been studied by a number of authors and a great deal is known about its structure and properties. Early work on the value function includes Blair and Jeroslow (1977, 1979, 1984); Blair (1995), while the material here is based on the work in Güzelsoy and Ralphs (2007); Güzelsoy (2009); Hassanzadeh and Ralphs (2014b, a).

As a starting point, consider an instance of (SS) with fixed right-hand side $b$ and let us interpret the values of the variables as specifying a numerical “level of engagement” in certain activities in an economic market. Further, let us interpret the constraints as corresponding to limitations imposed on these activities due to available levels of certain scarce resources (it is most natural to think of “$\leq$” constraints in this interpretation). In each row $j$ of the constraint matrix, the coefficient $G^{2}_{ij}$ associated with activity (variable) $i$ can then be thought of as representing the rate at which resource $j$ is consumed by engagement in activity $i$. In this interpretation, the optimal primal solution then specifies the level of each activity in which one should engage in order to maximize profits (it is most natural here to think in terms of maximization), given the fixed level of resources $b$.

Assuming that additional resources were available, how much should one be willing to pay? The intuitive answer is that one should be willing to pay at most the marginal amount by which profits would increase if more of a particular resource were made available. Mathematically, this information can be extracted from the value function $\phi:\mathbb{R}^{m_{2}}\rightarrow\mathbb{R}\cup\{\pm\infty\}$ associated with (SS), defined by

for $\beta\in\mathbb{R}^{m_{2}}$. Since this function returns the optimal profit for any given basket of resources, its gradient at $b$ (assuming $\phi$ is differentiable at $b$) tells us what the marginal change in profit would be if the level of resources available changed in some particular direction. Thus, the gradient specifies a “price” on that basket of additional resources.

The reader familiar with the theory of duality for linear optimization problems should recognize that the solution to the usual dual problem associated with an LP of the form (SS) (i.e., assuming $r_{2}=0$) provides exactly this same information. In fact, we describe below that the set of optimal solutions to the LP dual are precisely the subgradients of its associated value function. This dual solution can hence be interpreted as a linear price on the resources and is sometimes referred to as a vector of “dual prices.” The optimal dual prices allow us to easily determine whether it will be profitable to enter into a particular activity $i$ by comparing the profit $d^{2}_{i}$ obtained by entering into that activity to the cost $uG^{2}_{i}$ of the required resources, where $u$ is a given vector of dual prices and $G_{i}^{2}$ is the $i$-th column of $G^{2}$. The difference $d^{2}_{i}-uG^{2}_{i}$ between the profit and the cost is the reduced profit/cost in linear optimization. It is easily proven that the reduced profit of each activity entered into at a non-zero level (i.e., reduced profits of the variables with non-zero value) must be non-negative (again, in the case of maximization) and duality provides an intuitive economic interpretation of this result.

Although the construction of the full value function is challenging even in the simplest case of a linear optimization problem, approximations to the value function in the local area around $b$ can still be used for sensitivity analysis and in optimality conditions. The general dual problem we describe next formalizes this idea by formulating the problem of constructing a function that bounds the value function from below everywhere but yields a strong approximation near a fixed right-hand side $b$. Such a so-called “dual function” can yield approximate “prices” and its iterative construction can also be used in a more technical way to guide the evolution of an algorithm by providing gradient information helpful in finding the optimal solution, as well as providing a proof of its optimality.

Dual functions are naturally associated with relaxations of the original problem, as the value function of any relaxation yields a feasible dual function. In particular, the value function of the well-known LP relaxation is the best convex under-estimator of the value function.

In contrast to dual functions, primal functions are naturally associated with restrictions of the original problem and the value function of any such restriction yields a valid primal function.

It is immediately evident that a pair of primal and dual functions yields optimality conditions. If we have a primal function $H^{*}$ and a dual function $F^{*}$ such that $F^{*}(b)=\gamma=H^{*}(b)$ for some $b\in\mathbb{R}^{m_{2}}$, then we must also have $\phi(b)=\gamma$. Proofs of optimality of this nature are produced by many optimization algorithms.

The concepts we have discussed so far further lead us to the definition of a generalized dual problem, originally introduced in Güzelsoy and Ralphs (2007), for an instance of (SS) with right-hand side $b\in\mathbb{R}^{m_{2}}$. This problem simply calls for the construction of a dual function that is strong for a particular fixed right-hand side $b\in\mathbb{R}^{m_{2}}$ by determining

where $\Upsilon^{m_{2}}\subseteq\{f\;|\;f:\mathbb{R}^{m_{2}}\rightarrow\mathbb{R}\}$. Here, $\Upsilon^{m_{2}}$ can be taken to be a specific class of functions, such as linear or subadditive, to obtain specialized dual problems for particular classes of optimization problems. It is clear that (MILPD) always has a solution $F^{*}$ that is strong, provided that the value function is real-valued everywhere (and hence belongs to $\Upsilon^{m_{2}}$, however it is defined), since $\phi$ itself is a solution whenever it is finite everywhere.¹¹1When the value function is not real-valued everywhere, we have to show that there is a real-valued function that coincides with the value function when it is real-valued and is itself real-valued everywhere else, but is still a feasible dual function (see Wolsey (1981a)).

Although it may not be obvious, this notion of a dual problem naturally generalizes existing notions for particular problem classes. For example, consider again a parametric family of LPs defined as in (SS) (i.e., assuming $r_{2}=0$). We show informally that the usual LP dual problem with respect to a fixed instance with right-hand side $b$ can be derived by taking $\Upsilon^{m_{2}}$ to be the set of all non-decreasing linear functions in (MILPD) and simplifying the resulting formulation. First, let a non-decreasing linear function $F:\mathbb{R}^{m_{2}}\rightarrow\mathbb{R}$ be given. Then, $\exists u\in\mathbb{R}^{m_{2}}_{+}$ such that $F(\beta)=u\beta$ for all $\beta\in\mathbb{R}^{m_{2}}$. It follows that

From the above, it then follows that, for any $\beta\in\mathbb{R}^{n_{2}}$, we have

The conditions on the left-hand side above are exactly the feasibility conditions for the usual LP dual and the final condition on the right is the feasibility condition for (MILPD). Hence, the usual dual feasibility conditions ensure that $u$ defines a linear function that bounds the value function from below and is a dual function in the sense we have defined. The fact that the epigraph of $\phi$ is a convex polyhedral cone in this case (it is the max of linear functions associated with extreme points of the feasible region of the dual problem) is enough to show that the dual (MILPD) is strong in the LP case, even when we take $\Upsilon^{m_{2}}$ to be the set of (non-decreasing) linear functions. Furthermore, it is easy to show that any subgradient of $\phi$ at $b$ is an optimal solution (and in fact, the set of all dual feasible solutions is precisely the subdifferential of the value function at the origin).

The concepts just discussed can be easily seen in the following small example (note that this example is equality-constrained, in which case most of the above derivation carries through unchanged, but the dual function no longer needs to be non-decreasing).

• Example 1

  	$\displaystyle\min$	$\displaystyle\ 6y_{1}+7y_{2}+5y_{3}$
  	$\displaystyle\operatorname{s.\!t.}$	$\displaystyle\ 2y_{1}-7y_{2}+y_{3}=b$
  		$\displaystyle\ y_{1},y_{2},y_{3}\in\mathbb{R}_{+}.$

  The solution to the dual of this LP is unique whenever $b$ is non-zero and can be easily obtained by considering the ratios $c_{j}/a_{j}$ of objective coefficient to constraint coefficient for $j=1,2,3$, which determine which single primal variable will take a non-zero value in the optimal basic feasible solution. Depending on the sign of $b$, we obtain one of two possible dual solutions:

  $$u^{*}=\begin{cases}\displaystyle 6/2=3&\textrm{if }b>0\\ \displaystyle 7/(-7)=-1&\textrm{if }b<0.\end{cases}$$

  Thus, the value function associated with this linear optimization problem is as shown in Figure 1. Note that, when $b=0$, the dual solution is not unique and can take any value between $-1$ and $3$. This set of solutions corresponds to the set of subgradients at the single point of non-differentiability of the value function.

  

  This function has one of two gradients for all points that are differentiable, and these gradients are equal to one of the two dual solutions derived above. ∎

As we mentioned previously, solution methods for (2SMILP) inherently involve the explicit or implicit approximation of several functions, including the value function $\phi$ in (2SVF) and the risk function $\Xi$ in (RF), which ultimately derives its structure from $\phi$. Here, we summarize the results described in the series of papers Güzelsoy and Ralphs (2007); Güzelsoy (2009); Hassanzadeh and Ralphs (2014b). Most importantly, the function is piecewise polyhedral, lower semi-continuous, subadditive, and has a discrete structure that is derivative of the structure of two related value functions which we now introduce.

Let $y_{C}$, $d^{2}_{C}$, and $G^{2}_{C}$ be the parts of each of the vectors/matrices describing the second-stage problem (SS) that are associated with the continuous variables and let $y_{I}$, $d^{2}_{I}$, and $G^{2}_{I}$ be likewise for the integer variables. The continuous restriction (CR) is the LP obtained by dropping the integer variables in the second-stage problem (or equivalently, setting them to zero). This problem has its own value function, defined as

On the other hand, if we instead drop the continuous variables from the problem, we can then consider the integer restriction (IR), which has value function

To illustrate how these two functions combine to yield the structure of $\phi$ and to briefly summarize some of the important results from the study of this function carried out in the aforementioned papers, consider the following simple example of a two-stage stochastic mixed integer linear optimization problem with a single constraint. Note that, in this example, $d^{1}=d^{2}$ and we are again considering the equality-constrained case in order to make the example a bit more interesting.

Examining Figure 5.4, it appears that $\phi$ is comprised of a collection of translations of $\phi_{C}$, each of which has a structure that is similar to the value function of the LP in Example 5.3. At points where $\phi$ is differentiable, the gradient always corresponds to one of the two solutions to the dual of the continuous restriction (precisely as in Example 5.3, dual solutions are the ratios of objective function coefficients to constraint coefficients for the continuous variables), which are in turn also the gradients of $\phi_{C}$. The so-called points of strict local convexity are the points of non-differentiability that are the extreme points of the epigraphs of the translations of $\phi_{C}$ and are determined by the solutions to the integer restriction. In particular, they correspond to points at which $\phi_{I}$ and $\phi$ are coincident. For instance, observe that, in the example, $\phi_{I}(5)=\phi(5)=4$. Finally, we can observe in Figure 5.4 how the structure of $\phi$ translates into that of $\Psi$. ∎

Under the assumptions of the theorem, this result provides a finite description of $\phi$.

Constructing functions that bound the value function of an MILP is an important part of solution methods for both traditional single-stage optimization problems and their multistage counterparts. Functions bounding the value function from below are exactly the dual functions defined earlier and arise from relaxations of the original problem (such as the LP relaxation, for instance). They are naturally obtained as by-products of common solution algorithms, such as branch and bound, which itself works by iteratively strengthening a given relaxation and produces a dual proof of optimality.

Functions that bound the value function from above are the primal functions defined earlier and can be obtained by considering the value function of a restriction of the original problem. While it is a little less obvious how to obtain such functions in general (solution algorithms generally do not produce practically useful primal functions), they can be obtained by taking the minimum over the value functions of restrictions obtained by fixing the values of integer variables, as we describe below.

Both primal and dual functions can be iteratively improved by producing new such functions and combining them with existing ones by taking the maximum over several bounding functions in the dual case or the minimum over several bounding functions in the primal case. When such functions are iteratively constructed to be strong at different right-hand side values, such as when solving a sequence of instances with different right-hand sides, such a technique can yield an approximation with good fidelity across a larger part of the domain than any singly constructed function could—this is, in fact, the principle implicitly behind the algorithms we describe in Section 7.1.