Modulo operation Constraint?
Answered
Hi
Can we model such a constraint that involves modulo operation? For example, y = x % 4.
-
Official comment
This post is more than three 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 why not try our AI Gurobot?. -
Assuming \( x \) is an integer variable, we can model \( y = x \bmod 4 \) as follows:
$$\begin{align*}x &= 4u + y \\ 0 &\leq y \leq 3 \\ u, x, y &\in \mathbb{Z}.\end{align*}$$
Because \( y \in \{0, 1, 2, 3\} \), there are unique values of \( u \) and \( y \) such that \( x = 4u + y \). So, \( u \) and \( y \) are respectively the quotient and remainder of the Euclidean division of \( x \) by \( 4 \).
2 -
Thank you so much for the response, Sir.
How to deal with u in the constraint x = 4u + y, for an optimization problem?
Let suppose we have set of x and y as fellows
x = {0,1,....,n} and y ={0,1,2,3}
The constraint would be like this ?
for (u=0; u <= n; u = u+3)
m.addConstr( x = 4u +y)
0 -
You have to first add the new \( u \) variable with Model.addVar(), then you can add the constraint \( x = 4u + y \) with a single call to Model.addConstr(). E.g., in Python:
x = m.addVar(ub=n, vtype=GRB.INTEGER, name='x')
y = m.addVar(ub=3, vtype=GRB.INTEGER, name='y')
u = m.addVar(vtype=GRB.INTEGER, name='u')
m.addConstr(x == 4*u + y)0 -
Got it, Sir. Thank you.
I am just wondering, as my set x = {0,1,..,n}, has n elements. This single constraint x == 4*x + y will evaluate for each value of x?
0 -
I was assuming \( \texttt{x} \) was a single model variable. How do you define \( \texttt{x} \) in your code? Since \( \texttt{x} \) is something like a Python list, the equation \( y = x \bmod 4 \) isn't well-defined. Could you elaborate on what you are trying to do?
0 -
Sir x and y are my two geometrical dimensions not the lists, which I can define with the following constraints
x >= 0
x <= n
y >= 0
y <= 3
I am considering only integer points of these dimensions. And I want to place each x to the corresponding y. Since y upper bound is 3, whereas x got more elements than y.That's why I want to use the modulo operation which can place each x to a y as follows
y[0] = x[0]
y[1] = x[1]
y[2] = x[2]
y[3] = x[3]
y[0] = x[4]
y[1] = x[5]
y[2] = x[6]
y[3] = x[7]
...............
..............
Furthermore how I can define geometrical dimensions in Gurobi (Python)?
0 -
Okay, then I think the original Python code I posted is what you want. With this formulation, \( x \) can take on \( n + 1 \) discrete values ( \( 0, 1, \ldots, n \) ). However, \( x \) is a single variable in the model. During the optimization process, Gurobi looks for values to assign to all of the model variables such that all of the model constraints are satisfied. So, if your variables are defined to be integer and the bounds are correctly defined, you only need a single constraint to represent the modulus operator:
$$\begin{align*}x &= 4u + y. \end{align*}$$
This single constraint captures the relationship \( y = x \bmod 4 \). For example, if \( x \) takes on a value of \( 7 \) in a solution, then the above constraint is satisfied if and only if \( u = 1 \) and \( y = 3 \). If the solver wants to assign a value of \( 12 \) to \( x \), then it must hold that \( u = 3 \) and \( y = 0 \). There is no need to define \( n + 1 \) different constraints to cover all values of \( x \) and \( y \), since this is implicitly captured by the formulation.
It is also okay that the domain of \( x \) is larger than that of \( y \). Ultimately, the solver assigns a single value to \( x \) and a single value to \( y \) such that \( x \) and \( y \) satisfy the model constraints. It just has fewer possible values to assign to \( y \).
0 -
Thank you, Sir.
The modulus operator relationship is part of my little big problem, which got a couple of more dimensions, and a couple of more relations.
Sir, as I can define a dimension x, by adding an integer variable x in the model and then specifying its domain by adding two constraints.
x = m.addVar( vtype = GRB.INTEGER, name ="x")
m.addConstr( x >= 0, "c1")
m.addConstr( x <= 7, "c2")
If I want to iterate a loop on this x dimension, like
for i in range (x):
(some constraint)
is it allowed? or I have to code differently for this purpose, for example
x = m.addVars(8, vtype = GRB.INTEGER, name ="x") ?
0 -
Maybe you are confusing the bounds of an integer variable with its dimension? If you want to add a single (one-dimensional) integer variable bounded between \( 0 \) and \( 7 \), this can be done with
x = m.addVar(ub=7, vtype=GRB.INTEGER, name="x")
From a modeling perspective, this is equivalent to the following:
x = m.addVar(vtype=GRB.INTEGER, name="x")
m.addConstr(x <= 7, "xub")By default, variables added with Model.addVar() have a lower bound of \( 0 \), so you don't have to explicitly add this anywhere.
Model.addVars() can be used to add multiple variables to your model. The code
x = m.addVars(8, vtype=GRB.INTEGER, name="x")
creates eight separate integer variables to the model, each with a lower bound of \( 0 \) (and no upper bound). I don't see how this would be helpful in modeling a single modulo operation.
0 -
Right Sir, I got it.
Thank you so much.
0
Post is closed for comments.
Comments
11 comments