21
$\begingroup$

I think that the shortest path problem is probably the problem that is solved most often. But if we move to problems where we need more complicated solvers, like Gurobi, Cplex, and Baron? What are the problems which are solved most often in industry (or people deploy the solution)?

By problems I mean something like vehicle-routing-problems, scheduling problems, etc. It would also be great to know why these types of problems are solved most often (easy to implement, easy to deploy, most money involved, ...).

Improve this question
$\endgroup$

9 Answers 9

Reset to default
22
$\begingroup$

The two problems that come to my mind are:

  • Vehicle routing problem: solved tens of thousands of times per day by UPS/FedEx/other package carriers
  • Optimal power flow problem: solved every 5-15 minutes by nearly every independent system operator (ISO) in every modern power grid
Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Also, neural network training for image recognition, or whatever - maybe not by number of problems solved, but by total computing time. In the old days (through at least '70s), I think it was LPs to optimize oil refining. Question:How much are SOCPs used in actual OPFs in induitry? $\endgroup$
    – Mark L. Stone
    Commented May 19, 2020 at 1:14
  • 1
    $\begingroup$ @MarkL.Stone, that might be good to post as a separate answer. $\endgroup$
    – J W
    Commented May 19, 2020 at 7:18
17
$\begingroup$
  • Variations of bin packing problem (2D or 3D), when dealing with putting items in trucks or putting items in boxes (think of the times you order several items online and they all arrive in one big box)
  • Network design and flow problems, especially for making strategic decisions: where to locate warehouses to serve customers from different plants; during a pandemic or disaster, which plant or warehouse to shut down and where to allocate its loads, etc.
  • Many applications in the airline industry such as flight/crew scheduling and revenue management
  • Many applications in the railroad such as routing, train scheduling, freight car assignment, and capacity optimization

About the reasons for why they are solved most often: Saving cost, maximizing profit, improve customer service, mitigate risks, ... essentially whatever is your objective function in that specific industry.

A good source for OR applications in practice is INFORMS Journal on Applied Analytics (formerly, Interfaces). Also, there are some good answers about good-cause OR applications in this question. I suggest that you search for an industry that you're interested in to find more about OR applications there.

Improve this answer
$\endgroup$
17
$\begingroup$

In finance the Markowitz portfolio optimization problem and variants thereof solved a huge number of times every day in (semi) automatic trading systems.

Traditionally these problems is formulated as a convex QP but these days they are often formulated as a conic optimization problem.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ How many of your customers use MISOCP as opposed to continuous SOCP, to account for lot size, commission discounts, liquidity "schedule", etc.? That kind of stuff is menetoned in section 9.2.2 of the Mosek Modeling Cookbook docs.mosek.com/modeling-cookbook/… . $\endgroup$
    – Mark L. Stone
    Commented May 19, 2020 at 22:15
  • 1
    $\begingroup$ I do not know. However, in finance time is often critical so in many cases MISOCP is avoided. $\endgroup$
    – ErlingMOSEK
    Commented May 20, 2020 at 10:26
6
$\begingroup$

Many fine answers have already been provided fort this question. Here are some additional frequently solved optimization problems.

Neural network training for image recognition, or whatever. Not by number of problems solved, but by total amount of computing (those babies can burn weeks on high end GPUs and TPUs)

Oil Refining. In the old days (through the '70s and into at least the early 80s), LPs to optimize oil refining, solved by some variant of the Simplex Method, were the most frequently solved optimization problems, and were responsible for a large portion of the total worldwide floating point computations.

MILPs largely supplanted LPs, to include in oil refining, by the 90s when MILP solvers started greatly maturing and becoming commercially available.

Even in the 70s, there was some oil refining optimization done using Nonlinear Programming (or in some case, just Nonlinear Equation Solving). But I think such optimizations were more commonly performed by oil company researchers in Operations Research colloquiums, such as I attended at Stanford in the early 80s, than they were in practice at the oil companies which employed them.

Improve this answer
$\endgroup$
5
$\begingroup$

Staff scheduling problem.

Knapsack problem: Allocation of resource/time.

Location allocation.

Improve this answer
$\endgroup$
4
$\begingroup$

Even though Logistics applications (ranging from simple Economic Order Quantity (EOQ), to the more complicated Multi-Indenture Multi-Echelon (MIME)) are asked to produce suggestions to practitioners very frequently, given that they are already formulated, their solutions are not quoted or cited; they are part of the management process. Nevertheless, the insight that one can get by understanding their formulation and assumptions can be a game changer.

Improve this answer
$\endgroup$
3
$\begingroup$

Look at case studies from Gurobi: https://www.gurobi.com/customers/case-studies/

Improve this answer
$\endgroup$
1
$\begingroup$

Look at case studies from LocalSolver: https://www.localsolver.com/docs/last/exampletour/index.html

Improve this answer
$\endgroup$
0
$\begingroup$

Manufacturing applications based on tailored versions of Product-Mix Optimization and Diet Problem Optimization are also used a lot, daily.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.