Skip to main content

Problems adding columns "Only linear constraints allowed"

Answered

Comments

88 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    In this case, you should create an empty column for \(\texttt{newvar}\), because it will not be added to any linear constraints, but still has to be used in \(\texttt{modifyConstraints}\) afterwards. Or you handle the quadratic case separately and create the variable in \(\texttt{modifyConstraints}\) and don't call \(\texttt{addColumn}\).

    And note that the code in \(\texttt{modifyConstraint}\) should be

    rhs = current_cons.getAttr('QCRHS')
    sense = current_cons.getAttr('QCSense')
    name = current_cons.getAttr('QCName')
    newcon = self.model.addQConstr(qexpr, sense, rhs, name)
    self.model.remove(current_cons)
    1
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Carl,

    I just tried your code with Python 3.11 and Gurobi v11 and got a different error.

    Traceback (most recent call last):
      File "/Users/najman/Documents/Forum/test.py", line 221, in <module>
        master.addColumn(ScheduleCuts, itr, i)
      File "/Users/najman/Documents/Forum/test.py", line 83, in addColumn
        Column = gu.Column(newSchedule.items(), self.cons_demand.items())
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      File "src/gurobipy/column.pxi", line 35, in gurobipy.Column.__init__
    TypeError: float() argument must be a string or a real number, not 'tuple'

    This error occurs because in function \(\texttt{addColumn}\) the objects \(\texttt{newSchedule}\) and \(\texttt{self.cons_demand}\) are dictionaries, but they are required to be a list as described in the documentation of Column().

    Before constructing the Column object you should generate 2 lists of same length

    def addColumn(self, newSchedule, iter, index):
            colName = f"ScheduleUsed[{index},{iter}]"
            newScheduleList = []
            cons_demandList = []
            for item in newSchedule:
                newScheduleList.append(newSchedule[item])
                cons_demandList.append(self.cons_demand[item])
            Column = gu.Column(newScheduleList, cons_demandList)
    ...

    Note that there may be an easier way to constructs lists out of dictionaries. However, the above way will throw an error whenever a key from \(\texttt{newSchedule}\) is not present in \(\texttt{self.cons_demand}\) which should make debugging easier.

    After fixing this, I run into

    Traceback (most recent call last):
      File "/Users/najman/Documents/Forum/test.py", line 226, in <module>
        master.addColumn(ScheduleCuts, itr, i)
      File "/Users/najman/Documents/Forum/test.py", line 89, in addColumn
        self.model.addVar(vtype=gu.GBR.CONTINOUS, lb=0, obj=1.0, column=Column, name=colName)
                                ^^^^^^
    AttributeError: module 'gurobipy' has no attribute 'GBR'

    which is just a typo and it should read

    self.model.addVar(vtype=gu.GRB.CONTINUOUS, lb=0, obj=1.0, column=Column, name=colName)

    From here I run into

    Traceback (most recent call last):
      File "/Users/najman/Documents/Forum/test.py", line 226, in <module>
        master.addColumn(ScheduleCuts, itr, i)
      File "/Users/najman/Documents/Forum/test.py", line 92, in addColumn
        self.lmbda[index, iter].Start = 1
        ~~~~~~~~~~^^^^^^^^^^^^^
    KeyError: (1, 2)

    and I would say that it makes sense for you to start debugging yourself from here. We discuss debugging of a KeyError in the Knowledge Base article Tutorial: Preparing a Minimal Reproducible Example.

    Best regards, 
    Jaromił

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman Najman Thank you very much. Together with your help, I was able to get the iterative process working. However, the code currently runs over all iterations without changing the reduced costs. I suspect that this is because the columns are not added correctly. This is probably because the index \(i\) is not passed to the MP. I tried to introduce the index \(i\) into all variables and constraints in the subproblem, but I got key errors. Do you have any idea how I can solve this problem with the columns?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Do you have any idea how I can solve this problem with the columns?

    You should check whether the coefficient you pass in

    if reducedCost < -1e-6:
                ScheduleCuts = subproblem.getNewSchedule()
                master.addColumn(ScheduleCuts, itr, i)

    are actually meaningful, i.e., \(\neq 0\). If they are all \(0\) then you should first find out why.

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman I have now adapted the code so that for each iteration all sub-problems are solved first and then the next iteration begins. Unfortunately, the result is still the same. Columns are being added, but unfortunately the target function value remains unchanged, which is due to the fact that the motivation values in the SP are constant at zero. Why could this be the case? If I solve the model as a whole (i.e. without MP/SP) then these are not zero. I also added a constraint that (in theory) requires \(x\) to be at least 4 f.e. and calling the solution from the individual SP indicates that not all values of \(motivation\) are zero. I suggest, that the problem is, that the columns dont provide informations about the index \(i\), which is why the demand constraints dont change. Could it be something else? And how can I solve the problem with the index? I would be really grateful for any help!

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Carl,

    It might be best to have a look at the models you generate. You can use the write method to write out your models to a human-readable format

    model.write("myLP.lp")

    You can open the file \(\texttt{myLP.lp}\) in any standard text editor and analyze whether the model you constructed actually looks as you would expect it.

    Best regards, 
    Jaromił

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman Thanks, but before I can try that, another problem has just arisen, which again fits well with the title of the thread. I forgot to incooperate \(\lambda\) in the demand constraint. Now it has become a quadratic constraint. I can get the duals through "QCPi", but unfortunately I can't add the Columns because they have to be linear. Is there a way around this?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    I can get the duals through "QCPi", but unfortunately I can't add the Columns because they have to be linear. Is there a way around this?

    Unfortunately, currently the only way is to reconstruct the quadratic constraints with new variables. There is no equivalent to the Column object for quadratic relationships.

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman Thats sad to hear. Any idea on how to achieve that in this model?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    First you have to identify all quadratic constraints where you want to add a term. Then, you can use the getQCRow() method to get the lhs expression of the constraint. This expression will be a QuadExpr object. You can use the add() method to add your variable with a given coefficient to the quadratic expression. You can then use the addQConstr() method to add the new constraint using the QCRHS, QCSense attributes of the original constraint. After you have added the new constraint, you can remove the old one.

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman Thanks. Would this work? Sadly i cant test it right now!

    def modifyConstraints(self):
        for t in self.days:
            for s in self.shifts:
                current_cons = self.cons_demand[t, s]

                qexpr = current_cons.getQCRow()

                new_var = self.newvar
                new_coef = self.newcoef
                qexpr.add(new_var, new_coef)

                rhs = current_cons.getAttr('RHS')
                sense = current_cons.getAttr('Sense')
                name = current_cons.getAttr('ConstrName')

                self.model.addQConstr(qexpr, sense, rhs, name)

                self.model.removeConstr(current_cons)
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Yes, this should work. Of course, this needs some testing first. Note that when you remove \(\texttt{current_cons}\), then \(\texttt{self.cons_demand[t,s]}\) is no longer useful. Thus you could do this

    newcon = self.model.addQConstr(qexpr, sense, rhs, name)
    self.model.removeConstr(current_cons)
    self.cons_demand[t, s] = newcon

    This way you would overwrite \(\texttt{self.cons_demand[t, s]}\) and can reuse it later.

    You should also call update after the \(\texttt{for}\)-loops are done.

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman Thanks. Sadly i am running into this error:

    AttributeError: 'gurobipy.QConstr' object has no attribute 'getQCRow'

    And have i placed the model.update() correctly after the loop?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    The getQCRow() method has to be called on the model object

    qexpr = self.model.getQCRow(current_cons)
    0
  • Carl Baier
    Thought Leader
    First Question

    I still run into this error:

    AttributeError: 'MasterProblem' object has no attribute 'newvar'

    I know that newvar and newcoeff are not initialized, but I don't know what to assign to them. An empty variable and some value for the coefficient?

    def modifyConstraints(self):
    for t in self.days:
    for s in self.shifts:
    current_cons = self.cons_demand[t, s]
    qexpr = self.model.getQCRow(current_cons)
    new_var = self.newvar
    new_coef = self.newcoef
    qexpr.add(new_var, new_coef)
    rhs = current_cons.getAttr('RHS')
    sense = current_cons.getAttr('Sense')
    name = current_cons.getAttr('ConstrName')
    newcon = self.model.addQConstr(qexpr, sense, rhs, name)
    self.model.removeConstr(current_cons)
    self.cons_demand[t, s] = newcon
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    I know that newvar and newcoeff are not initialized, but I don't know what to assign to them. An empty variable and some value for the coefficient?

    For which variable did you create the column object? I would guess that you have to add exactly this variable here. I don't know about the coefficient, maybe just \(1.0\) would work.

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman I just did (see code in OP), but i still get this error!

    gurobipy.GurobiError: Invalid argument to QuadExpr addition
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    \(\texttt{self.motivation_i}\) is a list of variables and not a single variable.

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman I tried this but it doesnt work!

    def modifyConstraints(self):
    for t in self.days:
    for s in self.shifts:
    self.newvar = self.model.addVars(self.physicians, self.days, self.shifts, self.roster, vtype=gu.GRB.CONTINUOUS, lb=0, ub=1, name='motivation_iq')
    self.newcoef = 1.0
    current_cons = self.cons_demand[t, s]
    qexpr = self.model.getQCRow(current_cons)
    new_var = self.newvar
    new_coef = self.newcoef
    qexpr.add(new_var, new_coef)
    rhs = current_cons.getAttr('RHS')
    sense = current_cons.getAttr('Sense')
    name = current_cons.getAttr('ConstrName')
    newcon = self.model.addQConstr(qexpr, sense, rhs, name)
    self.model.removeConstr(current_cons)
    self.cons_demand[t, s] = newcon
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    The addVars() method returns a tupledict of variables. The add() method takes an expression and a coefficient as input, i.e., you can call it with a single optimization variable (not a tupledict of variables) or a multiplication of two variables (not a tupledict of variables).

    If you want to add all of the \(\texttt{motivation_iq}\) variables to each quadratic constraints, you would have to add another loop over all of these variables and add them one by one. However, I doubt that this is what you want to achieve.

    From what I understood, you wanted to add the variable for which you computed the Column object. You can save this variable.

    Column = gu.Column(rounded_ScheduleList, cons_demandList)
    self.newvar = self.model.addVar(vtype=gu.GRB.CONTINUOUS, lb=0, column=Column, name=colName)
    self.model.update()

    and then call \(\texttt{modifyConstraints}\) later when the variable is actually created.

        if reducedCost < 1e-6:
                ScheduleCuts = subproblem.getNewSchedule()
                master.addColumn(ScheduleCuts, itr, index)
    master.modifyConstraints() master.updateModel() modelImprovable = True

    In \(\texttt{modifyConstraint}\) you then could do

    self.newcoef = 1.0
    current_cons = self.cons_demand[t, s]
    qexpr = self.model.getQCRow(current_cons)
    new_var = self.newvar
    new_coef = self.newcoef
    qexpr.add(new_var, new_coef)

    I am just guessing here as I do not know or fully understand your algorithm.

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman

    Thanks for the answer, unfortunately, this error still occurs.

    gurobipy.GurobiError: Only linear constraints allowed

    I adapted my code accordingly. I also make sure to describe my problem exactly. I have a column generation algorithm where the sub-problem is solved and then the columns are passed on to the master problem with negatively reduced costs. In this case, the columns are the optimal value of the subproblem of the variable \(motivation_{ts}\). Since there are \(i\) nurses, the index is dropped here. The subproblem also provides \(\mid T\mid \times \mid S\mid\) values ​​of the variable \(motivation_{ts}\), as well as many constraints (cons_demand). So far so good. Until then, it works. Now to my current problem. Unfortunately, this cons_demand in the MP is not linear, which is why I have the problem with Column(..) and cannot add the columns to the MP. Now my current problem:

    • How can I now add this column, so in iteration \(itr=i\) such a negative column is found, it is added to the Mp, whereby this column is equal to the \(\lambda_{ir}\) ( \( r=\) respective iteration\) is multiplied as required in the demand constraint.

    How would the code need to be adjusted to achieve this? I would be grateful if you could help me here.

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Now to my current problem. Unfortunately, this cons_demand in the MP is not linear, which is why I have the problem with Column(..) and cannot add the columns to the MP.

    I think that you already answered your issue yourself. You try to add the column for nonlinear constraints. With the new modifyConstraints code, you should be able to remove cons_demand from

    Column = gu.Column(rounded_ScheduleList, cons_demandList)
    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman I see thanls. However, it looks like I'm too stupid for that. If I replace self.cons_demand with newcon it doesn't work. How would it be right then? Is a return newcon missing somewhere?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

     If I replace self.cons_demand with newcon it doesn't work. How would it be right then? Is a return newcon missing somewhere?

    I think this has been answered in the stackexchange post no?

    If not could you be more explicit what does not work? You could post the error message you get (if any).

     

    0
  • Carl Baier
    Thought Leader
    First Question

    Yes, I saw that, but I already knew what the problem was. Unfortunately I don't know how this works, so that newcon is passed. I tried it (see code above) and now I get another error:

    File "src\\gurobipy\\quadexpr.pxi", line 176, in gurobipy.QuadExpr.add
    gurobipy.GurobiError: Invalid argument to QuadExpr addition

    I really don't know what to do. What do I have to change? What should the code look like so that the linearized version is accepted correctly?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Here is the issue:

    You are calling \(\texttt{modifyConstraint}\), where you use \(\texttt{self.newvar}\) and generate \(\texttt{newcon}\). However, at this point \(\texttt{self.newvar}\) is not present, because it is created in \(\texttt{addColumn}\), which is called after \(\texttt{modifyConstraint}\). Additionally, when you create a Column in \(\texttt{addColumn}\), you use \(\texttt{newcon}\) as constrs argument, which does not make sense, because Columns can only be created for linear constraints and not for quadratic ones. Moreover, \(\texttt{newcon}\) is only 1 constraint, but the coefficient list \(\texttt{rounded_ScheduleList}\) holds more than 1 coefficient.

    To my understanding, you should first call \(\texttt{addColumn}\) where you generate the Column for linear constraints. I think you had this working at some point in time. In \(\texttt{addColumn}\), you create \(\texttt{self.newvar}\). Then, after \(\texttt{addColumn}\) you call \(\texttt{modifyConstraint}\), where you need \(\texttt{self.newvar}\) to re-create the affected quadratic constraints. You should not need the new quadratic constraints anywhere else outside of this function.

    I hope this helps.

     

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman Thank you for the detailed answer. Unfortunately, I do not fully understand it. Do you mean that I should reintroduce a linear constraint in the MP, and then only in modifyConstraint() then create the quadratic one? How do I then get the lambda added in the first iteration? Could you possibly provide me with the code on how to implement this approach?

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    My question is: Why in this line

    Column = gu.Column(rounded_ScheduleList, newcon)

    you use \(\texttt{newcon}\), which is just a single quadratic constraint?

    For my understanding the \(\texttt{addColumn}\) function should create a new variable \(\texttt{newvar}\) and add it to all affected linear constraints. Then \(\texttt{modifyConstraint}\) is called to also add \(\texttt{newvar}\) to all affected quadratic constraints.

    0
  • Carl Baier
    Thought Leader
    First Question

    Jaromił Najman I get that. The problem is, I only want the new variable newvar being added to the quadratic constraints, as the second constraint in the MP, which is \(\sum_r \lambda_{ir}=1\), doesn't get any columns passed, as it just ensures that there is in total no more than one roster (cumulative, as fractional assignments are allowed due to the relaxation) per nurse. So my current problem is as follows: I get the optimal values of the SP \(motivation_{its}^*\), which should then be added to the first (quadratic) demand constraint of the MP as columns. However, this does not work because of the quadratic nature of this demand constraint. I hope you now understand the problem a little better.

    0

Please sign in to leave a comment.