Skip to main content

Quicksum: bound is a variable




  • Jaromił Najman
    Gurobi Staff Gurobi Staff


    I will make the modeling problem slightly easier to better explain how you can reformulate your model. An equivalent explanation can be found here.

    If I understand correctly you would like to model some constraint \(\sum_{i=1}^p x_i = 0\), where \(x_i\) and \(p\) are variables.
    First, let's assume that you have a valid upper bound on the integer variable \(p\) called \(p^U\) and that \(x_i \in [x^L,x^U]\) are continuous variables.

    We introduce binary variables \(z_i\) and replace the above sum by  \(\sum_{i=1}^p x_i \cdot z_i = 0\). The bilinear terms can be linearized by the introduction of auxiliary variables \(v_i\) and the constraints \(x^L\cdot z_i \leq v_i \leq x^U \cdot z_i\) and \(x^L\cdot (1-z_i) \leq x_i - v_i \leq x^U\cdot (1-z_i)\). Meaning that ultimately we get \(\sum_{i=1}^p v_i = 0\). Now, we take care of the index part.

    What we want to achieve is that if \(i \geq p+1\) then \(z_i = 0\) and if \(i \leq p\) then \(z_i=1\). This can be achieved by the addition of the constraints \(i \geq p+1 - z_i \cdot p^U\) and \(i \leq p + (1-z_i)\cdot p^U\).

    I think that with the above you are able to reformulate your problem accordingly. Please note that this may result in a lot of additional variables, making your problem even more complex than it already is. Thus, I would recommend to try to find a different formulation where a variable does not have to be used as an index.

    Best regards,

  • Peter Joon
    First Question
    First Comment

    Hi Jaromił,

    Thank you for your consideration! I took your last advice to consider a different formulation, I will explain my steps below in case it may help anybody.

    What I have now and what works is using a tracker variable which substitutes my earlier idea of adding dummy jobs. This tracker variable is binary and takes the value 1 if we are between regular jobs and zero otherwise, furthermore the sum over the time of the tracker variable needs to be regulated to make sure the tracker is filled with ones in the gap between regular jobs.

    What this than gives is a more simple consideration in the resource usage constraint where we keep the constraint for regular jobs as I described but add for the tracker variables the sum over all tasks (i) of the trackers multiplied by the resource usage the dummy jobs had and check this constraint for each timestep t. 

    This fixes the variable index in the sum and I believe that there is limited extra complexity in terms of added variables as you remove the dummy start time and duration variables. Furthermore in terms of additional code I found that this does not significantly change compared to using dummy jobs. 

    Feel free to reach out if you want to now more about the exact code used.

    Kind regards,


Please sign in to leave a comment.