> 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.
Thanks for mentioning Gurobi. I
just looked them up! So, they
are headed up by Bixby! Terrific!
After IBM bought ILOG and C-PLEX,
I assumed that Bixby would retire.
Apparently, nope!
Also Bixby has two students from
Georgia Tech so, likely from
George Nemhauser and Ellis
Johnson.
George is the person who explained
0-1 integer linear set covering to
me. That same day he gave me
three words of advice that became
the direction for my Ph.D. dissertation
(in stochastic optimal control)
at Johns Hopkins. I knew Ellis
when we were both at IBM's
Watson lab.
What you mentioned looks like
something quite common for
linear programming software.
E.g., think linear programming
tableaux and appending a new
constraint with its own, new
artificial variable. Then do
elementary row operations to zero
out the row of the new constraint
in the columns of the old basic
variables. Then do elementary row
operations to zero out the new
artificial column in all rows except
the row of the new constraint.
Then do simplex algorithm pivots
to get the new artificial
variable out of the basis.
Changing costs is also easy and
standard in convenient little operations
called post-optimality.
There are more details, but covering
all of those would need much of a
course in linear programming.
E.g., the IBM Optimization Subroutine
Library (OSL) is quite nice work,
likely heavily from Ellis Johnson
when he was still at IBM before he
went to Georgia Tech where George
Nemhauser has long been and does
what you mentioned.
Once I
wrote some 0-1 integer linear programming
software with some Lagrangian relaxation
based on the OSL -- it was nice.
From Bixby, the guy that did C-PLEX,
and two Georgia Tech students,
etc., I would expect more than the usual
or just the OSL! I'd guess that they have
some good results in integer programming,
numerical stability, much larger problems,
exploitation of multi-core processors,
and more.
> 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.