Let's consider your > a complex multi-constraint optimization NP problem There was a day when I thought that! So, I was thinking non-linear optimization with

Let's consider your > a complex multi-constraint optimization NP problem There was a day when I thought that! So, I was thinking non-linear optimization with, say, some of gradients, steepest descent, conjugate gradients, quasi-Newton, Kuhn-Tucker conditions, maybe some Lagrangian relaxation, etc. and saw no hope. And I still remember the day when I got an explanation and learned better! Can make the problem 0-1 integer linear programming but otherwise linear. The non-linearities, really complicated costs, say, have a plane step climb when have a heavy cargo load, and really goofy constraints, e.g., don't fly over any US military bases or the White House, don't fly over residential areas at dinner time, etc., can handle in a simple way before the optimization itself. The technique has some generality and, thus, is a good tool to have in a 'data science' tool kit, especially with current computer hardware, library software, and practical data availability. Here's an outline of the technique: For one period from, say, 5 PM to midnight (again from 1 AM to, say, 8 AM) set up a table with one row for each city to be served, 90 cities, and one column for each candidate airplane trip, tour, from Memphis and back. In this table, for each city and column put a 1 in the table for that city and column if the tour for that column serves that city and put a 0 otherwise. So, generate all such columns; may have some thousands of columns. Considering all fine cost details want to account for, and taking expectations for random costs, say, from weather and air traffic control, find for each of the candidate tours its cost (first cut, assume that if a plane goes to a city, then it completely serves that city). Then for the schedule, want to pick no more than 33 columns (there were 33 planes in the fleet) from the 1000s so that all 90 cities are served and total cost is minimized. So, each column serves, covers, some cities (each city where the column has a 1), and want to pick columns that cover all 90 cities -- so have a set covering problem. Right, it's in NP-complete. So, in particular, we have a linear programming problem: We have one variable for each column. The costs and those variables form the linear function of the variables to be minimized. The constraint matrix is just that table we described. The constraints are that each city is served by some one column. Or in matrix algebra, we have from the table described above a matrix A with 90 rows and some thousands, say, m, columns. We have the variables x, m x 1. We have the m costs, 1 x m c. And we have the right hand side, 90 x 1 b where each component of b is 1. Then we want to find x to minimize cx subject to Ax = b. So, it's linear programming. Then in addition we ask that the variables take on values of only 0 or 1 -- so we have a 0-1 integer linear programming problem. If ignore the 0-1 constraint, then have a fairly routine linear programming problem but will likely end up with some fractional tours allocated. For honoring the 0-1 constraints, on this problem likely could do well enough with branch and bound. As FedEx grew, the nature of the scheduling problem changed. The outline above should have helped save significant bucks at least in the early years. Then, of course, that solution technique could be used to evaluate the few candidate hub locations. With some generalization, the solution technique could also be used to evaluate airplane types to add to the fleet. So, here we have 0-1 integer linear programming set covering; keep it in mind and see if you can find another good application.