[SCIP] Gain performance with plugin

[Gregor Hendel]

Dear Nicolas (or Julian?),

I am happy to hear that you like the python interface. We like it, too.

Regarding the callbacks: There are four fundamental callbacks of a 
constraint handler, namely consCheck, consEnfoLP, consEnfoPS, and 
consLocks. These are described in the section "Fundamental callbacks" of 
the constraint handler implementation documentation that you mentioned.

The consCheck method is called by SCIP for every solution that must be 
checked, which is usually the solution of the LP relaxation (if all 
binary variables have integer values) or solutions that are found by the 
primal heuristics of SCIP.

The source of a performance bottleneck in your case may be the presence 
of too many calls of the check routine, or an expensive algorithm used 
within your check routine, or a combination of both.
I took the time and scanned through your code, but I couldn't see an 
obvious performance flaw in the way you check your solution.

You can only partially get around the number of calls to the check 
method; The callback will be called every time SCIP needs to know if a 
solution is feasible regarding the constraints. However, if you assign 
your constraint handler a very low negative checkpriority, it will only 
be called if the feasibility of the remaining constraints has been 
checked already.
This means SCIP will skip (hehe) the expensive check of your constraint, 
if a solution already violates one of the linear or integrality constraints.

I suggest you use a performance profiler (in your case, profiling the 
python code part should be sufficient) to spot algorithmic parts of your 
check that can be improved.
By using the Python interface, some computational overhead compared to 
plain C/C++ is unavoidable. Especially, an extensive use of dictionary 
lookups (instead of arrays) is very pythonic, but may result in a 
computational disaster, IMHO. The same holds for return types, I would 
definitely use tuples instead dictionaries, wherever I have the freedom.

I hope this gives you some hints how to further optimize your application.

Happy profiling,
Gregor



Am 30.03.2017 um 21:28 schrieb Julain Stebler:
> Hello Everybody
>
> I like your Python interface for the SCIP Optimization Suite. And I 
> would like to learn more about the plugins. For that I try to solve 
> following Election Problem:
>
> I have a grid with the size of 10x10 (100 pieces/states). Every piece 
> represents a state and every state has votes.
> Votes for democrats and votes for republicans. The votes for the 
> republicans are two times higher.
> The sum of ten states defines which party wins the vote for the 
> constituency. So there are 10 constituency.
> The goal is that the party with the lower number of votes wins the 
> most  constituency more precisely wins the election.
> Now to make the whole part more trickier, I want that the constituency 
> are all aside. Which means the constituency grid should look something 
> like this:
> [1, 1, 1, 1, 2, 2, 2, 5, 5, 6
>  1, 1, 1, 1, 1, 2, 2, 2, 5, 6
>  1, 4, 4, 4, 4, 2, 2, 2, 5, 6
>   3, 3, 4, 4, 4, 2, 5, 5, 5,6
>  ....
>  ....]
> The number represents the number of the constituency which won the 
> election.
>
> To check if the winning constituency are aside I would like to use my 
> own constraint handler. But I do not know which method 
> (http://scip.zib.de/doc/html/CONS.php) I should use.
> At the moment I implemented 'conscheck' and 'consenfolp'. But the time 
> to check the correctness is way to long.
> I am not sure if this is possible, but I would like to call my handler 
> for every solution the solver sets the constituency of a state.
>
> The code for my election problem with the handler can be found here:
> https://gist.github.com/bhzunami/54cbc4f5ce37ba88e8c91d4ece0a4b56
>
> If there is a better idea I am happy to hear it.
> If something is not clear please ask back or make some comments in the 
> gist.
>
> Thank you for your help and time.
>
> Kind regards
> Nicolas
>
>
>
>
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170406/884bcc2f/attachment.html>