Consider a convex optimization problem with decision variable x. Though I'm interested in answers for any kind of convex optimization problem, let's say it's an LP, so we have something like:

\begin{equation*} \begin{array}{ll@{}ll} \text{min} & \displaystyle c^\text{T}x \\ \text{s.t.} & \displaystyle Ax\geq b \\ & x \geq 0 \end{array} \end{equation*}

Now let's say I have a second linear program where the constraint variables are defined by the decision variables of the first, i.e. the $x$ in what follows is the argmin of the preceding problem:

\begin{equation*} \begin{array}{ll@{}ll} \text{min} & \displaystyle d^\text{T}y \\ \text{s.t.} & \displaystyle By\geq x \\ \end{array} \end{equation*}

You could continue this chain of dependencies ad nauseam. This looks like it could be a common situation, where the decisions you make for one problem influence the feasible solutions of another, but I'm having a hard time finding examples in the literature. Possible examples that spring to mind include inventory management where you buy x units of something, and then use those x units to achieve some other goal $d^\text{T}y$, or optimal control where $c^Tx$ is a decision made at timestep $t$ and $d^Ty$ is a decision made a timestep $t+1$. But again I can't find any problems in this specific form.

Can anyone point me to some previously studied (class of) optimization problem where this setup arises?

  • 1
    $\begingroup$ I added the “bilevel-optimization” tag. $\endgroup$
    – RobPratt
    Commented Sep 24, 2022 at 3:47

1 Answer 1


This structure can arise in multi-objective optimization problems. While it is common for multi-objective problems to express each objective function directly in terms of the same variables, there can be instances where the objectives are computed via secondary / chained problems.

It also arises in stochastic programming with recourse, where the first stage model makes decisions in the face of uncertainty and the second stage model figures out how to handle the consequences of the first stage decisions. For instance, the first stage model might make production decisions in the face of uncertainty about demand, and the second stage problem might figure out the best way to deal with any shortfalls or overproduction.

Although I suspect this will not be helpful in your case, the structure you mention is similar (when things are linear) but not identical to Benders decomposition and the recent extensions of Benders. The fundamental difference is that with Benders decomposition the solution to the second problem is used to modify the first model (adding constraints), after which the first problem is solved again.

  • $\begingroup$ Thanks for the answer, do you have an example of a multi-objective optimization problem being expressed this way? $\endgroup$ Commented Sep 24, 2022 at 19:36
  • $\begingroup$ Outer problem: assign patients to facilities belonging to an HMO so as to minimize patient travel distance subject to various capacity constraints at the HMOs. Inner problems (one per facility): given the allocation of patients to that facility, assign patients to providers (creating what are called "patient panels" for the providers) subject to provider capacity constraints so as to optimize some measure of patient-provider compatibility (or subject to compatibility constraints with an objective of leveling the provider loads). $\endgroup$
    – prubin
    Commented Sep 24, 2022 at 21:29
  • $\begingroup$ Sorry, I meant a literature reference, i.e. a published example of such structure arising for a real-world problem. I haven't been able to track one down, I've only seen hypothetical scenarios. $\endgroup$ Commented Sep 25, 2022 at 3:28
  • $\begingroup$ Unfortunately, I can't think of any references off hand. $\endgroup$
    – prubin
    Commented Sep 25, 2022 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.