Let us have two vectors of decision variables, $\mathbf{x}$ and $\mathbf{y}$, two linear objective functions, $F \left( \mathbf{x}, \mathbf{y} \right)$ and $f \left( \mathbf{x} \right)$, and two sets of linear constraints, $G_i \left( \mathbf{x}, \mathbf{y} \right) \leq 0$ and $g_j \left( \mathbf{x} \right) \leq 0$, where $i=1,2,\dotsc,n$ and $j=1,2,\dotsc,m$.

The problem to be solved is minimization of $F$: $$ \begin{array}{rll} \min & F \left( \mathbf{x}, \mathbf{y} \right) & \\ \text{subject to:} & G_i \left( \mathbf{x}, \mathbf{y} \right) \leq 0, & i=1,2,\dotsc,n \\ & g_j \left( \mathbf{x} \right) \leq 0, & j=1,2,\dotsc,m \end{array} $$ but with the additional requirement that the values of $\mathbf{x}$ must be such that the value of $f \left( \mathbf{x} \right)$ is minimal possible for a given set of $\mathbf{y}$.

In my case, some variables of $\mathbf{x}$ are continuous and some are binary, while all $\mathbf{y}$ variables are binary.

Can this problem be solved using mixed integer linear programming (MILP), e.g. the branch and cut method and, if yes, how to formulate it?

I can solve such problems combining metaheuristics (e.g. genetic algorithms or simulated annealing), to find $\mathbf{y}$, and MILP to find $\mathbf{x}$ for each examined set of $\mathbf{y}$ values. I would, however, prefer using MILP for the entire problem, if possible.

Update. In order to clarify the problem, I'll explain its background. This problem aims at optimizing the energy supply plant. The $\mathbf{y}$ binary variables define the structure of the plant, i.e. determine if a component is going to be installed or not. The $\mathbf{x}$ variables define the operation of the plant, i.e. the operating modes of all components. If a component is not installed (corresponding $y=0$), than it cannot operate (corresponding $x=0$). The objective function $F \left( \mathbf{x}, \mathbf{y} \right)$ might be related to e.g. some financial parameter, environmental impact, energy consumption, plant reliability etc. or even a linear combination of all of them. The objective function $f \left( \mathbf{x} \right)$ represents variable operation-only-related costs. To make this simpler, I want to find $\min F \left( \mathbf{x}, \mathbf{y} \right)$ under the assumption that the plant will always operate in the cost-optimal manner (i.e. with $\min f$).

  • $\begingroup$ The inner problem doesn't depend on $y$ at all. Why not just solve it to obtain $x$, and then plug it into the larger problem to get a problem in $y$? $\endgroup$ – Michael Grant Jan 2 '15 at 23:08
  • $\begingroup$ Because that might lead to the violation of some of the constraints $G_i \left( \mathbf{x}, \mathbf{y} \right) \leq 0$. $\endgroup$ – MMSt Jan 3 '15 at 14:17
  • $\begingroup$ If the optimal value of the inner problem is unique, then there's nothing you can do about it. If it is not unique, then find its optimal value $p$, and just add the constraint $f(x)\leq p$ to the larger problem. Or maybe $f(x)\leq p+\epsilon$ to give it some breathing room. $\endgroup$ – Michael Grant Jan 3 '15 at 14:20
  • 1
    $\begingroup$ If neither of those options does what you want, then I would argue you're not actually trying to solve the model as you have described, and you may need to re-think your description. $\endgroup$ – Michael Grant Jan 3 '15 at 14:22
  • $\begingroup$ @MichaelGrant. I have added the additional explanation to the original post now. My primary objective is to minimize $F$, but under the assumption that $x$ values are such that $f$ is minimal. The $x$ values are constrained with the $y$ values. $\endgroup$ – MMSt Jan 3 '15 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.