Solving many tiny linear programming problems quickly on embedded

Issue

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?

Solution

The solution can reasonably be hard-coded as follows:

• take the first two linear constraints and select three variables (there are 10 ways to do so), to which you assign either 0 or max (there are 8 ways to do that). This leads to 10 elementary 2x2 systems, with 8 different right-hand sides.

• check if these solutions are admissible (the two computed unknowns in range 0 to max).

• keep the admissible solution that minimizes the objective.

I wouldn't be surprised that carefully micro-optimized and unrolled code can beat a general-purpose solver (simplex algorithm).

Answered By - Yves Daoust