Skip to main content

Modulo operation Constraint?

Answered

Comments

10 comments

  • Eli Towle
    Gurobi Staff Gurobi Staff

    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
  • Umair Sindhu
    Gurobi-versary
    Conversationalist
    Curious

    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
  • Eli Towle
    Gurobi Staff Gurobi Staff

    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
  • Umair Sindhu
    Gurobi-versary
    Conversationalist
    Curious

    Got it, Sir. Thank you.

    I am just wondering, as my set x = {0,1,..,n}, has elements. This single constraint x == 4*x + y  will evaluate for each value of x?  

     

     

    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    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
  • Umair Sindhu
    Gurobi-versary
    Conversationalist
    Curious

    Sir and 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 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
  • Eli Towle
    Gurobi Staff Gurobi Staff

    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
  • Umair Sindhu
    Gurobi-versary
    Conversationalist
    Curious

    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
  • Eli Towle
    Gurobi Staff Gurobi Staff

    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
  • Umair Sindhu
    Gurobi-versary
    Conversationalist
    Curious

    Right Sir, I got it.

    Thank you so much.

    0

Please sign in to leave a comment.