<div dir="ltr">Dear Gregor<div><br></div><div>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.</div><div><br></div><div>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.</div><div>The first solution is empty? the next 5 or 6 has the same number in every state.</div><div>E.g 4x4:<br></div><div>5 5 5 5 next: 3 3 3 3 </div><div>5 5 5 5 3 3 3 3</div><div>5 5 5 5<span class="inbox-inbox-Apple-converted-space"> </span> 3 3 3 3</div><div>5 5 5 5<span class="inbox-inbox-Apple-converted-space"> </span> 3 3 3 3</div><div><br></div><div><div style="line-height:18px"><div style="font-family:menlo,monaco,"courier new",monospace;white-space:pre;font-size:12px">model.includeConshdlr(conshdlr, <span style="color:rgb(163,21,21)">"election"</span>,</div><div style="font-family:menlo,monaco,"courier new",monospace;white-space:pre;font-size:12px"> <span style="color:rgb(163,21,21)">"Election"</span>, chckpriority=-<span style="color:rgb(9,136,90)">100</span>,</div><div style="font-family:menlo,monaco,"courier new",monospace;white-space:pre;font-size:12px"> needscons=<span style="color:rgb(0,0,255)">False</span>)</div><div style="font-family:menlo,monaco,"courier new",monospace;white-space:pre;font-size:12px">model.setBoolParam(<span style="color:rgb(163,21,21)">"misc/allowdualreds"</span>, <span style="color:rgb(0,0,255)">False</span>)</div><div style="font-family:menlo,monaco,"courier new",monospace;white-space:pre;font-size:12px"><br></div>So I am not sure if I done this right.<br>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.<br><br></div></div><div style="line-height:18px">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?</div><div style="line-height:18px"><br></div><div style="line-height:18px"><div style="line-height:18px"><div style="font-family:menlo,monaco,"courier new",monospace;font-size:12px;white-space:pre"><span style="color:rgb(0,0,255)">def</span> consresprop(self):</div><div style="font-family:menlo,monaco,"courier new",monospace;font-size:12px;white-space:pre"> print(<span style="color:rgb(163,21,21)">"consresprop"</span>)</div><div style="font-family:menlo,monaco,"courier new",monospace;font-size:12px;white-space:pre"> pdb.set_trace()</div><div style="font-family:menlo,monaco,"courier new",monospace;font-size:12px;white-space:pre"><br></div>I also think that I can reduce the numbers of possibilities when I add some new constraints during the process. </div><div style="line-height:18px">For example with a 3x3:<br></div><div style="line-height:18px">1 2 1 also not feasible: 2 1 2 3 1 3</div><div style="line-height:18px">1 3 3 2 3 3 3 2 2</div><div style="line-height:18px">2 3 2 1 3 1 1 2 1 .....</div><div style="line-height:18px"><br></div><div style="line-height:18px">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.</div><div style="line-height:18px"><br></div><div style="line-height:18px">I also added the code to a Github repository (<a href="https://github.com/bhzunami/clip">https://github.com/bhzunami/clip</a>).<br>You can find the Constraint-handler here: <a href="https://github.com/bhzunami/clip/blob/master/electionHandler.py">https://github.com/bhzunami/clip/blob/master/electionHandler.py</a></div><div style="line-height:18px">And the Problem here: <a href="https://github.com/bhzunami/clip/blob/master/election_problem.py">https://github.com/bhzunami/clip/blob/master/election_problem.py</a></div><div style="line-height:18px"><br></div><div style="line-height:18px">So If anybody else has a good idea I am very happy to hear it.</div><div style="line-height:18px"><br></div><div style="line-height:18px">Nicolas</div></div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Apr 6, 2017 at 12:50 PM Gregor Hendel <<a href="mailto:hendel@zib.de">hendel@zib.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF" class="gmail_msg">
<div class="m_-6915722490040910444moz-cite-prefix gmail_msg">Dear Nicolas (or Julian?),<br class="gmail_msg">
<br class="gmail_msg">
I am happy to hear that you like the python interface. We like it,
too.<br class="gmail_msg">
<br class="gmail_msg">
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. <br class="gmail_msg">
<br class="gmail_msg">
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.<br class="gmail_msg">
<br class="gmail_msg">
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.<br class="gmail_msg">
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.<br class="gmail_msg">
<br class="gmail_msg">
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.<br class="gmail_msg">
This means SCIP will skip (hehe) the expensive check of your
constraint, if a solution already violates one of the linear or
integrality constraints.<br class="gmail_msg">
<br class="gmail_msg">
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.<br class="gmail_msg">
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. <br class="gmail_msg">
<br class="gmail_msg">
I hope this gives you some hints how to further optimize your
application.<br class="gmail_msg">
<br class="gmail_msg">
Happy profiling,<br class="gmail_msg">
Gregor</div></div><div text="#000000" bgcolor="#FFFFFF" class="gmail_msg"><div class="m_-6915722490040910444moz-cite-prefix gmail_msg"><br class="gmail_msg">
<br class="gmail_msg">
<br class="gmail_msg">
<br class="gmail_msg">
Am 30.03.2017 um 21:28 schrieb Julain Stebler:<br class="gmail_msg">
</div></div><div text="#000000" bgcolor="#FFFFFF" class="gmail_msg"><blockquote type="cite" class="gmail_msg">
<div dir="ltr" class="gmail_msg">
<div dir="ltr" class="gmail_msg">
<div dir="ltr" class="gmail_msg">Hello Everybody
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg">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:</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg">I have a grid with the size of 10x10
(100 pieces/states). Every piece represents a state and
every state has votes.</div>
<div class="gmail_msg">Votes for democrats and votes for
republicans. The votes for the republicans are two times
higher.</div>
<div class="gmail_msg">The sum of ten states defines which
party wins the vote for the constituency. So there are 10
constituency.<br class="gmail_msg">
The goal is that the party with the lower number of votes
wins the most constituency more precisely wins the
election.</div>
<div class="gmail_msg">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:</div>
<div class="gmail_msg">[1, 1, 1, 1, 2, 2, 2, 5, 5, 6</div>
<div class="gmail_msg"> 1, 1, 1, 1, 1, 2, 2, 2, 5, 6</div>
<div class="gmail_msg"> 1, 4, 4, 4, 4, 2, 2, 2, 5, 6</div>
<div class="gmail_msg"> 3, 3, 4, 4, 4, 2, 5, 5, 5,6</div>
<div class="gmail_msg"> ....</div>
<div class="gmail_msg"> ....]</div>
<div class="gmail_msg">
<div class="gmail_msg">The number represents the number of
the constituency which won the election.</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg">To check if the winning
constituency are aside I would like to use my own
constraint handler. But I do not know which method (<a href="http://scip.zib.de/doc/html/CONS.php" class="gmail_msg" target="_blank">http://scip.zib.de/doc/html/CONS.php</a>)
I should use. </div>
<div class="gmail_msg">At the moment I
implemented 'conscheck' and 'consenfolp'. But the time
to check the correctness is way to long.</div>
<div class="gmail_msg">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.</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg">
<div class="gmail_msg">The code for my election problem
with the handler can be found here:</div>
<div class="gmail_msg"><a href="https://gist.github.com/bhzunami/54cbc4f5ce37ba88e8c91d4ece0a4b56" class="gmail_msg" target="_blank">https://gist.github.com/bhzunami/54cbc4f5ce37ba88e8c91d4ece0a4b56</a></div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
</div>
<div class="gmail_msg">If there is a better idea I am
happy to hear it.</div>
<div class="gmail_msg">If something is not clear please
ask back or make some comments in the gist.</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg">Thank you for your help and time.<br class="gmail_msg">
</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg">Kind regards</div>
<div class="gmail_msg">Nicolas</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<br class="m_-6915722490040910444m_-9016179870582273115inbox-inbox-Apple-interchange-newline gmail_msg">
</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
<div class="gmail_msg"><br class="gmail_msg">
</div>
</div>
</div>
</div>
<br class="gmail_msg">
<fieldset class="m_-6915722490040910444mimeAttachmentHeader gmail_msg"></fieldset>
<br class="gmail_msg">
</blockquote></div><div text="#000000" bgcolor="#FFFFFF" class="gmail_msg"><blockquote type="cite" class="gmail_msg"><pre class="gmail_msg">_______________________________________________
Scip mailing list
<a class="m_-6915722490040910444moz-txt-link-abbreviated gmail_msg" href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a class="m_-6915722490040910444moz-txt-link-freetext gmail_msg" href="https://listserv.zib.de/mailman/listinfo/scip" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br class="gmail_msg">
</div>
</blockquote></div>