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.