Integer and combinatorial optimization

What Hacker News says

1. thxgJul 2021
   For theoretical continuous/nonlinear/convex optimization, your #1 is the bible, together with

   "Convex Optimization" by Boyd & Vandenberghe.

   However, beware that both are grad textbooks. They can be tough going at times. Unfortunately, I never found undergrad textbooks I liked much, for theory.

   If you're interested in discrete optimization too (the other half of math optimization), the classics are:

   "Optimization Over Integers" by Bertsimas & Weismantel

   "Integer and Combinatorial Optimization" by Nemhauser & Wolsey

   Show morethread
2. graycatJul 2015
   > the documentation is half done

   The literature and documentation in operations research optimization is enormous, going back to the 1950s. The best of that literature is quite well written.

   For combinatorial optimization, there is

   George L. Nemhauser and Laurence A. Wolsey, 'Integer and Combinatorial Optimization', ISBN 0-471-35943-2, John Wiley & Sons, Inc., New York, 1999.

   The details of optimization are not always trivial, and several fairly challenging graduate applied math courses, complete with non-trivial theorems and proofs, can be needed for much depth in the subject.

   I've had four such courses and taught one.

   > I guess it's extremely difficult to implement generic optimization solver,

   A "solver"? Would be nice to have a "solver". Lots of people talk about giving a problem to a "solver". For linear programming, maybe usually can do that.

   Otherwise my experience is that asking for a general purpose solver is, for now, hopeless.

   Instead, for the real problems I've had success with, have to look carefully at the problem and exploit special structure particular to that problem.

   Typically part of the work involves doing some derivations using the math of optimization.

   Show morethread
3. graycatMar 2022
   Can look at the now old work of G. Nemhauser. His work was for combinatorial optimization and not just for exactly the traveling salesman problem (TSP).

   E.g., there is

   George L. Nemhauser and Laurence A. Wolsey, Integer and Combinatorial Optimization, ISBN 0-471-35943-2, John Wiley & Sons, Inc., New York, 1999.

   Some approaches involve set covering and set partitioning. Soooo, for the FedEx fleet, first just generate all single airplane feasible tours from the Memphis hub and back. Here can honor some really goofy constraints and complicated costing; can even handle some stochastic issues, i.e., the costs depend on the flight planning and that depends on the loads which are random, but it would be okay to work with just expectations -- we're talking complicated costing! Then with all those tours generated, pick ones that cover all the cities to be served, i.e., partition the cities. Have a good shot at using linear programming, tweaked a little to handle 0-1 constraints, to pick the tours.

   Then more generally for a lot of practical problems can write linear programming problems with some of the variables integer. Then can tweak the simplex algorithm of linear programming to handle some of such constraints fairly naturally in the algorithm. E.g., of course, can proceed with now classic branch and bound.

   The TSP taken narrowly can be regarded as more specialized.

   So, net, there is a big bag of essentially tricks, some with some math and some just heuristics.

   Part of the interest in the issue of P versus NP was to do away with the bag of tricks and have just some one grand, fantastic algorithm and computer program with guaranteed performance. Nice if doable. Alas, after all these years, so far not really "doable", not as just one grand, fantastic .... And the question of P versus NP has resisted so much for so long that it has even a philosophical flavor. And there are serious claims that a technically good algorithm would have some really astounding consequences.

   Sure, I have some half baked ideas sitting around that I hope will show that P = NP -- doesn't everyone? But my point here was just simple: For several decades we have been able to do quite well on real problems. Oh, for the problem with 600,000 0-1 variables and 40,000 contraints, otherwise linear, I used nonlinear duality theory (which is simple) or, if you wish, Lagrangian relaxation -- it's one of the tricks.

   Another old trick: For the actual TSP in any Euclidean space (sure, the plane but also 3 dimensions or 50 if you want), that is, with Euclidean distance, just find a minimum spanning tree (there are at least two good, that is, polynomial algorithms, for that) and then in a simple and fairly obvious way make a TSP tour out of that tree. That approach actually has some probabilistic bounds on how close it is to optimality, and it does better with more cities -- it's another tool in the kit.

   My main conclusion about the TSP, combinatorial optimization, and optimization more generally is that there are way, Way, WAY too few good customers. Whether there is 15% of project cost to be saved or not, the people responsible for the projects just do NOT want to be bothered. In simple terms, in practice, it is essentially a dead field. My view is that suggesting that a young person devote some significant part of their career to optimization is, bluntly, in a word, irresponsible.

   Show morethread
4. graycatOct 2019
   In grad school, I was lucky enough to have some especially well qualified professors of optimization including linear programming. I've applied it in business and taught it, both graduate and ugrad, in a business school. So, here I add a little to the original post:

   There is no need to explain the meaning of simplex or mention that polytope. The simplex algorithm just works with a polytope and never makes any use of the fact that there can be simplex polotypes.

   Or, to be more clear, "simplex algorithm" is the name of the algorithm, but there is no need to mention simplex again.

   He mentioned that the feasible region might go off the paper and seemed to suggest that that could cause a difficulty. Actually, no. Instead, a linear programming problem is feasible or not. If it is feasible, then the objective function is bounded or unbounded. The simplex algorithm handles all three cases. That the feasible region is unbounded does not mean that the objective function is, and, again, even if the objective function is unbounded the simplex algorithm handles that, i.e., routinely discovers that fact and reports it.

   He hints at cycling; can solve that nicely with the R. Bland anti-cycling rule. That rule is easy to program and can be used in practice but is also an especially elegant way to prove that the simplex algorithm can always work, that is, ends with the problem is feasible or infeasible and if feasible with an objective function bounded or unbounded and if bounded finds an optimal solution. That this situation is true means that we have just one baby step to showing the core saddlepoint theorem of two-person game theory, e.g., the game paper, scissors, rock.

   Some of the most interesting linear programming problems are to find the least cost way to move flow through a network where each arc has a maximum flow capacity. Here the simplex algorithm specializes in an astoundingly nice way (end up working with spanning trees). But cycling is still possible. There is an elegant, easy to program anti-cycling rule in (my TeX markup for D. Knuth's TeX)

   William H.\ Cunningham and John G.\ Klincewicz, ``On Cycling in the Network Simplex Algorithm'', {\it Mathematical Programming,\/} Volume 26, pages 182-189, North Holland, 1983.\ \

   Disclosure: Cunningham was one of my professors.

   Why so "interesting"? Now a huge question is how to attack linear programming problems where we ask that some or all of the variable values be integers. Some well informed people regard this problem as the most important in pure and applied math and computer science. Integer linear programming was one of the examples for the importance of the computational complexity question P versus NP; to be more clear, in principle integer linear programming is in NP-complete. There are more details on this question at Clay Mathematics where P versus NP is one of their million dollar prize problems.

   Well, for that network flow problem (i) if the arc flow capacities are all integers, (ii) if the problem is feasible with a bounded objective function, (iii) if we start with a feasible integer solution, then the simplex algorithm, including modified for network flows (with the spanning trees), and with an anti-cycling rule will in the simplex algorithm iterations automatically maintain a feasible integer solution and end with an optimal integer solution. In practice, this fact about integers makes a nice dent in the struggle of integer linear programming; that is, surprisingly often in practice integer linear programming problems (in principle in NP-complete) are merely just such network flow problems. Once I had that situation for a marketing resource allocation problem and another time for a NASA signal allocation problem.

   The simplex algorithm can be explained nicely as just a slight tweak of standard Gauss elimination for systems of linear equations.

   Indeed, the algorithm is so simple that when it ends, terminates, it is easy just to read off a lot of additional, possibly valuable, information about the problem. E.g., if are mixing feed for chickens, then can learn what one more pound of corn would be worth; here we can have what some economists call shadow prices. For one more, it can be easy to change some of the original data, add some constraints, etc. and for surprisingly little additional work solve the problem again. Such work after the algorithm terminates is called post-optimality.

   He didn't give any real examples; the usual first example is the diet problem for mixing feed, e.g., chicken feed, to give the chickens the nutrition they need at least total cost. I happened to have written up that problem earlier this week and posted it at

   https://themusingsofthebigredcar.com/the-technology-we-dont-...

   He gave no references. Here are some old but good references, just from my personal library with my markup for D. Knuth's TeX:

   Va\v sek Chv\'atal, {\it Linear Programming,\/} ISBN 0-7167-1587-2, W.\ H.\ Freeman, New York, 1983.\ \

   Mokhtar S.\ Bazaraa and John J.\ Jarvis, {\it Linear Programming and Network Flows,\/} ISBN 0-471-06015-1, John Wiley and Sons, New York, 1977.\ \

   G.\ Hadley, {\it Linear Programming,\/} Addison-Wesley, Reading, MA, 1962.\ \

   Dimitri P.\ Bertsekas, {\it Linear Network Optimization: Algorithms and Codes,\/} ISBN 0-262-02334-2, MIT Press, Cambridge, MA, 1991.\ \

   Saul I.\ Gass, {\it Linear Programming: Methods and Applications, Third Edition,\/} McGraw-Hill, New York, 1969.\ \

   In practice the simplex algorithm is astoundingly fast. An explanation for just why was by Karl-Heinz Borgwardt with more details and the reference at

   https://en.wikipedia.org/wiki/Simplex_algorithm

   But there are carefully constructed pathological problems where the simplex algorithm is very slow. The first paper on this was likely from Klee and Minty with more details at

   https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube

   Disclosure: Minty was one of my professors.

   Since I have mentioned integer linear programming, I should include a reference, e.g. (with my TeX markup)

   George L.\ Nemhauser and Laurence A.\ Wolsey, {\it Integer and Combinatorial Optimization,\/} ISBN 0-471-35943-2, John Wiley \& Sons, Inc., New York, 1999.\ \

   Disclosure: At one time Nemhauser gave me three words of advice, and that was the main direction for my Ph.D. dissertation.

   Yes, my references are, like the field, old.

   What the future in practice is of linear programming and related applied math I don't know.

   Show morethread
5. merrakshJun 2016
   the optimum is always at a vertex

   As you point out in [2], it would be more correct to say that among the optimal solutions there is always one at a vertex of the polyhedron</nitpicking>

   Also, simplex methods are very versatile when combined with other methods (see branch-and-bound for mixed integer linear optimization), but are sometimes easily beaten by barrier methods.

   Excellent textbooks for LP: Chvátal [4] and Bertsimas and Tsitsiklis [5]. For mixed integer linear optimization: Wolsey [6], Nemhauser and Wolsey [7], and Conforti et al. [8].

   [4] V. Chvátal, Linear Programming. MacMillan 1983.

   [5] D. Bertsimas, J.N. Tsitsiklis. Introduction to linear optimization. Vol. 6. Belmont, MA: Athena Scientific, 1997.

   [6] L.A. Wolsey (1998). Integer programming (Vol. 42). New York: Wiley.

   [7] L.A. Wolsey, G.L. Nemhauser. Integer and combinatorial optimization. John Wiley & Sons; 2014 Aug 28.

   [8] M. Conforti, G. Cornuéjols, G. Zambelli (2014). Integer programming (Vol. 271). Berlin: Springer.

   Show morethread
6. graycatJun 2013
   Not too impressed with the course.

   My qualifications: I got started in optimization scheduling the fleet at FedEx. In the words of FedEx founder, COB, CEO F. Smith, my work "Solved the most important problem facing the start of Federal Express" and the output from my software was "An amazing document".

   Later my Ph.D. research was in optimization and, in part, what I'd wished I'd known while at FedEx.

   Since my Ph.D. once there a problem in 'resource allocation' that became a 0-1 integer linear programming problem with 40,000 constraints and 600,000 variables. I derived some math, wrote some software, and in 905 seconds on a 90 MHz PC got a feasible solution within 0.025% of optimality.

   And there have been other problems.

   For the video, a good, first suggestion for an attack on a knapsack problem is via dynamic programming.

   By a wide margin, the most important topic in optimization is the simplex algorithm for linear programming. While the algorithm directly solves many problems in practice, it is the most important tool in solving optimization problems that are not linear programming. Usually there the role of linear programming is as a local linear approximation in an iterative scheme of better approximations.

   Much of the reason for the power of linear programming as a tool in larger iterative schemes is the several ways can take a linear programming problem and an optimal solution for it, make some changes in the problem, start with the optimal solution for the old problem, and get an optimal solution for the new problem very quickly.

   Good starts in linear programming include:

   Mokhtar S. Bazaraa and John J. Jarvis, 'Linear Programming and Network Flows', ISBN 0-471-06015-1, John Wiley and Sons.

   Vavsek Chvatal, 'Linear Programming', ISBN 0-7167-1587-2, W. H. Freeman, New York.

   Yes, the min-cost capacitated (each arc has a maximum flow it can carry) network flow problem, a special case of which is the transshipment problem (find the least cost way to ship some one good from factories to warehouses; also the source of the Kantorovich Nobel prize in economics) is a linear programming problem, and there the simplex algorithm simplifies and becomes the network simplex algorithm. Curiously, and of importance for fast computation, in the network simplex algorithm a basic feasible solution corresponds to a spanning tree in the network. For that problem, don't miss the W. Cunningham idea of a 'strongly feasible basis' or the more recent polynomial algorithm of D. Bertsekas.

   A significantly large fraction of real problems in combinatorial and discrete optimization can be solved as min-cost capacitated network flow problems via the network simplex algorithm. A big reason is, if the flow capacities are all integers and if have an integer basic feasible solution, then the simplex algorithm maintains integer basic feasible solutions for no extra work and, with the usual assumptions, produces an optimal integer basic feasible solution. So this is a case of linear programming where get integer linear programming for no extra effort; really, since nearly all the arithmetic is just integer, don't have to be concerned about roundoff error and get the solution for less effort.

   Yes, in combinatorial and discrete optimization, along with the rest of optimization, linear algebra helps.

   Curiously, one of the more powerful approaches to combinatorial optimization is a technique from nonlinear programming called Lagrangian relaxation, and there commonly the main computational step is linear programming. With that technique, some nonlinear duality theory can yield some bounds on how far are away from an optimal solution; such duality theory is what yielded the bound of 0.025% above.

   For combinatorial optimization there is, say,

   George L. Nemhauser and Laurence A. Wolsey, 'Integer and Combinatorial Optimization', ISBN 0-471-35943-2, John Wiley & Sons, Inc., New York.

   William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver, 'Combinatorial Optimization', ISBN 0-471-55894-X, John Wiley & Sons, Inc., New York.

   In the OP, the emphasis on NP-complete and algorithms that are worst case exponential is a bit exaggerated. E.g., as in the work of Klee and Minty, the simplex algorithm is worst case exponential, but in expectation in practice it is low order polynomial -- for why, there was some good work by K. Borgward.

   For integer, combinatorial, and discrete optimization, I have yet to see a claim that getting approximately optimal solutions is in NP-complete. In particular, if in a real problem have saved $10 million and have a bound saying that can't save more than another $2000, then why spend millions trying to save the last tiny fraction of the last penny and guarantee to have done so? If are willing to sacrifice the last penny, then it is not so clear (so far at least to me) that really are being forced into exponential algorithms, either average or worst case.

   The claim in the OP that combinatorial and discrete optimization are part of computer science looks like a case of 'academic theft'! Such optimization has long been regarded as part of applied math and there part of operations research. The material has been of interest in, say, departments of mathematical sciences. Some parts of optimization, e.g., control theory, have been regarded as parts of electronic engineering. At times it does appear that academic computer science wants to regard every topic that makes heavy use of computing as part of computer science! It looks like computer science has gotten tired of just quicksort, AVL trees, BNF, YACC, and RDBMS! :-)!

   The claims in the OP about the importance of optimization in the economy are a bit over enthusiastic. Maybe the importance would, could, and should be there, and maybe in Australia they are there, but my experience in the US is that there are essentially no significant non-academic career opportunities in optimization. E.g., at one time near year 2000, I had a nice, long talk with one of the leading US headhunters in technical fields, and he finally confessed that in the previous year in all of the US there had been exactly one recruiting request in operations research. He "packed it in" (from the movie 'The Sting', i.e., gave up) and went to law school!

   Here is a good future -- although a wildly long long shot -- for integer, combinatorial, and discrete optimization: At present, all but quite simple problems in such optimization are solved by some experts attacking each problem one at a time, exploiting special structure of each problem, trying various techniques, and, hopefully, finally getting some good results. It's custom, one-off, bench scale, expert, creative, hand work and often, really, some applied research.

   In addition, there have long been programs that can be used to pose or enter problems in integer, combinatorial, and discrete optimization suitable for solution by a 'solver'. The problem is, since the programs are general purpose, the 'solvers' to be used are also general purpose and, without the hand work, too often in practice are not powerful enough.

   Presumably a polynomial algorithm of low degree that showed that P = NP could be the core of a general purpose solver powerful enough to make solving such optimization problems easy and routine.

   Lacking such a solver, in practice patience with such optimization has long been a bit thin.

   So, what the heck happened? In much of physics, say, planetary motion, we can write down some equations the real system must solve. If the equations have a unique solution, then that solution must be the right one for the real system. At times since early in WWII, such physics was of enormous value for at least the US DoD.

   So, given such an equation, solve it. This technique often worked for, say, initial value problems for relatively simple ordinary differential equations. Alas, for the partial differential equations of fluid flow, the Navier-Stokes equations, the situation was usually a bit challenging.

   Also in problems for the US DoD, e.g., 'logistics' or how to move a large army across a large ocean in least time within capabilities of existing resources, could write down some equations and other mathematical specifications that a 'best' solution had to satisfy. So, then, to say how to move the army, just 'solve' the equations, etc. This work was called 'operations research', and at times the US DoD was very enthusiastic about it. With enough US Federal Government research grants to academics, parts of academics got enthusiastic about it. And so did Bell Labs.

   But there was no law of the universe that said that finding solutions to such mathematical specifications would be easy. Yes, Navier-Stokes is another example of difficulty. Now, in cryptography, so is the fundamental theorem of arithmetic, that is, factoring a positive integer into a product of prime numbers.

   Clay Mathematics Institute in Boston has more than one prize of $1 million available for progress on such things.

   Net, it does very much appear that for now making money by building a popular Web site and selling ads on it is a much easier way to make money! And, at times, in such work some applied math, possibly new, can be an advantage. But, clearly for now, the grand goals of integer, combinatorial, and discrete optimization are too difficult for 'prime time' in practice in mainstream business.

   Or, problem A can make a lot of money if we have a lot of applied math and computing. So, let's attack problem A. Alas, that much applied math and computing, or even just part of the computing, may be much more valuable for solving other problems!

   Show morethread