Adding SOCP contraints

回答済み

Samuel Alvite

2021年12月14日 12:58

• 
• 

Hello,

I'm working on a polynomial programming optimization tool that so far uses a branch-and-bound algorithm to solve linear relaxations of the original problem. I'm using the Gurobi C++ API and I want to add SOCP contraints to tighten those relaxations without incurring too much additional complexity. A generic example of such a constraint I would like to add would be:

Reading the reference manual I didn't see a clear way of adding this type of constraints. It seemed to me that maybe adding a quadratic constraint like the one below would suffice, provided I set the parameter PreMIQCPForm to 1 so that these constraints get transformed into second-order cone contraints.

If that is the way to go, what would be the correct approach to do that? I could expand both sides of the constraint and fully capture the constraint as one of the type GRBQConstr by having both sides as GRBQuadExpr&, but I also could use GRBaddgenconstrPow so I don't have to expand the terms, but that would require me to work with General Constraints. I'm not sure if expanding would have any effect on the quadratic-to-second-order-cone transformation I mentioned earlier, or if the second approach is worse in terms of efficiency. What would be the best way to add these constraints?

If the approach is entirely wrong, could you point me towards the right direction?

Best regards, Samuel.

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 02:42 編集済み

  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?.
• 

  Jaromił Najman

  • Gurobi Staff

  2021年12月17日 13:13

  Hi Samuel,

  Providing the constraint in the second form would be the way to go here.

  You could introduce a auxiliary variables for the \(\frac{a\pm b}{2}\) terms and then add the SOC constraint explicitly. Your code could look something like

  GRBVar a  = model.addVar(0.0, GRB_INFINITY, 0.0, GRB_CONTINUOUS, "a");
  GRBVar b  = model.addVar(0.0, GRB_INFINITY, 0.0, GRB_CONTINUOUS, "b");
  GRBVar c  = model.addVar(0.0, GRB_INFINITY, 0.0, GRB_CONTINUOUS, "c");
  GRBVar z1 = model.addVar(0.0, GRB_INFINITY, 0.0, GRB_CONTINUOUS, "z1");
  GRBVar z2 = model.addVar(-GRB.INFINITY, GRB_INFINITY, 0.0, GRB_CONTINUOUS, "z2");
  
  model.addConstr(0.5*a + 0.5*b - z1 == 0, "aux1");
  model.addConstr(0.5*a - 0.5*b - z2 == 0, "aux2");
  model.addQConstr(z1*z1 - c*c - z2*z2 >= 0, "socc")

  You will probably want to construct bigger constraints. In this case, you should use a GRBQuadExpr. When doing so you should avoid using a loop to compute

  expr = expr + x*x

  as described in the documentation of GRBQuadExpr. Using the addTerm in a loop or the addTerms method is the way to go here.

  Best regards, 
  Jaromił

  0

投稿コメントは受け付けていません。