Linearizing factorial function
Answered
Dear community team,
I'm trying to write a constraint in the following form:
$$(a_j * (s_j!)) / L \leq 1-\gamma$$
Where \(\texttt{a}\) and \(\texttt{gamma}\) are constants and \(\texttt{s}\) and \(\texttt{L}\) are decision variables. I would like to linearize factorial function \(s_j!\) but, I don't find any useful resource to do that.
I was wondering if, is there any way to linearize factorial function (in the algebraic form) in which its argument to be variable? and does Gurobi support such function using .addgencons() method?
Best regards
A. Omidi
-
There isn't a general constraint function specifically for the factorial function.
Presumably, the upper bound on each \( s_j \) is small, since the factorial function explodes very quickly and the numbers become too large for solvers to handle in a reasonable way. Assuming the \(s_j \) are integer-valued, you could try modeling this by explicitly enumerating the possible values of \( s_j! \) for \( 0 \leq s_j \leq m \), where \( m \) is probably around \( 10 \).
First, introduce auxiliary binary variables \( u_{jk} \) for \( j = 1, \ldots, n \) and \( k = 0, \ldots, m \), and continuous variables \( y_j \) for \( j = 1, \ldots, n \). Add the following constraints to the model:
$$\begin{alignat*}{2}1 &= \sum_{k = 0}^m u_{jk} &&j = 1, \ldots, n \\ s_j &= \sum_{k = 0}^m k \cdot u_{jk} &&j = 1, \ldots, n \\ y_j &= \sum_{k = 0}^m k! \cdot u_{jk} &&j = 1, \ldots, n \\ a_j y_j &\leq L (1 - \gamma) \qquad &&j = 1, \ldots, n \\ u_{jk} &\in \{0, 1\} && j = 1, \ldots, n,\ k = 0, \ldots, m.\end{alignat*}$$
Consider a fixed \( j \in \{1, \ldots, n\} \). By the first set of constraints, exactly one of the \( u_{jk} \) binary variables equals \( 1 \). Let \( u_{jk'} = 1 \). By the second constraint family, \( s_j \) is equal to the integer \( k' \). The third constraint family sets the auxiliary variable \( y_j \) equal to \( k'! = s_j!\). Now, \( y_j \) can be used in place of \( s_j! \) in any other constraints.
If the \( s_j \) are continuous, you could instead build a piecewise-linear approximation of \( s_j! \). Due to how fast the factorial function grows, making this approximation accurate would require many piecewise-linear segments and the model may become difficult to solve.
0 -
Dear Eli,
Many thanks for your detailed explanation. I can do that for modifying my model and it works fine. :)
Would you say please, how you can use LaTex in your comments? I tried it but, it seems there is something wrong!!?
Regards
Abbas
0 -
Dear Abbas,
Did you have a look at our guide to Posting to the Community Forum?
You can always edit your comments after posting as LaTeX will not be displayed properly if there is an error within the TeX code.
It is also necessary to write LaTeX code as "Normal Text" and not "Code".Best regards,
Jaromił0 -
Dear Jaromil,
Many thanks for your explanation. I have just updated it.
Regards
Abbas
0
Please sign in to leave a comment.
Comments
4 comments