NPL problem with sum of squares and radical sign

回答済み

Zekun Duan

2023年11月08日 13:44

• 
• 

The objective function is shown in the following picture. The highlighted blue parts refer to the modulus of vectors, which needs to sum the squares of variables and then root them out. The variables of this function are two binary matric X and Y, where x_{ij} and y_{ij} are the corresponding element, respectively. This objective function is very complex and cannot be solved directly by GUROBI. I want to konw how to transform this objective funtion to be suitiable to use GUROBI to solve the optimal solution.

0

• 

  Mario Ruthmair

  • Gurobi Staff

  2023年11月09日 15:24

  Hi Zekun,

  The main idea is to decompose the objective function into basic parts, introduce helper variables and additional equality constraints for those parts, and finally rebuild the expression with those helper variables.

  Here are a few examples:

  • Products of variables with >= 3 factors: Gurobi only supports quadratic terms, but terms of higher order can be represented with additional variables. For example,

  x1 * x2 * x3 * x4 
  ==
  x1 * y
  subject to
  y = x2 * z
  z = x3 * x4

  • Fractions:

  1 / x
  ==
  y
  subject to
  1 = x * y

  • Roots:

  sqrt(x)
  ==
  y
  subject to
  y * y = x

  • Norms: You could probably model norms similar to the examples above, probably with a few more helper variables. Alternatively, Gurobi models norms for you using the norm general constraint methods, see here.

  If I did not miss anything, you should be able to model your objective function with the abovementioned ingredients.

  Best regards,
  Mario

  0

サインインしてコメントを残してください。