pcbouman · HackerTrans

il y a 2 ansdiscuss

When you hit F5 (copy) or F6 (move) you typically get a dialog with the destination of the action where the other pane is pre-entered as a default so can just hit Return to start, but which you can also override by typing something before hitting Return. You can type whatever relative or absolute destination you want without having to navigate there explicitly in the other pane. For up/down one directory I personally type .. or the child-directory, if the destination is further away it is often more convenient to navigate there in the other pane.

pcbouman

il y a 4 ansdiscuss

To add some insight to what branch-and-cut actually does: even with integer programming you can still work with the high-dimensional polyhedron. If you end up being lucky and the optimal vertex turns out to be integral, you know you have the optimal integer solution. But of course, it may turn out that the vertex turns out to have non-integer components that should be integer, and that is where the real work starts. A lot of the magic in commercial solvers involves the development of clever tricks to get from this optimal non-integer point to an optimal integer point. With branching you split up the polyhedron eliminating your current non-integer point, and with cutting you add constraints that remove the non-integer point but are guaranteed to not remove any optimal integer points. There is typically a lot of choice in which thing to try first, and these choices typically have huge impact on how fast the solver is.

I am always happy to see people point out that NP-hard problems are solved to optimality in practice. Too often you come across someone who believes it is impossible to prove you have an optimal solution for an NP-hard problems, no matter which instance. But NP-hardness does not rule out the possibility that you might be much more lucky than the worst case with the particular instance you are interested in. It only says that there exist worst case classes of instances that become much more difficult to solve as their size increases.

By the way, I remember having learned that Integer Programming with a constant number of variables but a variable number of constraints can actually be solved in polynomial time with help from the Lenstra–Lenstra–Lovász lattice basis reduction algorithm, so I would not expect an integer problem with four variables to need years to solve. A constant number of constraints is actually more difficult than a constant number of variables (the Knapsack Problem is NP-hard and has a single constraint). AFAIK, for a constant number of constraints we have nothing better than a pseudo-polynomial time algorithm by Papadimitriou.

pcbouman

il y a 5 ansdiscuss

Mathematical Optimization still has many subfields that can be of interest. I guess that non-linear mathematical optimization is most more typical for many machine learning applications. Many pratical applications in scheduling, logistics, planning etc used linear (integer) programming and combinatorial optimization. The following are some points towards that body of literature.

Alexander Schrijver [1] has lecture notes on Combinatorial Optimization on his website [2]. He also has an affordable 1800 page three volume set of books "Combinatorial Optimization - Polyhedra and Efficiency" [3], although I would say it is better suited as reference material because it is quite densely written.

There is also the classic book "Combinatorial Optimization - Algorithms and Complexity" [4] by Papadimitriou (Bill Gates' MSc thesis supervisor) and Steiglitz that is a nice introduction to the topic as well.

"In Pursuit of the Traveling Salesman - Mathematics at the Limits of Computation" by William J. Cook [5] is a more popular science book on the history of the Traveling Salesman Problem, that also explains how linear programming is used in the state of the art solvers, but is of course focuses on a very specific problem. There is also a book that contains all the scientific and mathematical details by Applegate, Bixby, Chvátal and Cook [6] if that is preferred.

In recent years, there is a trend that mathematical optimization researchers work more with ML. In particular Dimitris Bertsimas has done some work on the intersection of those area's in recent years [7] and apparently has a book on the topic as well [8] (but I am not familiar with it).

[1] https://homepages.cwi.nl/~lex/ [2] https://homepages.cwi.nl/~lex/files/dict.pdf [3] https://www.springer.com/us/book/9783540443896 [4] https://www.amazon.com/Combinatorial-Optimization-Algorithms... [5] https://press.princeton.edu/books/paperback/9780691163529/in... [6] http://www.math.uwaterloo.ca/tsp/book/index.html [7] https://dbertsim.mit.edu/papers/ [8] https://www.dynamic-ideas.com/books/machine-learning-under-a...

comments