problem solving

Discussions, advice, bug reports and much more about the "cage" environment.
ernopolo
Posts: 151
Joined: Sun Sep 16, 2012 6:55 pm

problem solving

Post by ernopolo » Sun Feb 12, 2017 7:22 pm

Dear masterminds,

I'm wondering if any of you could help me with this. I think it could be done using bach.constraints but I couldn't yet grasp using that object.

1090 ranges (single-voice portions of a bach.roll) are searching for shelter in a (54 voiced) bach.roll. They would like to keep their positions in time but they don't really care which voice they are landing in - except one crucial condition: they refuse to be overlapped. Our goal is to find a new home for all of them - or if it's impossible then find the best possible solution - "best" meaning that we try to minimize the number of homeless ranges.

I already built something but still 170 of my 1090 are out.

Of course, the exact numbers are not important here, just need to check time ranges (like 234000. 334000.) if they overlap or not - but the tricky part is how to find better and better arrangements. Does it make sense to use bach.constraints here?

Hope it makes sense.
Best,
Ernő

andreaagostini
Posts: 175
Joined: Fri Dec 03, 2010 1:51 pm

Re: problem solving

Post by andreaagostini » Mon Feb 13, 2017 4:44 pm

Hi Ernő.

There is something I'm clearly missing, but I'll ask anyway: are you sure that there is a better solution than assigning each "range" to the first (i.e., the lowest indexed) free voice available? I'm not saying that this is completely trivial, but my guts tell me that bach.constraints is probably overkill for the task, as it would perform a combinatorial search which, given the vastness of your search space, I'm afraid would be impossibly slow.

But I'm sure I'm missing something, so don't hesitate to give me more insight...

Cheers,
andrea

ernopolo
Posts: 151
Joined: Sun Sep 16, 2012 6:55 pm

Re: problem solving

Post by ernopolo » Mon Feb 13, 2017 10:06 pm

Hey Andrea,

thanks for picking this up!
Imagine for example that one of the ranges is so long (e.g. 15 minutes) it would use up a voice's whole time if we let him land there. But if we refuse him, it saves space (=time) for possibly hundreds of 1 second long ranges. You see the point now? The number of voices are limited so we need to find the best combination to fit them all or most of them in.

E

andreaagostini
Posts: 175
Joined: Fri Dec 03, 2010 1:51 pm

Re: problem solving

Post by andreaagostini » Mon Feb 13, 2017 10:15 pm

I see.

Actually, I didn't consider carefully the fact that you want to maximize the number of assigned ranges, rather than their total duration. So, you actually prefer two 1-second ranges than one 15-minute range, right?

Now, what about sorting the ranges by increasing length, and inserting each of them in the lowest-indexed free voice, starting from the shortest one? Does it make sense? Once again, I'd not go for bach.constraints so far...

Sounds like a fun problem anyway ;) — and, by the way, I'd use bach.roll as the actual data container for performing the placement of ranges: for every new range, you ask for a subroll on the range's onset and offset, look for the first empty voice and put your new range there (perhaps in the form of a dummy note with a slot marking the corresponding range index).

Let me know what you think,
andrea

ernopolo
Posts: 151
Joined: Sun Sep 16, 2012 6:55 pm

Re: problem solving

Post by ernopolo » Mon Feb 13, 2017 10:16 pm

We could say to sum it up:

assign the ranges voices in a way that
- they don't overlap inside a voice while
- minimizing the number of ranges left out
- this could imply minimizing the empty parts between the ranges inside the voices

andreaagostini
Posts: 175
Joined: Fri Dec 03, 2010 1:51 pm

Re: problem solving

Post by andreaagostini » Mon Feb 13, 2017 10:40 pm

I don't really see how your second point implies the third one. It seems to me that the empty spaces would be minimised more effectively by favouring longer ranges over more numerous.

Anyway, the difficulty here with bach.constraints would not only be the slowness of operation, but the actual representation of the problem.

The first approach coming to my mind would be having one variable for each range, its value being the assigned voice (or, say, 0 for "left out"). It might not be too difficult setting up a system with a bach.roll in the lambda loop for performing the overlaps test, although I'm pretty sure this would make things quite slow — but I can't think of any other tool capable of a good representation of ranges in time. The lambda loop might return "reject" (or perhaps some very small value such as -10000?) for each overlap, and 1 for each non-0 variable: in this way, avoiding overlaps would be the priority, but maximising the number of placed ranges would have an impact, too. But I'm afraid that the heuristics would be terrible, and the solver would get stuck in locally optimum, but globally bad, solutions. Don't know, it would be worth trying...

andrea

ernopolo
Posts: 151
Joined: Sun Sep 16, 2012 6:55 pm

Re: problem solving

Post by ernopolo » Mon Feb 13, 2017 10:51 pm

Hey I drew an example which proves your solution would fail in minimizing the number of voices used. (and that would be useful in order to fit most of them)

(sorry i post the image again there was something wrong)

i hope you see it :) your solution is down, while the upper one would be ideal (2 against 3 voices used)
what do you think?

ernopolo
Posts: 151
Joined: Sun Sep 16, 2012 6:55 pm

Re: problem solving

Post by ernopolo » Mon Feb 13, 2017 11:00 pm

hey, i couldn't post it in managable size, here we go:

https://dl.dropboxusercontent.com/u/899464/ranges.jpg

ernopolo
Posts: 151
Joined: Sun Sep 16, 2012 6:55 pm

Re: problem solving

Post by ernopolo » Mon Feb 13, 2017 11:58 pm

i saw your last message just now.

maybe combining my solution for ranges representation with your constraints suggestion would work.
instead of checking with a roll, i earlier designed an llll to hold all data i need for decisions about overlap. (1 ((range1_begin range1_end)(range2_begin range2_end)) (yy-balance) (no-triads))(2 ...)
(yy-balance is another condition but not important here, no. of ranges i used as a condition - i prefer the no. of ranges to be similar in all voices but if all ranges get in this would get irrelevant)

so this was the init state (i put an 0. to 0. range by default in order to have something numerical to compare with)

( 1 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 2 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 3 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 4 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 5 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 6 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 7 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 8 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 9 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 10 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 11 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 12 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 13 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 14 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 15 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 16 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 17 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 18 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 19 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 20 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 21 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 22 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 23 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 24 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 25 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 26 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 27 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 28 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 29 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 30 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 31 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 32 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 33 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 34 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 35 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 36 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 37 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 38 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 39 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 40 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 41 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 42 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 43 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 44 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 45 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 46 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 47 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 48 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 49 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 50 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 51 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 52 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 53 ( ( 0 0 ) ) ( 0 ) ( 0 ) ) ( 54 ( ( 0 0 ) ) ( 0 ) ( 0 ) )

and this was the end state, where still 170 of the 1090 ranges were left out.

<pre><code>
----------begin_max5_patcher----------
305.3ocWQEsiBCBD7Y3qfvy0FpdsFueEi4BEWULsPCk1qdF+2OXAM24KPms6
NyNC2oDdqcAF4rOY6YDxcJgfkhEHYLg2KWTcxQrMtA911dkWj9kGV7X4Vo5R
4rraBXyVsJvYtiQ+sN.a4YEyTucx2Adjvpb0AoWcQaN+kCT9zBsYWonfUUuo
rNbIZhn0qKErC4YzGQhC6ypshmzm31ea.Rrv4u5Onr17R3XsGTZ7.6fKGFlA
2n1ZP+Gcev6WstHbaAB0lDbCBcvr9Y+nQ3RWvE9fElbIWuz7AOMp8H3LS5r1
OnQIwz4s72H6Sidx5NuRYCDg6O+HbRN04++iyIqwOp+Ia1pl+DOsmU1tz5tm
IJqEU6ZpJBeES07A6PJFRJLHcPft2dx38AUw8VjSK5C5uXvtFFG
-----------end_max5_patcher-----------
</code></pre>

my way to check the ranges overlap and to decide was something like this (i don't want to tire you with a chaotic patch so it's just an excerpt)

<pre><code>
----------begin_max5_patcher----------
1573.3oc4ZssqahCE84juBDOT0JkSD1lKgQiFMy2wQUQbwmD2RLHvI8zos+6
iu.DfDHlTZFNp4Ahhswr1Ku2Ki2Y+skKLCSeEWXZ7GFOarXw2VtXgrIQCKJ+
8ByCAuFkDTHGlY3QFKkZtR0UA6qIXY6UsPOdH8HKAyjCGT1ZV.KZOgtaaNNh
odbHem0VqLPtPwWP6pqFer7dHwxINM7SOsoZ1USM6qYX0jXFFP2YVeK7GNgV
+rEs8ikKEWVoo0c.WTDrCW83X3Wkn078HHvxZsgs3y5OLAluC.pLeKwWJt.B
ut4a2q42ioCuCSmh+B+YcgkmYDkRiILRJ0.X7jQb5g.BsXRb.bEFssGbsyJC
.ZPJ.MZJn4CFmWZ3kV9ByWHI3S37BtY0.lKLCxxZz7hF2hft9Tpbh7VU2Dgp
ZBU2TN9Do6zxm2bt4y319wbEc8pa0ppXZRiw4zijZ2V4B2xpI7rOifh.tdxu
.1xucbaDzvWj2kjF8Yrj4rpZLMCSIzrbbAlxBXknqt6X7KAGSXaeIkxJH+qD
fR2yqz+KAQ3duYZvAk08O4jfjJ6ybWNINkJ.QKtVzb0i6YCfb8Wb8rwHGAMH
6J2L2ofyK8zYA2HOVDFjKVJBUNnvpNYooIs6p99RvuvJ6NiPocXQVZV+clS1
sef6MLk24gglaYOEaORU8tkGXx1VDbpMayBRRJiTaO8uFPIGBXXFQsD.sp6D
SC3F59hn7zjjV1qpmSWomXtWbD9KjX1d4Cpoy.e3jrJmHy5U4XxNbAqcarfc
Esa4BACdSGCKiR2xvGxR3VQ6AzZSplgjM0zZ09PZas02BCh1uNiD8Yi2CL.e
feA9glC7R7doHGrQOWSpGBUws1kwscE55SuuGAuUMD85YauEU5+kRI2IuIm0
wxFfgYCakruRDCYUcsOt.MLWzOOX0ninzCG3JeJfOg7ys7q3vgO9wRf1CSfv
MNq836XZ6HUL2.uk6Dz619Sqdn9UCvaLiPijIN.DBTabZ6b1maPBa3.P46bN
KHKoSVDW6VXpSaXZsWFTRZd2TzBd2QpnGCY88uOwTDBfVC4TDxGHdCVnu75.
TjObPJhHTn5kkfOFV5cuapYIWvZfqq6FONS43qGSsw+2PlB55JC4zmk1L+YI
oD0eN09T1n0tU9TPaAOoNLzfrk6uqrkuT7FAQZRTduQHp+ZpC.4tUViwiB96
JQ4iVi3e.nwvVf2HrUqSCVdjv65bg1Z4tIj8EI.yEcSFz5MzKxKoRBCma727
aIFmw1a.GKChziAQd8jBwtLnmudL37vQjxoLv3IM8T4fVx3VuaF25s4dew9G
IWUPvmvMb0.S7YHA.YZK.VajtZ1t2j1P+LYwYJOSj5YOV9v5FowQdjZGKYj2
sSiCvrW4nGPdZ9UjGKGoMaaoWZrfOhzXcNw4IDZeYLUZJh9uNuUjdLOpBWkH
2nsYEiKXDZ8eivym826Lv8j3XLsqUDSJDYcVk+asVjGMjQZhYQlwlKX1VWLq
KOefDmkxeqpR+.HTkwUGTGuzGjsAzwGZy7Y8vaL98v6X8v2Ql8Hae41wt1xC
oU8Kj5+3CY23W99x8bbj+eohe7fWF0Mpxd1rHpqem3nIcF3+mPVGRVb1y2ZP
1cVAYsbL7lMP1S2vOvrI7SBYcnY37Qx3JaA0itu+7Ay95FAZMavrDJZqMOiv
r1hyyHLC0UcdFgYjtxyyDLCz02XyrYKkMvwf4YBO6pKlmO5ya7FClmI9F5tO
n+LRqyeLXddvy9vwbt+o.ymyRjLKX8jln5R47kz7cOEkliOmAqpZ975lXypH
8YCQZSaA5vcQoIphl8YCq0NV.eWvJYEFZ.JuX7wy3dUCpMGym5qj5NyCbzPZ
ZvBybYyIvTTJkwaUkM51.FKmDdjor9lEF7nJuwcIogAIkEuXMiMTsNdtfHWd
dYYZpTaYZvOEjbDabJkDgmxZzV8WF.rbGpFs8fisHsaVh9xQzNwkJxnaDUIk
bYzey.o9do8VQaWF.cYvyEqM5BGaMfSqP5eonoig2ObtGxQsz0oz4EHoSIy2
ob4urT46uL46Vh7xv5NBXJFoOgqNhVkDU+hUiPnpTioGAp1hSRgoer7+.XJr
MjB
-----------end_max5_patcher-----------
</code></pre>

but it doesn't check for better solutions - that's where .constraints - maybe - could help...

sorry for long msg

andreaagostini
Posts: 175
Joined: Fri Dec 03, 2010 1:51 pm

Re: problem solving

Post by andreaagostini » Wed Feb 15, 2017 7:42 am

Thanks for the drawing. I see your point, and I agree with you that there is no easy solution. bach.constraints might indeed be worth a try...

... and of course your calculated approach to finding the overlaps is probably much more efficient than my idea of using bach.roll. The latter has two advantages, though — first, it requires less patching; second, and perhaps more important, it allows viewing how the process unfolds, which I think might be interesting bach.constraints runs the search.

Anyway, keep me up to date with your progress if you like!

Cheers,
andrea

Post Reply