メインコンテンツへスキップ

How to add quadratic constraint in conditional indicator constraints

回答済み

コメント

5件のコメント

  • 正式なコメント
    Simranjit Kaur
    • Gurobi Staff
    This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
  • Eli Towle
    • Gurobi Staff

    Consider your simplified version of modeling \( x = 1 \implies y^2 \leq 4 \). Let \( \ell \) and \( u \) be \(y\)'s lower and upper bounds, respectively. We can model this implication with the constraint

    $$\begin{align*}y^2 &\leq 4 + (M-4)(1-x),\end{align*}$$

    where \( M = \max\{\ell^2, u^2\} \). In this case, \( M = 100 \).

    If \( x = 1 \), then the constraint becomes \( y^2 \leq 4 \), as desired. If \( x = 0 \), then the constraint enforces \( y^2 \leq 100 \), which is redundant with \( y \)'s bounds.

    0
  • Saeid Ghafouri
    • Gurobi-versary
    • Curious
    • Conversationalist

    Hi Eli,

    Thank you for your answer! how about the situation where we have two distinct variables in our formulation that are making it quadratic e.g. $z.y <= 4$ then the only modification to your solution would be to change the $M$ to $M=max{l_{z} * l_{y}, u_{z} * u_{y}}$ and the formulation to $z.y <= 4 + (M-4)(1-x)$ where $l_{z}, l_{y}$ and ${u_z}$ and $u_y$ are the lower and upper bound of $z$ and $y$ respectively, correct?

    In a more complicated scenario I have ($x$ is the indicator variable):

    Where $n$ and $b$ are variables and the rest are constants. Can I do the same in the following format?

    and set the $M$ to the following (considering all the variables and constants values are positive):

    where $l_b$ and $l_n$ are lower bounds of variable $n$ and $b$, does such an extension from your solution make sense to you?

    And is there any caveat to setting the value of $M$ to an extremely large number instead of explicitly computing $M$ with lower and upper bounds of variables? Will that have any effect on the performance of the optimizer?

    Thanks!

    0
  • Eli Towle
    • Gurobi Staff

    For the case of multiplying two distinct variables together, you should set

    $$\begin{align} M &:= \max\{\ell_y \ell_z, \ell_y u_z, u_y \ell_z, u_y u_z\}.\end{align}$$

    For example, for \( y \in [-2, -1] \) and \( z \in [1, 2] \), the maximum attainable value of \( yz \) is \( u_y \ell_z = -1 \).

    In your more complicated scenario, it looks like you want to enforce

    $$\begin{align} yz - \lambda (c_1 y + c_2) &\geq 0 \end{align}$$

    when \( x = 1 \). Is that right? If so, we should derive a valid lower bound for \( y z - \lambda (c_1 y + c_2) \). We can break this into two parts:

    • A lower bound for \( y z \) is \( m_1 := \min\{\ell_y \ell_z, \ell_y u_z, u_y \ell_z, u_y u_z\} \)
    • A lower bound for \( - \lambda (c_1 y + c_2) \) is \( m_2 := - \max\{\lambda c_1 \ell_y, \lambda c_1 u_y \} - \lambda c_2 \).

    Putting those two together, we have the constraint

    $$\begin{align} y z - \lambda (c_1 y + c_2) &\geq (m_1 + m_2)(1 - x). \end{align}$$

    You should not pick an arbitrary large value for \( M \). Not only can this cause numerical trouble for the model, but it often results in a weaker root relaxation, which can cause the model to take much longer to solve. A good rule of thumb is: your big-M values should be derived from the problem data.

    0
  • Saeid Ghafouri
    • Gurobi-versary
    • Curious
    • Conversationalist

    Thanks Eli! It was very helpful!

    0

投稿コメントは受け付けていません。