[SCIP] Gain performance with plugin

[Julain Stebler]

Dear Gregor

Thank you for your time and help. My real name is Nicolas but the Mail
address is my 'spam' address. Because I did not know how many mails I get,
when I signed up for the Mailling list. I hope this is ok.

I tried the very low negative checkpriority but I am not sure if other
constraints are really checked before. For my profiling I printed the
solution out. And at the beginning the constraint, which are defined in the
code, are violated.
The first solution is empty? the next 5 or 6 has the same number in every
state.
E.g 4x4:
5 5 5 5      next:    3 3 3 3
5 5 5 5                  3 3 3 3
5 5 5 5                  3 3 3 3
5 5 5 5                  3 3 3 3

model.includeConshdlr(conshdlr, "election",
"Election", chckpriority=-100,
needscons=False)
model.setBoolParam("misc/allowdualreds", False)

So I am not sure if I done this right.
I also checked the time for my Constraint-handler. And the average time to
check if it is feasible or not is 0.5 milliseconds. This should be ok.

I think there are too much possibilities to check. I studied the additional
methods for a constraint-handler and found CONSRESPROP. But the method
never get called? What is the trigger to call this method?

def consresprop(self):
print("consresprop")
pdb.set_trace()

I also think that I can reduce the numbers of possibilities when I add some
new constraints during the process.
For example with a 3x3:
1 2 1    also not feasible:  2 1 2    3 1 3
1 3 3                                 2 3 3    3 2 2
2 3 2                                 1 3 1    1 2 1 .....

This is not a feasible solution cause the 2 is not connected to the others
2. If we would replace the number two with one and the ones with two it is
also not a feasible solution. So if we found a not feasible solution we can
propagate this for all other combinations. I will try this the next days.

I also added the code to a Github repository (
https://github.com/bhzunami/clip).
You can find the Constraint-handler here:
https://github.com/bhzunami/clip/blob/master/electionHandler.py
And the Problem here:
https://github.com/bhzunami/clip/blob/master/election_problem.py

So If anybody else has a good idea I am very happy to hear it.

Nicolas

On Thu, Apr 6, 2017 at 12:50 PM Gregor Hendel <hendel at zib.de> wrote:

> 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 listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170409/3f346e2a/attachment.html>