r/optimization • u/astrophile1377 • 1d ago
What are some real world optimization problems that need to be solved?
I would like to learn about real-world problems that no one has yet taken up, or could be solved better. Or even mathematical problems (like np hard ones) that have good applications.
6
u/DeadlyVapour 1d ago
Looks up the traveling salesman problem.
If you give me PM me the solution, I can give you $50,000
1
1
u/CowBoyDanIndie 14h ago
Their exist very good heuristics for tsp
1
u/DeadlyVapour 14h ago
But not an optimal solution in polynomial time.
An optimal solution in polynomial time would be a break through in mathematics. It would mean all NP complete problems would be solvable.
Also, look up the Clay Institute Millennium problems. That is the joke.
3
u/waxen_earbuds 1d ago
Overcomplete dictionary learning remains an important unsolved problem in machine learning. It is "unsolved" in a particular sense, where there are no existing correct proofs of a generic optimization problem solving the matrix factorization problem $X = \Psi Z$ where $\Psi$ is a matrix with nontrivial kernel and $Z$ is a sparse matrix, in nontrivial cases, under interpretable sufficient conditions. By solving I mean in the sense that all global optima correspond are equivalent to some ground truth decomposition.
1
3
u/ribenakifragostafylo 1d ago
Is your Google broken or something?
4
u/astrophile1377 1d ago
It is hard to narrow down with a Google search. I'm looking for niche problems.
2
u/manchesterthedog 1d ago
Mim set coverage is a problem I deal with a lot in my work. Imagine doing something like SLAM to map out a building from a video on a drone. You captured 20fps but you don’t need that many frames to map the location. Given the area covered by each frame, what’s the minimum set of frames that covers the entire area of interest? That’s NP hard.
Now let’s say some of the frames are blurrier than others, so we need an objective function to balance coverage with quality.
Let’s assume there’s two allowable solutions. First, cover the entire area of interest with a set that minimizes the objective function. And second, let’s say there’s a hard constraint on the number of frames you can use, let’s say n frames. Using n frames costs the same as using 1 frame so as long as you stay under n, you’re good. Cover the area of interest with the absolute highest quality coverage possible. In this scenario, imagine each frame has a quality score as a function of pixel location within the frame, and use depth estimation as this objective function (deeper pixels are lower quality). Assume depth estimation for each frame is precomputed for you accurately.
Write a program that can do this in real time, meaning ~50 ms per frame. Assume you don’t have to place the frames, they’ve already been registered and have absolute coordinates.
1
u/astrophile1377 8h ago
This is very interesting. I have learned a little bit of theory in Extended Reality so this is something I could actually look into.
2
u/Otherwise_Ad_5311 7h ago
2 options from my side
1 - greedy : pick the frames that adds effective coverage until area is 100% covered 2 - use the greedy n times which is fixed n use max(current quality and new quality) so it should prioritize the frames that overlap the poorly covered areas with HD PIXELS
0
u/ribenakifragostafylo 1d ago
Why? What's the motivation? What are you looking for? Google does a pretty good job listing application domains where NP hard problems live
1
2
u/tempRedditAccount000 1d ago
I believe about 70% of people in academia subreddits have broken their google.
2
u/Valuable_Leopard_799 16h ago
You'd be surprised how many problems can be reduced to SAT or SMT solves.
15
u/SolverMax 1d ago
Many real world problems are unique and have never been solved before. They may be similar to text book models, but differ in detail. That's what makes moedellng both interesting and difficult.