search

nucleic / kiwi

Efficient C++ implementation of the Cassowary constraint solving algorithm
https://kiwisolver.readthedocs.io/en/latest/
Other
692 stars 88 forks source link

How do we define an "objective function" and maximize or minimize it? #176

Open trusktr opened 9 months ago

trusktr commented 9 months ago

I have a feeling this concept is implicit in the usage of Kiwi, but I'm new to this stuff, and wondering if you can help point it out, if in fact the API allows it.

I read the Cassowary paper (API very similar to Kiwi's),

https://cassowary.readthedocs.io/_/downloads/en/latest/pdf/

and it mentions that it is great for solving objective function min/maximization problems, however after that brief mention at the top of the doc, it no longer mentions "objective function" anywhere else.

Where exactly in that doc is the "objective function", and is it being minimized or maximized?

(I'm trying to figure it out for use in the TypeScript fork of kiwi, and I'd like to document these concepts more clearly if in fact they are doable).

In Google OR-Tools, there's actually an API for explicitly defining objective functions, with "objective" in the API naming:

https://developers.google.com/optimization/lp/lp_example#define_the_objective_function

// Maximize 3 * x + 4 * y.
MPObjective objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 4);
objective.setMaximization();
MatthieuDartiailh commented 5 months ago

Indeed in kiwi one cannot directly access the objective function. Kiwi attempts to satisfy all constraints and minimize the deviation for constraints with a non-required strength.

I am not sure how best to help you however. @sccolbert may have a clearer image of kiwi inner working than I do though.