Fast constraint minimizer needed

[jamievicary]

We currently use the general-purpose linear optimizer Kiwi.js to compute 3d diagram layouts. Unfortuately this is too slow, taking a few seconds even for a relatively small 3d diagrams. (In the developer console you can see logging messages showing how long this is taking.)

For the 2d diagrams, we also had this issue, and I replaced the Kiwi code with some custom code a while ago, which is 2 orders of magnitude faster.

We should either find a faster linear optimizer to use, or write our own. We need both 'hard' and 'soft' constraints, which Kiwi does well. For example, the height of a vertex is generally exactly known (hard constraint), and every entity must be a distance of at least 1 (hard constraint). But we also want the diagram to be as small as possible, which can be thought of as a soft constraint putting everything at the origin.

[jamievicary]

This looks like a good option: https://github.com/jvail/glpk.js

[jamievicary]

Kiwi.js has an "incremental" behaviour, meaning that it updates its solution as you add new constraints. This is probably not as efficient as just solving for all constraints simultaneously, which most other libraries do.

[zrho]

Cassowary, the LP variant with priorities, seems to be almost always incremental. One option would be to use the cassowary implementation in rust and compile it to webassembly.

On Tue, 15 Jan 2019, 21:58 jamievicary <notifications@github.com wrote:

Kiwi.js has an "incremental" behaviour, meaning that it updates its solution as you add new constraints. This is probably not as efficient as just solving for all constraints simultaneously, which most other libraries do.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/homotopy-io/webclient/issues/66#issuecomment-454548818, or mute the thread https://github.com/notifications/unsubscribe-auth/AAV1JUKPsyj0179A4xEcLhMvSn2bIt2Sks5vDkEGgaJpZM4aA2vD .

[jamievicary]

Hi Lukas, it's great that you're lurking :). Why would that proposal make sense - is the rust implementation not incremental?

I think that glpk package I linked to looks quite good - the API is easy and it seems well maintained. Unless we have a specific reason not to, surely it makes sense to go for an existing library.

[zrho]

It is incremental, but should be vastly faster than the js version due to it being compiled to what amounts to native code instead of Javascript. From what I have seen from a quick look, the solver you linked does not support priorities, which are essential in >= 3 dimensions, unless there is some LP voodoo that allows to encode this without priorities.

On Wed, 16 Jan 2019, 00:06 jamievicary <notifications@github.com wrote:

Hi Lukas, it's great that you're lurking :). Why would that proposal make sense - is the rust implementation not incremental?

I think that glpk package I linked to looks quite good - the API is easy and it seems well maintained. Unless we have a specific reason not to, surely it makes sense to go for an existing library.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/homotopy-io/webclient/issues/66#issuecomment-454586503, or mute the thread https://github.com/notifications/unsubscribe-auth/AAV1JU5FGR1RLhfVFpsLFH1OshFIHCyGks5vDl7vgaJpZM4aA2vD .

[jamievicary]

Linear programming is a standard thing. I thought those "priorities" in the Kiwi API just referred to the magnitudes of various coefficients for the objective function.

[zrho]

This is a bit different to standard LP: instead of an objective function, the solver tries to satisfy the constraints according to their priorities. I used this to allow for the nice layout constraints that we want to be broken, if they are impossible to satisfy. This uses a slightly modified simplex algorithm, which happens to be implementable in an incremental fashion as well.

On Wed, 16 Jan 2019, 00:21 jamievicary <notifications@github.com wrote:

Linear programming is a standard thing. I thought those "priorities" in the Kiwi API just referred to the magnitudes of various coefficients for the objective function.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/homotopy-io/webclient/issues/66#issuecomment-454589945, or mute the thread https://github.com/notifications/unsubscribe-auth/AAV1JXBlMPiTorTHtruvMh243J1V8klmks5vDmJ9gaJpZM4aA2vD .

[zrho]

To clarify from the previous message: a constraint of higher priority is always satisfied if possible, regardless of how much it affects lower priority constraints. Unless there are some boundednesd arguments, this cant be emulated by an objective function.

On Wed, 16 Jan 2019, 01:02 Lukas Heidemann <lukas@heidemann.me wrote:

This is a bit different to standard LP: instead of an objective function, the solver tries to satisfy the constraints according to their priorities. I used this to allow for the nice layout constraints that we want to be broken, if they are impossible to satisfy. This uses a slightly modified simplex algorithm, which happens to be implementable in an incremental fashion as well.

On Wed, 16 Jan 2019, 00:21 jamievicary <notifications@github.com wrote:

Linear programming is a standard thing. I thought those "priorities" in the Kiwi API just referred to the magnitudes of various coefficients for the objective function.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/homotopy-io/webclient/issues/66#issuecomment-454589945, or mute the thread https://github.com/notifications/unsubscribe-auth/AAV1JXBlMPiTorTHtruvMh243J1V8klmks5vDmJ9gaJpZM4aA2vD .

[jamievicary]

I see, thanks for that explanation. I accept that it can't be precisely replicated by a standard objective function, but surely it can be very well approximated, by building the objective function with coefficients of different magnitudes. For example, if we want to minimize X, and only then to minimize Y, we could attempt to minimize an objective function like this:

O(X,Y) = 10 * X + Y

It's possible that using this approach to convert the current Kiwi.js constraints-with-priorities setup into a standard LP problem could also lead to perfectly reasonable 3d layouts. (Certainly for 2d it would work fine.)

Anyway, I am happy in principle to try to a webassembly'd Cassowary, but I remain concerned about the incrementality and non-standard objective function, both of which I worry could mean we're ultimately sacrificing efficiency, which needs to be blazing if we're going to realistically be able to render large 3d and 4d (i.e. 3d movies) composites.

Lukas, is this something you could try to implement? We need to improve the layout speed by over 2 orders of magnitude. For example, at the moment, rendering the source of the pentagon equation takes about 2500 ms, for a small optimization involving just a handful of variables. Even 25 ms to solve this problem seems slow to me.

[jamievicary]

Another option is to use a standard LP solver in batches, optimizing first for the primary objective function, then fixing parameters appropriately and optimizing for the secondary objective function, etc. This would let us use a standard LP solver and still exactly replicate the nice layout algorithm that Lukas has developed.

[jamievicary]

This is now implemented; the 3d renderer now uses GLPK to prepare the layout.