First we start with what 'mathematical' programming
(optimization) is. For a reasonably general definition,
let R denote the set of real numbers and m and n be
positive integers. Let R^n be real n-dimensional
space, that is, the set of n-tuples of real numbers.
Let x be in R^n.
Next we have two functions. We have an 'objective'
function f: R^n --> R, and we have a 'constraint'
function g: R^n --> R^m. We can think of g as
m functions mapping R^n --> R. Then the optimization
problem is to find x so that f(x) is as large as
possible while g(x) = 0 where here 0 is the
point in R^m with all components 0. Or we can
ask that g(x) <= 0 by which we mean that each of
the m components of g(x) is <= 0 in R. In 'linear
programming', functions f and g are both linear.
So, function f is given by just n coefficients, and
function g is given by an m x n matrix.
If there exists x in R^n so that g(x) = 0
(or <= 0 for that version of the problem), then
x is a 'feasible' solution. If x is feasible
and for any feasible solution u in R^n we have
that f(x) >= f(u), then x is an 'optimal'
solution.
Linear programming where we ask that all the
components of x be integers is 'integer' linear
programming (ILP) and is in NP-complete. Industry
is awash in important ILP problems, e.g., airline
scheduling. There is an enormous literature on
practical means of solving ILP problems; Google
Nemhauser long at Georgia Tech.
The problem may fail to be feasible. If the problem
is feasible, it may fail to have an optimal solution.
Constraint programming is the same except we have
no objective function and are looking for just
feasible solutions.
Since in principle finding a feasible solution is
as hard as finding an optimal solution, constraint
programming is essentially the same subject as
mathematical programming (optimization).
Constraint programming is nice when a planner is
just trying to get some work done and knows that
the cost will be the same for all alternatives.
E.g., maybe yesterday they killed 5000 hogs,
overnight chilled them down, today are cutting
them into pieces and putting the pieces into
boxes, and during the day want to back 18 wheel
refrigerated trucks into the small loading dock
in the right order to get all the boxes loaded
and each truck with the boxes it needs for its
deliveries. Once a real problem.
SAP in Germany has wanted to offer constraint
programming as part of its software suite.
Since constraint programming is essentially
the same (mostly just different in how the
user sees it and, thus, the user interface)
as mathematical progamming, at one time SAP
worked with C-PLEX, with some of the best
software for linear and integer programming,
the company of R. Bixby, long at Rice U.
First we start with what 'mathematical' programming (optimization) is. For a reasonably general definition, let R denote the set of real numbers and m and n be positive integers. Let R^n be real n-dimensional space, that is, the set of n-tuples of real numbers. Let x be in R^n.
Next we have two functions. We have an 'objective' function f: R^n --> R, and we have a 'constraint' function g: R^n --> R^m. We can think of g as m functions mapping R^n --> R. Then the optimization problem is to find x so that f(x) is as large as possible while g(x) = 0 where here 0 is the point in R^m with all components 0. Or we can ask that g(x) <= 0 by which we mean that each of the m components of g(x) is <= 0 in R. In 'linear programming', functions f and g are both linear. So, function f is given by just n coefficients, and function g is given by an m x n matrix.
If there exists x in R^n so that g(x) = 0 (or <= 0 for that version of the problem), then x is a 'feasible' solution. If x is feasible and for any feasible solution u in R^n we have that f(x) >= f(u), then x is an 'optimal' solution.
Linear programming where we ask that all the components of x be integers is 'integer' linear programming (ILP) and is in NP-complete. Industry is awash in important ILP problems, e.g., airline scheduling. There is an enormous literature on practical means of solving ILP problems; Google Nemhauser long at Georgia Tech.
The problem may fail to be feasible. If the problem is feasible, it may fail to have an optimal solution.
Constraint programming is the same except we have no objective function and are looking for just feasible solutions.
Since in principle finding a feasible solution is as hard as finding an optimal solution, constraint programming is essentially the same subject as mathematical programming (optimization).
Constraint programming is nice when a planner is just trying to get some work done and knows that the cost will be the same for all alternatives. E.g., maybe yesterday they killed 5000 hogs, overnight chilled them down, today are cutting them into pieces and putting the pieces into boxes, and during the day want to back 18 wheel refrigerated trucks into the small loading dock in the right order to get all the boxes loaded and each truck with the boxes it needs for its deliveries. Once a real problem.
SAP in Germany has wanted to offer constraint programming as part of its software suite. Since constraint programming is essentially the same (mostly just different in how the user sees it and, thus, the user interface) as mathematical progamming, at one time SAP worked with C-PLEX, with some of the best software for linear and integer programming, the company of R. Bixby, long at Rice U.