Solving many tiny linear programming problems quickly on embedded

user_1899587 0
Viewed 513

As part of some live rendering process for a program that runs on iOS/Android, written in C/C++, I need to solve many tiny linear programming problems, with 5 variables and 2 constraints, i.e.

minimize: a_0*x + b_0*y + c_0*z + d_0*u + e_0*v
subject to:
  p_1 = a_1*x + b_1*y + c_1*z + d_1*u + e_1*v
  p_2 = a_2*x + b_2*y + c_2*z + d_2*u + e_2*v
  0 <= x <= x_max
  0 <= y <= y_max
  0 <= z <= z_max
  0 <= u <= u_max
  0 <= v <= v_max

I'd like to solve this quickly using a permissive license.

Searching I found Google's linear optimization library glop (Apache2), but

  1. it is a fairly big dependency, 7MB of code for something so small
  2. I'm concerned about the overhead of setting up the LP problems.

I feel it should be possible to solve this directly, by just enumerating the vertices and testing the objective function, but I can't wrap my head around it.

Is there a tiny LP library with small overhead I could use? Or alternatively, how would I break down the math?

linear-programming optimization android c++ ios
3 Answers

Your feasible set is a hypercube in 5 dimensions being sliced by two planes. It is small enough to be represented in a different form - as a combination of extreme vertices. The vertices can be enumerated, and the optimal can be found by simply evaluating the objective function in each vertex.

If your plane coefficients change, you can start with the 32 vertices that define the hypercube as the combination of extreme vertices.

You need to write some code to slice a region (polytope) represented by extreme vertices against a plane.

Since you only slice it twice, this will not add too many extra vertices.

user_2950930
Related