9

A fair share of academic research and software development focuses on solving ever-larger problems, particularly when it comes to LPs.

I am however curious to know in what contexts and to what extent small LPs are solved in practice. Let's say LPs/QPs with at most a few hundred variables & constraints, possibly solved repeatedly with only minor changes between successive solves.

Does anyone know of practical examples of interest?

mtanneau
  • 4,123
  • 11
  • 24
  • 4
    In whichever applications where online computation is needed, I would presume the LPs or QPs being solved will be small. So problems arising in model predictive control in robotics, such as control of drones, may be examples of interest. Often many successive problems may need to be solved, where these problems may not differ by a lot in terms of constraints and objective. While I have not read this thesis, you may be able to find something relevant to you. – batwing Jul 17 '21 at 22:46
  • During the development of my code, I used netlib instances ( https://www.netlib.org/lp/ ). Compared to today's problems, these instances are rather small. You might find some information where these instances originally came from. – T_O Jul 17 '21 at 23:02
  • 2
    DEA (Data Envelopment Analysis) solves series of very small LPs. – Erwin Kalvelagen Jul 18 '21 at 06:07

2 Answers2

3

As batwing mentioned in a comment, optimal control applications, particularly in robotics, aerospace, and now self-driving cars, involve NLPs to be solved quickly. These NLPs are generally solved using a Sequential Quadratic Programming (SQP) approach, thus involving series of small-changing QPs to be solved very efficiently. For examples of applications, have a look at this website.

Pricing optimization (particularly in the airline industry) and inventory optimization (essentially in supply chain management) traditionally involve series of small-changing LPs to be solved over time. Nevertheless, the models considered, originally rough approximations of the reality, tend to be larger and larger, richer and richer, mixing discrete and nonlinear features.

Hexaly
  • 2,976
  • 1
  • 11
  • 17
2

Often small LP's are solved as subroutines to solve bigger discrete optimization problems.

Example 1: Say you're solving a VRP with time windows and you've a nice heuristic to enumerate good feasible solutions (subgraphs with n-nodes), to figure out an optimal route schedule on the enumerated path, you wanna solve an LP that minimizes the waiting time. This subproblem is an LP with 2n variables

Example 2: In several column generation algorithms, the subproblem is often a small LP (a popular case is solving a PM in bipartite graphs) that is solved to generate feasible good quality columns for the master problem in the context.

mohit-mhjn
  • 394
  • 2
  • 7