root mean square

[Martin Genet]

Hello,

I have a bunch of integer variables, and would like to minimize their root mean square.Is there some kind of "trick" to do that in OR-Tools? Could not find any in the examples… Thanks in advance for any pointer!

Martin

[Laurent Perron]

which solver ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/61d50ef8-b2f6-49c6-9e9a-bb871be78006n%40googlegroups.com.

[Martin Genet]

For now I am using CP-SAT, sorry for not mentioning it in my first message.

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/Kr9TJUDCGNQ/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeZAVerfGB5DnOjX6vO6j%3DxJH-qPA98e%2B44mBD3L39ag7g%40mail.gmail.com.

[Laurent Perron]

the spread_robot example implements the square root with variable precision.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f53244e8-a712-4a6b-b619-1b1e63e08fdf%40polytechnique.edu.

[Martin Genet]

Thank you!

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeaMwN%2BtU831cES8VcfULZH5e-1QZs-1-6fWRKc%3DA_H_KQ%40mail.gmail.com.

[A S]

Dear Martin,
it might be helpful to use AddMultiplicationEquality
https://github.com/OptimizationExpert/Pyomo/blob/main/MeanSquare.ipynb
sum the square values of x --> y = sum_n x*x once it is solved then you can use this formula 

 

Alireza Soroudi

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/4d702e08-9c87-4a96-8fad-19f9278a351a%40polytechnique.edu.

[Martin Genet]

Thanks to Alireza as well!

I understand the "trick" to use another series of variables together with `AddMultiplicationEquality` to define the squares, but I also need a "trick" to manage the square root (reason is: my objective is actually a composite of multiple objectives, and the scaling is important). I tried this:

n = 2

x_min = [ 1]*n

x_max = [10]*n

model = cp_model.CpModel()

x = {i:model.NewIntVar(x_min[i], x_max[i], f"x_{i}") for i in range(n)}

x_sq = {i:model.NewIntVar(x_min[i]**2, x_max[i]**2, f"x_sq_{i}") for i in range(n)}

for i in range(n):

model.AddMultiplicationEquality(x_sq[i], (x[i], x[i]))

mse = model.NewIntVar(np.mean(np.square(x_min), dtype=int), np.mean(np.square(x_max), dtype=int), f"mse")

model.AddDivisionEquality(mse, sum(x_sq), n)

rmse = model.NewIntVar(int(np.floor(np.sqrt(np.mean(np.square(x_min))))), int(np.ceil(np.sqrt(np.mean(np.square(x_max))))), f"rmse")

model.AddMultiplicationEquality(mse, (rmse, rmse))

model.Minimize(rmse)

solver = cp_model.CpSolver()

status = solver.solve(model)

print(f"Status = {solver.status_name()}")

print(f"Objective = {solver.objective_value}")

print("")

for i in range(n):

print(f"x_{i} = {solver.Value(x[i])}")

But it does not work: with `x_min = [ 0]*n` I am getting the expected null solution, but with `x_min = [ 1]*n` I am getting `Status = INFEASIBLE`. I guess it makes sense, since in general there is no "integer" square root to an integer… So I tried this:

n = 2

x_min = [ 1]*n

x_max = [10]*n

model = cp_model.CpModel()

x = {i:model.NewIntVar(x_min[i], x_max[i], f"x_{i}") for i in range(n)}

x_sq = {i:model.NewIntVar(x_min[i]**2, x_max[i]**2, f"x_sq_{i}") for i in range(n)}

for i in range(n):

model.AddMultiplicationEquality(x_sq[i], (x[i], x[i]))

mse = model.NewIntVar(np.mean(np.square(x_min), dtype=int), np.mean(np.square(x_max), dtype=int), f"mse")

model.AddDivisionEquality(mse, sum(x_sq), n)

rmse = model.NewIntVar(int(np.floor(np.sqrt(np.mean(np.square(x_min))))), int(np.ceil(np.sqrt(np.mean(np.square(x_max))))), f"rmse")

rmse_sq = model.NewIntVar(np.mean(np.square(x_min), dtype=int), np.mean(np.square(x_max), dtype=int), f"rmse_sq")

model.AddMultiplicationEquality(rmse_sq, (rmse, rmse))

rmse_diff = model.NewIntVar(-int(np.ceil(np.sqrt(np.mean(np.square(x_max))))), +int(np.ceil(np.sqrt(np.mean(np.square(x_max))))), f"rmse_diff")

model.Add(rmse_diff == mse - rmse_sq)

rmse_err = model.NewIntVar(0, int(np.ceil(np.sqrt(np.mean(np.square(x_max))))), f"rmse_err")

model.AddMultiplicationEquality(rmse_err, (rmse_diff, rmse_diff))

model.Minimize(rmse + rmse_err)

solver = cp_model.CpSolver()

status = solver.solve(model)

print(f"Status = {solver.status_name()}")

print(f"Objective = {solver.objective_value}")

print("")

for i in range(n):

print(f"x_{i} = {solver.Value(x[i])}")

But again I am getting `Status = INFEASIBLE`. Any idea on the proper way to deal with this?

[blind.line]

If I’m reading it right, your variable “mse” is maybe? not allowing a possible value?  When you define it, the min and max value intvar are defined correctly, but doesn’t quite match the next line of code. What if the solver has a solution with very low values or something?

I’d try 0 to maxint for all the intermediate variables first to see if that is the issue.

James

On Jul 22, 2024, at 06:29, Martin Genet <martin...@polytechnique.edu> wrote:

 Thanks to Alireza as well!

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5774e749-36fc-4b71-93a5-4b58922f81e0%40polytechnique.edu.