Treatment of float variables

[lionel.r...@ensam.eu]

I am getting started with or-tool and I only have seen the declaration of integer variables.

Is that possible to treat other kind of variables : float variables, discrete variables.... (I did not find it in the documentation)

So far to treat float variables, I am making a transformation of float to integer via a MakeProd(var, n*10) where n is the number of required decimals.

Is that a good idea ?

Best regards

[Michael Powell]

On Friday, November 21, 2014 4:13:16 PM UTC-6, lionel.r...@ensam.eu wrote:

I am getting started with or-tool and I only have seen the declaration of integer variables.

Is that possible to treat other kind of variables : float variables, discrete variables.... (I did not find it in the documentation)

In my brief experience with CP, I could be wrong, but I'm not sure that OR tools, or any CP/CSP for that matter, necessarily support floating point values. CP in general tends to be geared more towards discrete, integral values.

So far to treat float variables, I am making a transformation of float to integer via a MakeProd(var, n*10) where n is the number of required decimals.

Is that a good idea ?

One answer is, 'it depends', depending on your model, what you want to represent.

For one model, I had fractional (/2, /5, etc) values, and in that case I scaled the costs accounting for lowest-common-denominator; in this case, 1/(1/sum(N)). Just remember to scale in both directions producing and consuming the model.

I ended up doing a simple cost equation: i.e. solver.Add(a*aCost+b*bCost+c*cCost==totalCost), and it worked well enough.

HTH

Best regards

[Frédéric Girod]

Hi there,

Sorry I come very late in the discussion.

I have sort of similar problem: I have 100 individuals with decimal values (ranging between 1 and 50), and I must constitute 10 groups of 10 individuals: each group must have the same average value.

So I have to handle floating values and not integer values: how to do so with OR tools ?

Best,

Fred

[Laurent Perron]

Hi, 

same average value is most likely impossible.

So you want average value with an epsilon.

In that case, you can always constraint the sum.

xi, total sum is S

create x_i_j if xi belong in group j

for all j, sum x_i_j = 10

for all j, s / 10 - e <= sum x_i_j * Vi <= s / 10 + e 

and minimize e

But beware, this is a very hard problem as it is purely combinatorial.

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.
For more options, visit https://groups.google.com/d/optout.

[Frédéric Girod]

Hi Laurent,

Many thanks for this.

Here the code in Python I have started to write, but how would you express the objective (minimize e) ?

from ortools.constraint_solver import pywrapcp

solver = pywrapcp.Solver("individuals_grouping")

boo_x_i_j = {}

for i in range(1,101):

    for j in range(1,11):

        boo_x_i_j[(i, j)] = solver.BoolVar('x%d belongs to group %d' % (i, j))

for j in range(1,11):

    solver.Add(solver.Sum([boo_x_i_j[(i, j)] for i in range(1,101)]) == 10)

for j in range(1,11):

    solver.Add (solver.Sum([boo_x_i_j[(i, j)]*value[i] for i in range(1,101)]) >= (v/10) - e)

    solver.Add (solver.Sum([boo_x_i_j[(i, j)]*value[i] for i in range(1,101)]) <= (v/10) + e)

Thanks.

Best,

Frederic

[Laurent Perron]

from __future__ import print_function

from ortools.sat.python import cp_model

model = cp_model.CpModel()

boo_x_i_j = {}

for i in range(100):

    for j in range(10):

        boo_x_i_j[(i, j)] = model.NewBoolVar('x%d belongs to group %d' % (i, j))

e = model.NewIntVar(0, 5, 'epsilon')

values = [i + 1 for i in range(100)]

sum_of_values = sum(values)

average_value = sum_of_values / 10

for j in range(10):

    model.Add(sum(boo_x_i_j[(i, j)] for i in range(100)) == 10)

for i in range(100):

    model.Add(sum(boo_x_i_j[(i, j)] for j in range(10)) == 1)

for j in range(10):

    model.Add(-e <= sum(boo_x_i_j[(i, j)]*values[i] for i in range(100)) -

              average_value <= e)

model.Minimize(e)

solver = cp_model.CpSolver()

status = solver.Solve(model)

print('Optimal epsilon: %i' % solver.ObjectiveValue())

print('Statistics')

print('  - conflicts : %i' % solver.NumConflicts())

print('  - branches  : %i' % solver.NumBranches())

print('  - wall time : %f s' % solver.WallTime())

groups = {}

for j in range(10):

    groups[j] = []

for i in range(100):

    for j in range(10):

        if solver.Value(boo_x_i_j[(i, j)]):

            groups[j].append(values[i])

for j in range(10):

    print ('group %i: average = %0.2f [' % (j, sum(groups[j]) / 10.0), end='')

    for v in groups[j]:

        print(' %i' % v, end='')

    print(' ]')

Displays:

Optimal epsilon: 0

Statistics

  - conflicts : 2230

  - branches  : 13847

  - wall time : 1.077324 s

group 0: average = 50.50 [ 5 6 19 26 27 77 83 84 87 91 ]

group 1: average = 50.50 [ 1 30 42 43 52 58 59 65 76 79 ]

group 2: average = 50.50 [ 7 13 38 51 53 55 56 63 81 88 ]

group 3: average = 50.50 [ 2 8 11 12 62 72 80 82 86 90 ]

group 4: average = 50.50 [ 3 4 9 17 18 69 94 95 97 99 ]

group 5: average = 50.50 [ 28 33 34 35 44 47 66 71 73 74 ]

group 6: average = 50.50 [ 14 20 21 23 25 46 68 92 96 100 ]

group 7: average = 50.50 [ 31 36 39 41 48 49 50 54 64 93 ]

group 8: average = 50.50 [ 22 32 37 40 45 57 60 67 70 75 ]

group 9: average = 50.50 [ 10 15 16 24 29 61 78 85 89 98 ]

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

[Laurent Perron]

I pushed a slightly better version here:

https://github.com/google/or-tools/blob/master/examples/python/balance_group_sat.py

Thanks

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

[Mirco Milletari]

Hi Laurent, 

To go back to the original topic of the post, can you work with float variables? 

Let us say I want to find a weight vector w_i by solving a constrained optimization problem, with sum_i w_i =1. To be more explicit, consider a portfolio construction problem 

max_w ( sum_i r_i w_i)

subject to: 

sum_{i,j} w_i S_{ij} w_j <= e

sum_i w_i =1 

where r_i is a vector of expected returns, S_{ij}  the covariance matrix, and e some threshold risk. Clearly, the weights are not integer here. Can I solve this simple problem in or-tools? How do I specify that w is a float? I did not see examples concerning this case.

Thank you! 

[Laurent Perron]

You could approximate this to fit into a discrete solver, but it seems overkill.

To me, this looks like continuous quadratic programming to me.

So any solver here: https://en.wikipedia.org/wiki/Quadratic_programming

should be fine.

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

--

[Frédéric Girod]

Gents,

I was wondering how to set a 'AllDifferent' constraint in CP-SAT ?

Because it seems 'cp_model' has no attribute 'AllDifferent' ...

Best,

Fred

[Laurent Perron]

Assuming you are in python.

https://github.com/google/or-tools/blob/a533e7ad0f95f042b6aaccd18c9c8247f50ea4db/ortools/sat/python/cp_model.py#L583

[Frédéric Girod]

Many thanks Laurent.

[Frédéric Girod]

Laurent,

How it it possible to use AddAllDifferent function on (x.A) matrix ?

For example,

for j in range(num_groups):
    model.AddAllDifferent([boo_x_i_j[(i, j)] * int(countries_ids[i]) for i in range(num_teams)])

I get this type of error:

TypeError: NotSupported: model.GetOrMakeIndex((10 * x0 belongs to group 0))

[Laurent Perron]

You need to creates integer variables equal to [boo_x_i_j[(i, j)] * int(countries_ids[i])

Now, it boo_x_i_j are booleans, then they can only take value 0 or country_ids.

Assuming countries_ids are all different, it means that at most 1 is false. Which is a simpler constraint.

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

[Frédéric Girod]

Thanks Laurent,

This is below what I did, but get the same type of error.

int_countries_i_j = {}

for i in range(num_teams):

    for j in range(num_groups):

        int_countries_i_j[(i, j)] = model.NewIntVar(0, len(countries_unique_ids), 'country%d belongs to group %d' % (i, j))

        int_countries_i_j[(i, j)] = boo_x_i_j[(i, j)] * int(countries_ids[i])

for j in range(num_groups):

    model.AddAllDifferent([int_countries_i_j[(i, j)] for i in range(num_teams)])

What did I do wrong ?

[Laurent Perron]

len ? or max(countries_unique_ids) or len() + 1

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

[Frédéric Girod]

No it doesn't change anything.

I still have the same error: TypeError: NotSupported: model.GetOrMakeIndex((11 * x0 belongs to group 0)).

[Frédéric Girod]

Hi Laurent,

Sorry I have another question:

I keep fine tuning the program (balance_group_sat.py) you did for me, and I would like to add another constraint, which that each group should have the same boo_x_i_j[(i, j)] * regions_ids[i] , which means for example, teams should come from the same region within any given group. And 3 different regions exist.

I tried several methods, but nothing is really working.

How would you do so ?

Sorry for my basic issues.

[Laurent Perron]

replace int_countries_i_j[(i, j)] = boo_x_i_j[(i, j)] * int(countries_ids[i])

by model.Add(int_countries_i_j[(i, j)] == boo_x_i_j[(i, j)] * int(countries_ids[i]))

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

[Laurent Perron]

Can you be more precise?

If you mean that a group should have only one region, I would implement it this way:

bool_var region_is_in_group[r][g]

boo_x_i_j implies the right region_is_in...

Then for each group, sum(region_is_in_group) <= 1

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

[Frédéric Girod]

Thanks.

Indeed a group should have only region, whatever it is.

Could you just elaborate a little bit more on this way to implement this ?

Because we don't know which region will be represented in each group ...

[Laurent Perron]

each member has a region.

For each group, 

  add one boolean per region: region_is_in_group

  for each member:

     member_is_in_group_var implies region_is_in_group

sum for all regions (region_is_in_group) <= 1

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

[Frédéric Girod]

Sorry Laurent for my basic questions (I'm not familiar with SAT).

I don't understand this syntax: 

for each member:

     member_is_in_group_var implies region_is_in_group

How do you link the members (boo_x_i_j) with the regions (region_is_in_group) ?

Moreover, 2 groups can belong to the same region. There are 3 regions, 10 groups for instance. The optimizer must allocate optimally among the groups.

Thanks again for your patience.

[Frédéric Girod]

Actually, this is relatively clear, but I don't see how to connect members boo_x_i_j[(i, j)] with the regions region_is_in_group[(r, j)] ...

[Frédéric Girod]

Does this syntax seem ok to you ?

region_is_in_group = {}

for j in range(num_groups):

    for k in range(num_regions):

        region_is_in_group[(k, j)] = model.NewBoolVar('region%d is in group %d' % (k+1, j))

    for i in range(num_teams):

        for k in range(num_regions):

            model.AddImplication(boo_x_i_j[(i, j)], region_is_in_group[(k, j)])

    model.Add(sum(region_is_in_group[(k, j)] for k in range(num_regions)) <= 1)

Actually the solver doesn't find any solution...

[Laurent Perron]

I miss the test when you only set region_is_in_group for the actual region of the team.

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

[Frédéric Girod]

There was a mistake in my code above. This is below an amended version:

region_is_in_group = {}

for j in range(num_groups):

    for k in range(num_regions):

        region_is_in_group[(k, j)] = model.NewBoolVar('region%d is in group %d' % (k+1, j))

        for i in range(num_teams):

            model.AddImplication(boo_x_i_j[(i, j)], region_is_in_group[(k, j)])

    model.Add(sum(region_is_in_group[(k, j)] for k in range(num_regions)) <= 1)

The solver doesn't find any solution because it puts 1 everywhere in the matrix region_is_in_group .....

I don't know how to use the model.AddImplication( ....

This is the cause of my error.

Is it more clear ?

Each group is comprised of the same region (I mean from teams stemming from the same region). There are 10 groups and 3 regions.

[Frédéric Girod]

Actually I don't know how to set region_is_in_group for the actual region of the teams .... because those 2 matrices have 2 different dimensions.

[Frédéric Girod]

Is it with model.AddBoolOr() that I could link the 2 variables ?

Help please.

[Michael Powell]

On Tue, Aug 7, 2018 at 4:05 PM, Frédéric Girod
<fred.fred...@gmail.com> wrote:
> Is it with model.AddBoolOr() that I could link the 2 variables ?

Engage brain. What are you after? If by "linking" you mean one or the
other. If 'a' and 'b' are your Boolean (IntVar) variables:

(a+b>0)

I'm not positive what that looks like off the cuff in terms of model
API or from your target language POV, i.e. if your language supports
variables, constraints, etc, falling out of operator overloads as with
C#.

Or something like,

var constraint = model.GreaterEqual(a+b,1); // yields a new IntVar c=a+b

Remember "boolean" are just "integers with 0 or non zero results" as
far as the model is concerned.

It's basically just modeled logic patterns at that point.

The API here isn't precise, but you get the point.

Can you clarify?


> Help please.
>
> --
> 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/O3z_xaMKHrM/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to

[Laurent Perron]

Actually you problem is likely to have no solution, 

you have 100 persons, 10 groups

thus 10 persons per group.

You have 3 regions, this 2 regions with 33 persons, 1 with 34 persons.

1 region per group, so 1 group with 10 persons, another one with 10 persons, and one with 3 or 4. Impossible.

You need to relax you problem.

Here is the code for regions:

# region_in_group variables.

region_in_group = {}

for g in all_groups:

    for r in all_regions:

        region_in_group[(r, g)] = model.NewBoolVar(

            'region %d is in group %d' % (r, g))

# Item is in a group implies its region is in that group.

for i in all_items:

    for g in all_groups:

        model.AddImplication(item_in_group[(i, g)],

                             region_in_group[(region[i], g)])

# Exactly one region per group.

for g in all_groups:

    model.Add(sum(region_in_group[(r, g)] for r in all_regions) == 1)

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

Le mar. 7 août 2018 à 08:06, Frédéric Girod <fred.fred...@gmail.com> a écrit :

Actually I don't know how to set region_is_in_group for the actual region of the teams .... because those 2 matrices have 2 different dimensions.

--

[Laurent Perron]

I have improved my previous model to add colors, and a min number of items of the same color in a group.

The code is still at: https://github.com/google/or-tools/blob/master/examples/python/balance_group_sat.py

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

Le mar. 7 août 2018 à 13:05, Frédéric Girod <fred.fred...@gmail.com> a écrit :

Is it with model.AddBoolOr() that I could link the 2 variables ?

Help please.

--

[Frédéric Girod]

Many many thanks for your help !

I really appreciate it.

[Frédéric Girod]

A quick question if I may again:

if I decide to prevent to persons from 2 specific countries not to be in the same group (e.g. England and Russia), why is the below constraint not working ?

for j in range(num_groups):

    model.Add(sum(boo_x_i_j[(i, j)] * (countries[i] == 'ENG') for i in range(num_teams)) * sum(boo_x_i_j[(i, j)] * (countries[i] == 'RUS') for i in range(num_teams)) == 0)  

Probably there are different ways to implement this, what's the best one ?

[Laurent Perron]

Please have a look at mizux@ answer on the (a == 0) == (b == 0) thread.

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

[Frédéric Girod]

I get mizux point, but don't know how to translate into my issue.

In my case, I cannot create conditions element-wise, because I have to sum up across my groups.

Should I use model.AddBoolAnd() to make sure my 2 conditions are fulfilled across my groups ?

[Laurent Perron]

As with regions

create variables country_in_group

do the right implication person_in_group -> country_in_group

then

for each group country1_in_group + country2_in_group <= 1

--

[Frédéric Girod]

Thanks Laurent.

[Frédéric Girod]

Hi Laurent,

I don't know if you remember the balance_group_sat project ...

The algo works very well, but ends up with quite imbalanced groups in terms of standard deviation or value gap within each group. 

I mean, the group with the strongest (outlier) value ends up with the smallest values, for some obvious reasons.

I didn't succeed to add a constraint aiming to get kind of similar standard deviation of values within each group or a constraint making sure the group with the strongest value doesn't end up with the smallest values ....

Any clever idea how to get a relatively similar dispersion as well as the same average value within each group  ?