0
$\begingroup$

I am a engineer who is working on an optimization problem and my constraints are in the form of this statement "if $x_1=1$ then $d_1=1T$" where $T$ is just a given time period.

Scenario 1

Particularly, I need to linearize or formulate an entire system that looks like this:

$\left\{ \begin{array}{l} \begin{array}{*{20}{c}} {{\rm{if}}}&{{x_1} = 1}&{{\rm{then}}}&{{d_1} = 1T} \end{array}\\ \begin{array}{*{20}{c}} {{\rm{if}}}&{{x_2} = 1}&{{\rm{then}}}&{{d_2} = 2T} \end{array}\\ \begin{array}{*{20}{c}} {{\rm{if}}}&{{x_3} = 1}&{{\rm{then}}}&{{d_3} = 3T} \end{array}\\ \begin{array}{*{20}{c}} {...}&{...}&{...}&{...} \end{array}\\ \begin{array}{*{20}{c}} {{\rm{if}}}&{{x_n} = 1}&{{\rm{then}}}&{{d_n} = nT} \end{array} \end{array} \right.$

Scenario 2

$\left\{ {\begin{array}{*{20}{l}} {\begin{array}{*{20}{c}} {{\rm{if}}}&{{x_1} = 1}&{{\rm{then}}}&{{d_1} = 1T}\\ {{\rm{if}}}&{{x_1} = 0}&{{\rm{then}}}&{{d_1} = + \infty } \end{array}}\\ {\begin{array}{*{20}{c}} {{\rm{if}}}&{{x_2} = 1}&{{\rm{then}}}&{{d_2} = 2T}\\ {{\rm{if}}}&{{x_2} = 0}&{{\rm{then}}}&{{d_2} = + \infty } \end{array}}\\ {\begin{array}{*{20}{c}} {{\rm{if}}}&{{x_3} = 1}&{{\rm{then}}}&{{d_3} = 3T}\\ {{\rm{if}}}&{{x_3} = 0}&{{\rm{then}}}&{{d_3} = + \infty } \end{array}}\\ {\begin{array}{*{20}{c}} {...}&{...}&{...}&{...} \end{array}}\\ {\begin{array}{*{20}{c}} {{\rm{if}}}&{{x_n} = 1}&{{\rm{then}}}&{{d_n} = nT}\\ {{\rm{if}}}&{{x_n} = 0}&{{\rm{then}}}&{{d_n} = + \infty } \end{array}} \end{array}} \right.$

Here, the $x$ are binary variables that satisfied ${x_1},{x_2},{x_3},...,{x_n} \in \left\{ {0,1} \right\}$. On the other hand, ${d_1},{d_2},{d_3},...,{d_n} \ge 0$ are just some real non-negative variables. Please help me with this.

Editted

For completeness, I add scenario 2 where some enforcement is needed for the system to work.

The answer of Mr @RobPratt work quite neat but are there anyway to avoid this Big-M formulation ?

Thank you for your enthusiasm !

$\endgroup$
1
  • 1
    $\begingroup$ Not sure what solver supports $\infty$ as the value of a variable, but for Scenario 2 you could impose $d_i=i T x_i+\infty(1-x_i)$. $\endgroup$ Commented Oct 29, 2023 at 12:56

1 Answer 1

Reset to default
2
$\begingroup$

Let $M_i$ be some constant upper bound on $d_i$. The standard linearization of $$x_i=1 \implies d_i=i T$$ is achieved by the following linear “big-M” constraints: $$(0-i T)(1-x_i)\le d_i-i T \le (M_i-i T)(1-x_i)$$

To see that this linearization works, check the two cases. When $x_i=1$, the constraints enforce $0\le d_i-i T \le 0$, as desired. When $x_i=0$, the constraints enforce $0-i T\le d_i-i T \le M_i-i T$, which is redundant by the choice of $M_i$.

$\endgroup$
8
  • $\begingroup$ Thank you but this beg the question: how big should this number $M$ be ? Furthermore, will any bad thing happen if $M$ is too big or too small ? $\endgroup$ Commented Oct 29, 2023 at 2:55
  • $\begingroup$ Too large will cause numerical issues, and too small will prohibit feasible solutions that you want to allow. $\endgroup$ Commented Oct 29, 2023 at 12:53
  • $\begingroup$ So in practice I should study some statistic about the upper bound on $d_i$, and choose an avarage value for $M$ right ? $\endgroup$ Commented Oct 29, 2023 at 13:12
  • $\begingroup$ To find a good (small, data-dependent) value for $M_i$, you should consider what $d_i$ represents in your problem. $\endgroup$ Commented Oct 29, 2023 at 13:53
  • 1
    $\begingroup$ It might be best to start a new question that describes your complete business problem and asks how to formulate it mathematically. $\endgroup$ Commented Oct 29, 2023 at 14:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.