11 ms·
Researchers have found a faster way to do integer linear programming
- klysm 3y agoSo 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.
- idatum 3y agoI 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.
- ByteMe95 3y agoDo you have any recommendations on where to start?
- idatum 3y agoI wish I can remember how I even learned LP tools existed. I started with this: https://coin-or.github.io/pulp/ https://coin-or.github.io/pulp/
- eru 3y agoThe Google OR-tools library is also a good starting point. I learned about linear programming in uni, but alas I don't think a mathematician's course on linear programming would be a good starting point for practical programmers.
- mp05 3y agoWinston's "Operations Research: Applications and Algorithms" is the authority so far as I can tell. Trivial to find old editions online.
- graycat 3y agoFor positive integers m and n, have a m x n matrix A of real numbers. Then also have n x 1 x, 1 x n c, and m x 1 b. Seek x to solve LP1: maximize z = cx subject to Ax = b x >= 0 Instead just as easily can do minimize. Instead of =, might be given >= and/or <=, but use slack and/or surplus variables to get the problem in the form of LP1. Any x so that Ax = b x >= 0 is feasible. If there is such an x, then LP1 is feasible; else LP1 is infeasible. If LP1 is feasible and for any feasible x we have z bounded above, then LP1 is bounded and has an optimal x (z as large as possible) solution. Else feasible LP1 is unbounded above. So, LP1 is feasible or not. If feasible, then it is bounded or not. If bounded, then there is at least one optimal solution. Regard n x 1 x as a point in R^n for the real numbers R. Cute: If all the numbers in LP1 are rational, then have no need for the reals. The set of all feasible x is the feasible region and is closed (in the usual topology of R^n) and convex. If LP1 is bounded, then there is at least one optimal x that is an extreme point of the feasible region. So, it is sufficient to look only at the extreme points. To determine if LP1 is feasible or not, and if feasible bounded or not, and if bounded to find an optimal x, can use the simplex algorithm which is just some carefully selected linear algebra elementary row operations on z = cx Ax = b The iterations of the simplex algorithm have x move from one extreme point to an adjacent one and as good or better on z. A LOT is well known about LP1 and the simplex algorithm. There is a simpler version for a least cost network flow problem where move from one spanning tree to another. If insist that the components of x be integers, then are into integer linear programming and the question of P = NP. In practice there is a lot known about ILP, e.g., via G. Nemhauser. I used to teach LP at Ohio State -- there are lots of polished books from very elementary to quite advanced. I attacked some practical ILP problems successfully. I got into ILP (set covering, a darned clever idea since get to handle lots of goofy, highly non-linear constraints, costs, etc. efficiently) for scheduling the fleet at FedEx. The head guy at FedEx wrote me a memo making that problem my work -- officially I reported to the Senior VP Planning, but for that ILP work in every real sense reported to the head guy. The promised stock was very late, so I went for a Ph.D. and got good at lots of math, including optimization, LP, and ILP, etc. Conclusion: A career in LP or ILP is a good way to need charity or sleep on the street -- literally, no exaggeration. For some of what AI is doing or trying to do now, LP/ILP stands to be tough competition, tough to beat. And same for lots more in the now old applied math of optimization. Bring a strong vacuum cleaner to get the thick dust off the best books.
- CyberDildonics 3y agoPeople 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.
- ford 3y agoThis 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#History https://en.wikipedia.org/wiki/Mathematical_optimization#Hist...
- dang 3y agoFrom that link: Programming in this context does not refer to computer programming, but comes from the use of program by the United States military to refer to proposed training and logistics schedules, which were the problems Dantzig studied at that time Is that also true of 'dynamic programming'?
- mturmon 3y agoIf you don’t know, you are in for a treat. Here is Bellman’s own description of how he came up with the term “dynamic programming “ — I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities (Autobiography, p. 159). See: https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.17791 https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.... People up-thread have been getting cranky about the use of “programming “ in this sense. Now of course, “programming“ for optimization has been well-entrenched since the 1970s at least. But perhaps Bellman’s story does give some cover to those who feel the word “programming“ has been wrongly appropriated?
- ford 3y agoSoftware 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)
- tylerhou 3y agoILP is NP-complete.
- eru 3y agoYes? We do manage to solve ILP problems in practice quite nicely. In fact, most NP problems that you come across in practice are relatively tractable for most practical instances. Eg for the knapsack problem you have to actually work very hard to get a hard instance in the first place.
- imtringued 3y agoThat's not correct. First of all, you can't solve a neoclassical economy using LP, because equilibrium constraints can only be represented as complementarity constraints. You would have to give up on some aspects, like dynamic prices. The linear complementarity problem in itself is NP hard. So you're screwed from the get go, because your problems are now LPCC problems. Good luck finding an LPCC solver. I can confirm that an open source QPCC solver exists though, which should be even slower. Next is the fact that if you wanted to build a neoclassical economy model, only global optimization will do. This means that you need to simulate every time step in one large LPCC model, instead of using a finite horizon. Due to the perfect information assumption, you must know about the state of every person on the planet. You're going to need millions of variables due to simple combinatorial explosion. It's kind of startling how these assumptions, which are supposed to make analytical solutions tractable by the way, also make non-analytical solutions literal hell. And before you say that prices can be determined iteratively, as I mentioned, you would run into the problem that future prices are unknown to you, so how are you going to plug them into the second time step? The very thing you want to calculate depends on it's future value. Economics is a weird science, where experienced reality works much better than the theory.
- Duanemclemore 3y agoGreat 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 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.
- ken47 3y agoThis discovery may change the world in unpredictable and, perhaps very big, ways. Discoveries like this put all the self-important feature / model developers that we work with in our big tech day jobs into context.
- CyberDildonics 3y agoCan you explain specifically what about it you think will change the world and why?
- fuidani 3y agoAbout the travelling salesperson problem, below is a quote from the latest Sapolsky's book Determined: A Science of Life without Free Will. I am not sure how relevant this is for software developers, but still fascinating: "An ant forages for food, checking eight different places. Little ant legs get tired, and ideally the ant visits each site only once, and in the shortest possible path of the 5,040 possible ones (i.e., seven factorial). This is a version of the famed “traveling salesman problem,” which has kept mathematicians busy for centuries, fruitlessly searching for a general solution. One strategy for solving the problem is with brute force— examine every possible route, compare them all, and pick the best one. This takes a ton of work and computational power— by the time you’re up to ten places to visit, there are more than 360,000 possible ways to do it, more than 80 billion with fifteen places to visit. Impossible. But take the roughly ten thousand ants in a typical colony, set them loose on the eight- feeding- site version, and they’ll come up with something close to the optimal solution out of the 5,040 possibilities in a fraction of the time it would take you to brute- force it, with no ant knowing anything more than the path that it took plus two rules (which we’ll get to). This works so well that computer scientists can solve problems like this with “virtual ants,” making use of what is now known as swarm intelligence."
- deleted 3y ago[deleted]
- jcranmer 3y agoThere's been more than a few of these "nature solves NP-hard problems quickly!" kinds of stories, but usually, when one digs deeper, the answer is "nature finds local optima for NP-hard problems quickly!" and the standard response is "so does pretty trivial computer algorithms." In the case of TSP, when you're trying to minimize a TSP with a Euclidean metric (i.e., each node has fixed coordinates, and the cost of the path is the Euclidean distance between these two points), then we can actually give you a polynomial-time algorithm to find a path within a factor ε of the optimal solution (albeit exponential in ε).
- pas 3y agohttps://scottaaronson.blog/?p=266 https://scottaaronson.blog/?p=266 """ I went to the hardware store, bought some glass plates, liquid soap, etc., and found that, while Nature does often find a minimum Steiner tree with 4 or 5 pegs, it tends to get stuck at local optima with larger numbers of pegs. """
- Bimos 3y agoI have a dumb question: how long will it take before this result becoming a pratical MIP solver beating SCIP or gurobi?
- _dark_matter_ 3y agoCouldn't either of those implement this algorithm?
- ubj 3y agoDon't forget about the HiGHS solver [1]. MIT licensed and getting to the point where it's outperforming SCIP on the Mittelmann benchmarks [2]. [1]: https://github.com/ERGO-Code/HiGHS https://github.com/ERGO-Code/HiGHS [2]: https://mattmilten.github.io/mittelmann-plots/ https://mattmilten.github.io/mittelmann-plots/
- FreakLegion 3y agoHiGHS is more of an alternative to Bonmin and Minotaur than Couenne and SCIP. In my experience though the presolvers in SCIP are extremely dangerous, and it's easy to end up with a local optimum even when that isn't your goal.
- nkh 3y agoFor now, the new algorithm hasn’t actually been used to solve any logistical problems, since it would take too much work updating today’s programs to make use of it. But for Rothvoss, that’s beside the point. “It’s about the theoretical understanding of a problem that has fundamental applications,” he said. I don't see how "it would take to much work updating today's programs". Most domain specific models call out to Gurobi, CPLEX, or FICO solvers for large problems, and open source ones like SCIP for the small ones. There is a standard MPS format where you can run exchange models between all of these solvers, and the formulation of the problem shouldn't change, just the solving approach inside the solver. Can someone enlighten me? I could see if they are arguing, this will require a new implementation, and if so, there is a ton of benefit the world would see from doing so.
- math_dandy 3y agoThe new algorithm of R&R would need to replace the algorithms at the core of Gurobi, CPlex, etc. These tools are marvels of engineering, extremely complex, results of decades of incremental improvements. If would likely take significant research effort to even figure out a way to incorporate the new discoveries into these engines.
- nkh 3y agoWhy would it need to replace them? From the article, they claim they have found a way to reduce the upperbound faster when searching large Integer problems. I don't see how that effects the current searching process. All of these solvers you can enter in an upperbound yourself if you have knowledge of the problem and know a previous solution. So it seems if this is just a programmatic way of reducing the upper bound, it should fit right in with current approaches. What am I missing?
- whatyesaid 3y agoIt's a research paper. You can write a theoretical paper and let others apply it practically, which others can figure out the practical aspect and report results of benchmarks, or others can also build on the theory. This paper only has 2 authors. The other solvers are probably applying technique specific tricks and speedups, and you're working with approximate optimization, it's not that easy to move everything over.
- ubj 3y agoMinor nitpick, but the title of this submission should specify "Integer Linear Programming", since the integer part is a much bigger deal. Polynomial time algorithms have been known for linear programming for decades; _integer_ linear programming is NP-hard.
- dang 3y agoI think we fixed that, albeit by accident when I edited the title earlier. If it needs further fixing let me know!
- eru 3y agoYou are right that integer linear programming is NP-hard; but faster algorithms for continuous linear programming are also super interesting and impactful. Continuous linear programming is also _hard_. Not in the sense of NP-hard, but in the sense of there being lots of algorithmic and engineering aspects that go into an efficient, modern LP solver. Even just the numerics are complicated enough. (And many integer linear programming solvers are based on continuous linear programming solvers.)
- ubj 3y agoTrue, these are all fair points! I didn't intend to diminish the impact or complexity of linear programming solvers. Well-written solvers are some of the most useful and powerful computational tools that exist today.
- eru 3y agoDefinitely. Advances in numerics in general, matrix multiplication in particular, and solving of systems of (continuous) linear equation and continuous linear programming are to computing what advances in basic material science are to engineering. Modern concrete and steel (and plastics etc) allow you to build so much more advanced, but also simpler, than the kinds of wacky shenanigans people had to pull off in eg the 19th century just to get high pressure steam engines to work (if they could do that at all).
- 3y ago
- aaron695 3y agoLinear programming is very cool, I loved Vasek Chvatal's book as a kid having accidently bought it thinking it was for computers. But it's tricky to understand and implement and it struggles with real life constraints. i.e. This whole specialty just for integers. Monto Carlo is trivial to understand and implement, adapts to changes and constraints trivially and should be just as good. I'm sure for something high end like chip design you will do both. I'd be surprised to hear of real life stories where linear programming beats Monty Carlo.
- anon291 3y agoLinear programming on reals is "easy"... You can just check all the points. I believe you can follow the shell of the legal polytope and just use a greedy algorithm to choose the next point that will minimize your goal. If you can get away with a continuous linear program I don't see why you'd use monte carlo. The simplex method will get you an exact answer.
- aaron695 3y ago[dead]
- eru 3y ago> But it's tricky to understand and implement and it struggles with real life constraints. i.e. This whole specialty just for integers. Integers are actually harder to deal with than rational numbers in linear programming. Many solvers can also deal with a mixed problem that has both rational and integer variables. Monte Carlo simulations are an entirely different beast. (Though you probably mean simulated annealing? But that's close enough, I guess. Linear programming is an optimization technique. Monte Carlo by itself doesn't have anything to do with optimization.) One problem with these other approaches is that you get some answer, but you don't know how good it is. Linear programming solvers either give you the exact answer, or otherwise they can give you a provable upper bound estimate of how far away from the optimal answer you are.
- genman 3y ago[2023] The paper was uploaded first in March https://arxiv.org/abs/2303.14605 https://arxiv.org/abs/2303.14605
- coliveira 3y agoWhile this is an interesting theoretical result, we need to remember that they found an algorithm that is (log n)^O(n). In other words, this is not practical to solve problems with moderate to large size n.
- adgjlsfhk1 3y agocompared to the previous bound of n^n, log(n)^n looks pretty good.
- muldvarp 3y ago> In other words, this is not practical to solve problems with moderate to large size n. This depends entirely on your definition of "moderate to large". Many real world problems can be solved easily using existing MILP solvers. We will likely never find an algorithm that can solve arbitrarily large instances of NP-complete problems in practice. Heck, it's easy to generate lists that are to large to be sorted with O(n^2) bubblesort.
- onetoo 3y agoI don't know much about the specific space of ILP, but speaking more generally... It is sometimes possible to specialize algorithms and implementations to be faster for certain subdomains of the overall problem, allowing real-world-useful problems to be solved in reasonable time despite the generalized theoretical complexity bound. If this new algorithm is a fundamentally different approach from the current ones, this may allow ILP to be used in domains where it is currently infeasible. Vice versa, this new algorithm may not be feasible in domains where current tools thrive.
- whatever1 3y agoIt’s great result but probably not useful. Similarly to how interior point methods have better theoretical complexity than simplex for LPs, but fine tuned simplex in reality almost always wins.
- geysersam 3y agoI never really understood that. Is there a commonly understood "reason" why IP methods are typically slower in practice? Seems going through the interior you'd quicker approach a good solution than when being confined to the boundary. But maybe that difference is less important in high dimensions.
- whatever1 3y agoCalculating derivatives is the most expensive and numerically challenging operation you do in optimization. Simplex circumvents these issues by traversing the edges of the polytope. Pivoting is very cheap and from practice we see that you are afforded a LOT of iterations before even start thinking about interior point methods.
- fuzztester 3y agoI remember the news articles when Karmarkar's algorithm for linear programming was announced. https://en.wikipedia.org/wiki/Narendra_Karmarkar https://en.wikipedia.org/wiki/Narendra_Karmarkar https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
- rurban 3y agoSo this is for the special case of non-negative and non-zero weights only, right? But those cases are the only sane ones, avoiding recursive loops winning a time-travel-alike race.
- andrewp123 3y agoIt seems their result has been out for almost a year now... https://arxiv.org/abs/2303.14605 https://arxiv.org/abs/2303.14605 I'm curious how this affects Traveling Salesman. I was under the impression that all NP-Complete problems take O(n!). Does this method improve it at all?
- yau8edq12i 3y agoSo what? It takes time for the community to digest the result, grasp its significance, and then write popularization articles about it. If you want to know what's being discovered right this second, read arXiv preprints. If you want to know what was discovered semi-recently and you want an explanation in layman terms that puts the results in perspective, read popularization pieces a while later.
- blackbear_ 3y agoDepending on the problem it can also O(2^n), but that is always the worst case scenario. Modern ILP solvers employ a variety of heuristics that in many cases significantly reduce the time needed to find a solution. Anecdotally, some years back I was developing MILPs with millions of variables and constraints, and most of them could be solved within minutes to hours. But some of them could not be cracked after weeks, all depending the inputs.
- adrianN 3y agoWe actually don't know how long NP-complete problems take to solve. We conjecture that it's superpolynomial, but that can be exponentially faster than O(n!).
- deleted 3y ago[deleted]
- Tarean 3y agoOften, the concrete problems we are interested in have some internal structure that make them easier to solve in practice. Solving Boolean formulas is NP-complete but we routinely solve problems with millions of variables. ILP (and sat) solvers are interesting because they are great at ruling out large areas that cannot contain solutions. It's also easy to translate many problems into ILP or SAT problems.
- yuki69536 3y ago[flagged]
- mzl 3y agoLowering the algorithmic upper bound for a core NP-complete problem is always extremely interesting. However, this is not necessarily related to improving runtime for practical implementations solving the problem in question. Solvers for mixed integer programming (MIP) use a lot of algorithms in conjunction with loads of heuristics. Building up the library of heuristics and strategies is a crucial part of why the improvement in MIP solvers have outpaced Moores law. From https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/602.f16/602miscfiles/UF_Entrepreneurship_19November2014.pdf https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6..., the improvements in hardware from 1990 to 2014 was 6500x. But the improvements to the software are responsible for 870000x performance improvement. The referenced article may become another part of the puzzle in continuing performance improvements for MIP solvers, but it is not in any way a given.
- WhitneyLand 3y ago[flagged]
- eigenket 3y agoRun time, runtime and run-time are all commonly used for the thing you want to call run time. None are incorrect. https://www.collinsdictionary.com/dictionary/english/runtime https://www.collinsdictionary.com/dictionary/english/runtime
- WhitneyLand 3y agoInformally they are used interchangeably. However, their definitions are different. The subject here, is academic research involving algorithmic complexity. What papers do you know of that refer to algorithmic complexity and “runtime”? Context matters. It is incorrect in this context.
- eigenket 3y agoGoing on arXiv computer science and searching for the string "runtime" returns 6135 results, many of which seem use it in the sense we're talking about here. https://arxiv.org/search/cs?query=runtime&searchtype=all&abstracts=show&order=-announced_date_first&size=50 https://arxiv.org/search/cs?query=runtime&searchtype=all&abs... In any case Quanta Magazine is not a formal academic journal, and neither is hacker news. We're having an informal discussion about a popular science article.
- sanketskasar 3y agoCan the folks on HN guide me on how to learn and master linear programming and create a consulting career out of it? I've been exposed to linear programming slightly at work and I find this to be powerful technique to solve a lot of problems that are currently written with generic software programming with better results. I feel there is good opportunity to create a consulting career/business out of it, though having the knowledge and expertise is necessary and there aren't lot of good resources on the internet to learn.
- 3abiton 3y agoTo be fair, I don't see why LP is still being used for many applications nowadays and not replaced, as it tends to be a brute force techniques.
- davidgrenier 3y agoLP or ILP? There is a significant difference since for non-discrete problem Linear Programming is shockingly efficient and in no way can be considered a brute force technique. edit: What would be a technique you consider non-brute force in discrete problems?
- ricogallo 3y agoWould you care to elaborate?
- spywaregorilla 3y agoDon't. There's a lot of low hanging fruit out there in the world of decisions that get made manually today. If you can do a globally optimal MIP solver, cool, I guess. But often you don't have time to run it, and an immediately calculated and configurable greedy solution is good too. Find a domain space with one archetypal decision that gets solved by many different companies on repeat and just solve that one problem. The ones that already have software answers are the hard sells.
- geysersam 3y ago
- davidgrenier 3y agoCorrect me if I'm wrong but (log n)^O(n) sounds like atrocious complexity?
- cvoss 3y agoIt is atrocious. It's worse than exponential. But it's much better than the prior state of the art which was n^n 2^O(n). [1] The Quanta article, unfortunately, doesn't bother to report the prior complexity for comparison, despite that that's probably the single most important thing to say in order to support the claim in the article's sub-headline. [1] https://en.m.wikipedia.org/wiki/Integer_programming#Exact_algorithms_for_a_small_number_of_variables https://en.m.wikipedia.org/wiki/Integer_programming#Exact_al...
- KingLancelot 3y ago[dead]
- antonioevans 3y agoHas anyone considered the potential of integrating the recent ILP breakthrough into transformer models? Given ILP's prowess in optimization, I'm curious about its application in enhancing transformer efficiency, especially in inference speed. Could this ILP method streamline computational resource allocation in transformers, leading to a significant leap in AI model optimization? Keen to hear thoughts on practical challenges and theoretical implications of merging these two fields.
- teknopaul 3y agoTL;DR fun math no impl
- henriquegodoy 3y ago[dead]
- henriquegodoy 3y ago[dead]
- duguppy 3y agoI am a little confused about some of the language used here. > The best version they could come up with — a kind of speed limit — comes from the trivial case where the problem’s variables (such as whether a salesman visits a city or not) can only assume binary values (zero or 1). Did they just call an NP-Complete problem a trivial case?! I was under the impression that all ILP can be reduced to 01-ILP equivalents, and vice versa? > Unfortunately, once the variables take a value beyond just zero and 1, the algorithm’s runtime grows much longer. Researchers have long wondered if they could get closer to the trivial ideal. So, is the work a solver improving the lower bound for 01-ILP or an algorithm that brings the bounds between 01-ILP and general ILP closer?
- j2kun 3y agoThe abstract is more informative: https://arxiv.org/abs/2303.14605 https://arxiv.org/abs/2303.14605 We obtain a (log(2n))^O(n)-time randomized algorithm to solve integer programs in n variables. So the work is theoretical: a better exponential-time algorithm than the previous best, based on some analysis of the structure of convex bodies in R^n and how they can be covered by integer grids (lattices). Most of the practical work on ILPs uses heuristics and branch and bound while taking advantage of the special structure of particular problem formulations. It isn't clear if this work could be used to help either of those, and I imagine without someone from Gurobi (or similar) chiming in, I wouldn't be able to tell from reading the paper.
- NanoYohaneTSU 3y agoOh please. Just another theory that won't impact anyone or improve anything anywhere.
- wduquette 3y agoI studied Operations Research at Stanford University in 1985/86, and got to take classes with George Dantzig; and then I went off and became a software engineer instead of doing OR. It's fascinating to read the comments on this post and see how much has been learned about linear programming algorithms since then.
- Chinjut 3y ago"The problem’s dimension influences the dimension of this shape: With two variables it takes the form of a flat polygon; in three dimensions it is a Platonic solid, and so on." It certainly needn't be a _Platonic_ solid! The author must have meant to write merely "solid" or "polyhedron" or some such thing