Researchers have found a faster way to do integer linear programming
quantamagazine.org
Researchers have found a faster way to do integer linear programming
1–10 of 210 posts
Re: Researchers have found a faster way to do integer linear programming
#2So many discrete optimization problems can be translated into linear programs. It's a really powerful set of tools to know, kind of like SAT solvers.
Re: Researchers have found a faster way to do integer linear programming
#3People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing.
Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short average distances first can also get to shorter distances sooner.
You can also cluster points knowing you probably don't want to jump from one cluster to another multiple times.
Re: Researchers have found a faster way to do integer linear programming
#4Software engineers interested in ML/algorithms should learn about linear programming.
It's surprising how many problems can be formulated as linear optimization.
For example, in college I was talking to my Industrial Engineer friend about the average minimum number of swaps required to place billiards balls in an acceptable starting position in the rack (triangle). We both happened to write programs that used monte-carlo sampling to solve it - but my solution did BFS on the state space of a graph, and his used linear programming (which was _probably_ more efficient)
Re: Researchers have found a faster way to do integer linear programming
#5People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short ave…
This made me wonder why it's called programming (since clearly it's not the sense of the word programming most HN'ers are used to).
https://en.wikipedia.org/wiki/Mathematical_optimization#Hist...
Re: Researchers have found a faster way to do integer linear programming
#6People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short ave…
take "programming" to mean "scheduling" and the ancient crusty term acquires some meaning.
Re: Researchers have found a faster way to do integer linear programming
#7People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short ave…
absolutely nothing? you mean other than the relationship with linear systems and linear algebra?
Re: Researchers have found a faster way to do integer linear programming
#8Great short article. I haven't looked deeply into the math behind this yet, but this looks to be a preprint [0]. It doesn't appear they're looking directly at the Space Groups as a way to reduce out any symmetries or repetitions that may occur (thus generalizing simplifications of the problem "space"), but it would be interesting to see whether those structures apply or not. I say this as someone who writes software to apply the Space Groups and describe the Voronoi cells around points (or groups of points) distributed through them, so I'm familiar with the "uncanny" ways effects propagate. [1]
I'm also not a mathematician (just a lowly architect), so I'm way out of my depth here. But it's fascinating and as someone looking at paths across these generated honeycombs, this result bears more investigation for me as well.
[0] https://arxiv.org/pdf/2303.14605.pdf [1] If you know a mathematician who might be interested in collaborating on this kind work, ping me. This is ongoing work, and as I said I'm out of my depth mathematically. But have run into some interesting properties that don't seem that deeply investigated which may bear deeper study by an actual expert.
Re: Researchers have found a faster way to do integer linear programming
#9People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short ave…
[deleted]
Re: Researchers have found a faster way to do integer linear programming
#10So many discrete optimization problems can be translated into linear programs. It's a really powerful set of tools to know, kind of like SAT solvers.
I only recently learned about linear programming. I started with PuLP and Python to get a grasp. It was one of those "How did I miss this??" moments as a developer.