or-tools user manual / documentation

[Otto Dandenell]

Hi,

Firstly, I want to thank the creators of the or-tools library for having done an excellent job.

That said, such a rich tool would be much more usable if the documentation were more complete.

E.g. the chapter in the user manual concerning custom constraints consists of a few headlines with empty sections:

http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/custom_constraints.html

Also, the .NET port lacks XML comments describing classes, methods and arguments. Having such documentation would be very valuable when writing client code inside Visual Studio.

I'm hoping this could be a prioritized area for further development.

Regards

/ Otto Dandenell

[Laurent Perron]

Hi

Unfortunately we depends on swig to generate the C# libraries.

And swig does not import documentations.

In the meantime, I will try to re-run the C++ reference manual to get a clean state.

For writing a constraint, I would recommend reading the dobble_ls c++ example.

Thanks

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

[Otto Dandenell]

Thanks, Laurent,

I can't find any dobble_ls example, but perhaps you mean dummy_ls?

Having re-read chapter 5, I think that rather than a custom constraint, I need a custom IntValue Selector / strategy.

I'm not sure I understand how to implement an IndexEvaluator2 callback as described at:

http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/search_primitives/basic_working_phases.html#callbacks-to-the-rescue

The example code files mentioned at the top of:

http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/search_primitives.html

are nowhere to be found. 

There is no chapter 5 at:

http://or-tools.googlecode.com/svn/trunk/documentation/tutorials/cplusplus/

So, any suggestions?

Regarding the IndexEvaluator2:

Should the callback return an int64? or is the result of the callback in the last argument?

And what is the result supposed to be; a "score" or the index of an actual value?

Regards

/ Otto

[Laurent Perron]

No, I meant or-tools/examples/cpp/dobble_ls.cc

Thanks

[Sylvain Ducomman]

Hi Otto,

For create a custom constraint, you need just to redefine two methods of the class Constraints.

The Post method and the InitialPropagate.

The Post method enable to attach a demon on the variables : i.e. you decide when the InitialPropagate will be called (it’s when the variable change of domain or only when the bound have changed…)

After you need to redefine InitialPropagate, in this method you just create your propagator and assigne values to variables.

If is not a custom constraint you need, but a IntValue Selector / strategy, I think you need a DecisionBuilder.

The DecisionBuilder decides which variables to select with which value in the search tree.

For create a custom DecisionBuilder, you just need to redefine one method of DecisionBuilder : the Next method.

Next method return a decision, i.e. you assign a value on a variable ( example with this method AssignVariableValue(x, 3), the next decision will be x=3).

For call the DecisionBuilder, you don’t need the method MakePhase. You just call your own DecisionBuilder (example db = new DecisionBuilder(…)

Finally, for use the IndexEvaluator2 callback, you don’t need really implement this. You just create a function with the parameters  accepted by callback, and call the function "NewPermanentCallback(yourFunction) »

You can fin a lot of example where callback is use, and I don’t know how to implement an IndexEvaluator2 but I think it’s not necessary.

I hope I help you and that my english is not so bad.

Best regards,

—

Sylvain Ducomman

[Otto Dandenell]

Hi,

Thanks for the pointers,

I am looking into using the callback (regardless of exactly how it is bound to the decision builder).

Now, I create a custom callback class which inherits from the C# base class

LongResultCallback2

It exposes the virtual method
    long Run(Int64 arg0, Int64 arg1)
which I override.

I interpret arg0 to be the index of the current decision variable in the Intvar[] passed to MakePhase, so I make sure that the custom class gets a reference to that array in its constructor.

Thus, I can lookup the current decision variable by doing:

IntVar var = vars[arg0].

I interpret arg1 to be the index, in the domain of my variable var, which I am supposed to evalute. That is: my callback function is supposed to score this value and tell the decision builder if this value should be selected before other values. Correct?

But I cannot find a quick way to access, by index, the values of the domain.

The one suggestion I have is to create a domain interator by doing:

            int iterationIndex = 0;
            IntVarIterator domainIterator = vars[arg0].MakeDomainIterator(false);
            for (domainIterator.Init(); domainIterator.Ok(); domainIterator.Next())
            {
                if (iterationIndex == arg1)
                {
                    long domainValue = domainIterator.Value();
 
                    // Evaluate this value and return a low score if we want this value to be selected
                }
                iterationIndex++;
            }

Am I on the right track here?

The documentation at
http://or-tools.googlecode.com/svn/trunk/documentation/reference_manual/or-tools/src/constraint_solver/classoperations__research_1_1IntVarIterator.html
says that the IntVarIterators are not robust to domain changes, but perhaps I do not need to worry about concurrency here?

Regards

/ Otto

[Otto Dandenell]

Ok, thanks.

[Laurent Perron]

Hi, 

arg1 is the value in the domain, not its index.

Thanks

[Otto Dandenell]

Thank you!

Regards

/ Otto

[Otto Dandenell]

Hi again,

(Please be patient with me.)

I'm making progress with the IndexEvaluator2.
It is helping my decision builder prioritize which values to try first from the domain.

In order to to so, it looks at a range of previously bound vars in my array of IntVars.

To make this more efficient (minimize looping), I would want to have a way to observe when the variables in my array are bound (or unbound) and update another array of variables acordingly.

I realise that this is done in the constraint context using Demons.
(
Specifically looking at the class

SymbolsSharedByTwoCardsConstraint

in this example:
http://or-tools.googlecode.com/svn/trunk/documentation/reference_manual/or-tools/examples/cpp/dobble__ls_8cc-source.html
)

So now my questions are:
a) Is there another way to observe the binding of a variable other than using Demons + Constraints?

b) Can I use a Demon without attatching it to a Constraint?

c) In the example, a set of IntVars are observed, and when either of them is bound, the InitialPropagate() method is called. But there is no reference to the actual variable which was bound (in the code, there is a loop over the variable array). Is there some other callback / event which includes the variable reference (or the index of the variable)?

c) will the InitialPropagate() or other similar callbacks be called then the variable is UNbound (when the decision builder backtracks in the decision tree)?

Regards

/ Otto

Sylvain Ducomman skrev 2014-07-10 09:44:

[Michael Powell]

On Thursday, July 10, 2014 7:31:03 AM UTC-5, Otto Dandenell wrote:

Hi again,

(Please be patient with me.)

Ditto for me as well.

Any responses here? On- or offline? I'm not sure the problem domain I am attempting to constrain doesn't also require some sort of custom DecisionBuilder. For me, trying to gain a better understanding as to how Variables/Values are assigned. Perhaps I need to spend more time in the docs studying DecisionBuilder.

i.e. 'A Decision represents a choice point in the search tree', doesn't sound like a complete solution, but another step, in a stack, tree, etc, along which path solution(s) are resolved? Which Decision sounds like it can either Accept, 'yes I am a valid Decision, i.e. solution', or Refute, 'no I am not a valid Decision, i.e. solution', and so on.

First of all, at every iteration, what does a "decision" represent? In my mind, that's at least one step toward satisfied-constraints. Or potentially that also represents one solution in the space of satisfied constraints. Seems like an elementary CP question to want to understand better, I know.

In the case of my problem domain, I'd like to potentially weight those decisions, and increment by +1. Not necessarily taking any mins, maxes, or even randoms. I'd like for the decision space to be a bit more deterministic than that if possible.

i.e. choose the next variable, increment by one, present that Decision to the DecisionBuilder.
 

[Michael Powell]

On Wednesday, November 19, 2014 1:51:14 PM UTC-6, Michael Powell wrote:

On Thursday, July 10, 2014 7:31:03 AM UTC-5, Otto Dandenell wrote:

Hi again,

(Please be patient with me.)

Ditto for me as well.

More documentation on Callbacks would be welcome:

http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/under_the_hood/conventions.html#idiom-callbacks

13.2.2.3. Callbacks

[Michael Powell]

On Wednesday, November 19, 2014 5:53:18 PM UTC-6, Michael Powell wrote:

On Wednesday, November 19, 2014 1:51:14 PM UTC-6, Michael Powell wrote:

On Thursday, July 10, 2014 7:31:03 AM UTC-5, Otto Dandenell wrote:

Hi again,

(Please be patient with me.)

Ditto for me as well.

More documentation on Callbacks would be welcome:

http://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/under_the_hood/conventions.html#idiom-callbacks

13.2.2.3. Callbacks

 
For example, I am not entirely sure what to do with the callbacks.

They aren't 'callbacks' in the sense that they are function pointers, true .NET delegates, can be satisfied with lambdas, although that would be great.

In fact they seem more like Listener patterns, or functors in C/C++ vocabulary, in the sense that you derive classes and implement methods on your own.

    private class TestCallback1 : LongResultCallback1
    {
        public override long Run(long arg0)
        {
            return base.Run(arg0);
        }
    }

    private class TestCallback2 : LongResultCallback2
    {
        public override long Run(long arg0, long arg1)
        {
            return base.Run(arg0, arg1);
        }
    }

Which is fine, but along which lines, would be helpful to know what arg0 and arg1 are, what the purpose(s) of Run are. In fact more aptly named arguments would be better, if possible.

Indeed, a more descriptive name of the class/function would be better, than "LongResultCallback1" or "...2" would be helpful. That's not altogether descriptive. Even the parameter names in MakePhase only somewhat help to clarify their purpose, but for their inconsistencies themselves.

As a side note, other .NET wrappers, like IKVM for Java, for example, have similar issues like this and a hard time naming parameters. Although not IKVM, I think, but ones like it, in the a similar solution space.

Probably a patch would be helpful along these lines, but that isn't my focus for the moment.

[Otto Dandenell]

Michael Powell skrev den 2014-11-20 01:11:
> For example, I am not entirely sure what to do with the callbacks.
>
> They aren't 'callbacks' in the sense that they are function pointers,
> true .NET delegates, can be satisfied with lambdas, although that would
> be great.

I noticed from the previous thread something which Sylvain Ducomman wrote:
"Finally, for use the IndexEvaluator2 callback, you don’t need really
implement this. You just create a function with the parameters accepted
by callback, and call the function "NewPermanentCallback(yourFunction)"

I haven't tried this, but perhaps the yourFunction argument can be a lambda?

> In fact they seem more like Listener patterns, or functors in C/C++
> vocabulary, in the sense that you derive classes and implement methods
> on your own.
>
> private class TestCallback1 : LongResultCallback1
> {
> public override long Run(long arg0)
> {
> return base.Run(arg0);
> }
> }
>
> private class TestCallback2 : LongResultCallback2
> {
> public override long Run(long arg0, long arg1)
> {
> return base.Run(arg0, arg1);
> }
> }
>
> Which is fine, but along which lines, would be helpful to know what arg0
> and arg1 are, what the purpose(s) of Run are. In fact more aptly named
> arguments would be better, if possible.

I am not entirely sure if you are only arguing for better documentation
here or if you really need instructions? If the latter, here are my
thoughts:

In Testcallback2.Run(), arg0 is the index of a decision variable and
arg1 is a value to evaluate.

If you have told MakePhase to use (an instance of) TestCallback2 as the
IntValueStrategy, this is what will happen:

a) The IntVarStategy decides to branch on a variable at indexIV.

b) The solver (not sure if this is technically correct, it may be some
other component responsible) then looks up what values are still valid
in the domain if the decision variable.

c) For each of the valid values, the solver will call
myTestCallback2.Run(), passing in the arguments arg0 = indexIV, arg1 =
[the value to evaluate].

d) For each call in c, the Run() function returns a (arbitrary) value. A
low return value means: try this first. If two domain values are scored
the same and there is no tie-breaking function defined, then the solver
will select the lower domain value.

e) After all calls in [c] have been made, the solver tries to apply the
domain value with the lowest score to the decision variable, which will
trigger a bunch of propagations. If any constraint is then broken, the
decision is refuted and the solver backtracks in the decision tree.
Otherwise it is committed and the solver gets the next IntVar to branch
on from the IntVarStrategy (go back to a)

So, in essence, TestCallback2.Run() is a sorting function.

Since TestCallback2 is a class, it may contain fields to remember
previous decisions and make smarter choices.

In the implementation I have made for creating sports match schedules, I
pass a reference to the array of decision variables to the constructor
of the class, which means that I can inspect all variables to see if
they are bound (and to which values) and adjust my evaluation accordingly.

Regards.

/ Otto D

[Michael Powell]

On Thursday, November 20, 2014 3:31:20 AM UTC-6, Otto Dandenell wrote:

Michael Powell skrev den 2014-11-20 01:11:
> For example, I am not entirely sure what to do with the callbacks.
>
> They aren't 'callbacks' in the sense that they are function pointers,
> true .NET delegates, can be satisfied with lambdas, although that would
> be great.

I noticed from the previous thread something which Sylvain Ducomman wrote:
"Finally, for use the IndexEvaluator2 callback, you don’t need really
implement this. You just create a function with the parameters  accepted
by callback, and call the function "NewPermanentCallback(yourFunction)"

I'm not sure what you mean, "IndexEvaluator2" callback.

Is this a MakePhase parameter?

The only thing that looks even remotely close to a comparator, functional callback, is: 'SWIGTYPE_p_ResultCallback3T_bool_long_long_long_long_long_long_t'. I am starting to see a trend here...

Am I the only one here that sees a difficulty understanding what that is supposed to represent? I'll have a gander at the online docs, but I wonder if that couldn't be captured better.

For instance in C/C++ it is possibly to typedef a std::function with a proper name, no? Don't know how much support there is for that sort of thing in SWIG, would be the only trick.
 

I haven't tried this, but perhaps the yourFunction argument can be a lambda?


> In fact they seem more like Listener patterns, or functors in C/C++
> vocabulary, in the sense that you derive classes and implement methods
> on your own.
>
>      private class TestCallback1 : LongResultCallback1
>      {
>          public override long Run(long arg0)
>          {
>              return base.Run(arg0);
>          }
>      }
>
>      private class TestCallback2 : LongResultCallback2
>      {
>          public override long Run(long arg0, long arg1)
>          {
>              return base.Run(arg0, arg1);
>          }
>      }
>
> Which is fine, but along which lines, would be helpful to know what arg0
> and arg1 are, what the purpose(s) of Run are. In fact more aptly named
> arguments would be better, if possible.

I am not entirely sure if you are only arguing for better documentation
here or if you really need instructions? If the latter, here are my
thoughts:

More aptly named callbacks / methods / arguments would in itself be better documented, instructive, don't you think?

I understand you are not the maintainer, so this observation is more for the maintainers.
 

In Testcallback2.Run(), arg0 is the index of a decision variable and
arg1 is a value to evaluate.

If you have told MakePhase to use (an instance of) TestCallback2 as the
IntValueStrategy, this is what will happen:

a) The IntVarStategy decides to branch on a variable at indexIV.

b) The solver (not sure if this is technically correct, it may be some
other component responsible) then looks up what values are still valid
in the domain if the decision variable.

Solver is the parent, umbrella. You are correct, connecting the dots, technically I think it's the DecisionBuilder that is orchestrating things at this point in discussion, I believe.
 

c) For each of the valid values, the solver will call
myTestCallback2.Run(), passing in the arguments arg0 = indexIV, arg1 =
[the value to evaluate].

I see what's going on under the hood. The function names have unnamed arguments themselves. Which is fine in C/C++ code, but translates to ambiguous interpretation, especially in a declarative domain such as CP.
 

d) For each call in c, the Run() function returns a (arbitrary) value. A
low return value means: try this first. If two domain values are scored
the same and there is no tie-breaking function defined, then the solver
will select the lower domain value.

Understood.
 

e) After all calls in [c] have been made, the solver tries to apply the
domain value with the lowest score to the decision variable, which will
trigger a bunch of propagations. If any constraint is then broken, the
decision is refuted and the solver backtracks in the decision tree.
Otherwise it is committed and the solver gets the next IntVar to branch
on from the IntVarStrategy (go back to a)

So, in essence, TestCallback2.Run() is a sorting function.

Since TestCallback2 is a class, it may contain fields to remember
previous decisions and make smarter choices.

In the implementation I have made for creating sports match schedules, I
pass a reference to the array of decision variables to the constructor
of the class, which means that I can inspect all variables to see if
they are bound (and to which values) and adjust my evaluation accordingly.

Understood. I would need to teach my callbacks by telling them what they need to know.
 

Regards.

/ Otto D

[Laurent Perron]

Actually, 

callbacks predates std::functions, these are just abstract classes with a Run() method. These callbacks are wrapped in python, java, C#.

A good example in C# is the RandomManhattan class in examples/csharp/cstsp.cc

To evaluate a variable, you need to subclass (in C#) LongResultCallback1. The Run() methods returns a long which is the evaluation of the variable, it takes as input another long that is the index of the variable to evaluate.

See src/constraint_solver/constraint_solver.h with references to IndexEvaluator1, 2, 3.

In C#, these are wrapped into LongResultCallback1, 2, 3.

I hope this helps.

--Laurent

--

[Michael Powell]

On Thu, Nov 20, 2014 at 6:45 AM, Laurent Perron
<laurent...@gmail.com> wrote:
> Actually,
>
> callbacks predates std::functions, these are just abstract classes with a
> Run() method. These callbacks are wrapped in python, java, C#.
> A good example in C# is the RandomManhattan class in
> examples/csharp/cstsp.cc
>
> To evaluate a variable, you need to subclass (in C#) LongResultCallback1.
> The Run() methods returns a long which is the evaluation of the variable, it
> takes as input another long that is the index of the variable to evaluate.

I think I see, it's a matter of SWIG processing.

This is in the online help, for example:

http://or-tools.googlecode.com/svn/trunk/documentation/reference_manual/or-tools/src/constraint_solver/classoperations__research_1_1Solver.html#7f0d352629d2977405e67c85154b0081

DecisionBuilder * operations_research::Solver::MakePhase ( const
IntVar *const * vars,
int size,
IndexEvaluator1 * var_evaluator,
IndexEvaluator2 * val_eval,
IndexEvaluator1 * tie_breaker
)

> See src/constraint_solver/constraint_solver.h with references to
> IndexEvaluator1, 2, 3.
> In C#, these are wrapped into LongResultCallback1, 2, 3.

"wrapped into" ? in the sense SWIG is wrapping them.

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

[Michael Powell]

On Thu, Nov 20, 2014 at 7:25 AM, Michael Powell <mwpow...@gmail.com> wrote:
> On Thu, Nov 20, 2014 at 6:45 AM, Laurent Perron
> <laurent...@gmail.com> wrote:
>> Actually,
>>
>> callbacks predates std::functions, these are just abstract classes with a
>> Run() method. These callbacks are wrapped in python, java, C#.
>> A good example in C# is the RandomManhattan class in
>> examples/csharp/cstsp.cc
>>
>> To evaluate a variable, you need to subclass (in C#) LongResultCallback1.
>> The Run() methods returns a long which is the evaluation of the variable, it
>> takes as input another long that is the index of the variable to evaluate.
>
> I think I see, it's a matter of SWIG processing.
>
> This is in the online help, for example:
>
> http://or-tools.googlecode.com/svn/trunk/documentation/reference_manual/or-tools/src/constraint_solver/classoperations__research_1_1Solver.html#7f0d352629d2977405e67c85154b0081
>
> DecisionBuilder * operations_research::Solver::MakePhase ( const
> IntVar *const * vars,
> int size,
> IndexEvaluator1 * var_evaluator,
> IndexEvaluator2 * val_eval,
> IndexEvaluator1 * tie_breaker
> )

Still not sure what arg0 and arg1 are in callback #2.

For callback #1, I'm not sure one can adequately know the result of a
single thing without knowing what it is being compared with.

I'll use the .NET reference as a paradigm.

http://msdn.microsoft.com/en-us/library/system.icomparable.compareto(v=vs.110).aspx

The CompareTo method is similar in nature, compares the implementing
class with another object, which returns:

Value | Meaning
Less than zero | This instance precedes obj in the sort order.
Zero | This instance occurs in the same position in the sort order as obj.
Greater than zero | This instance follows obj in the sort order.

Along similar lines, callback #2 evaluates values? How to know where
the value(s) have been?

Or perhaps I need to add Demons to the IntVar(s) WhenBound, to track
that aspect, i.e. to further inform callback #2?

[Laurent Perron]

It depends, 

var_evaluator: the arg is the index of the variable, it returns a evaluation. The solver selects the first variable with the minimum evaluation.

value_evaluator: the index of the variable, then the value inside the domain of the variable.

tie_breaker: the index of the variable.

I hope this helps.

--Laurent

>>> email to or-tools-discuss+unsubscribe@googlegroups.com.

>>> For more options, visit https://groups.google.com/d/optout.
>>
>> --
>> 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/U4exb0bixcI/unsubscribe.
>> To unsubscribe from this group and all its topics, send an email to

>> or-tools-discuss+unsubscribe@googlegroups.com.

>> For more options, visit https://groups.google.com/d/optout.

--

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-discuss+unsubscribe@googlegroups.com.

[Otto Dandenell]

>> See src/constraint_solver/constraint_solver.h with references to
>> IndexEvaluator1, 2, 3.
>> In C#, these are wrapped into LongResultCallback1, 2, 3.
>
> "wrapped into" ? in the sense SWIG is wrapping them.

Yes. The IndexEvaluator1 is not a public class in .NET, but instead
there is a LongResultCallback1 which appears to do the same thing. I am
only assuming that by some SWIG magic the underlying native class is
instantiated and its methods called.

I know nothing about SWIG so I am only drawing conclusions from the
available documentation and discussions.

Regards

/ O

[Laurent Perron]

Exactly, 

IndexEvaluator1/2/3 are mapped to LongResultCallback1/2/3

Thanks

--
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-discuss+unsubscribe@googlegroups.com.