 |
|
| Computers Forum Index » Computer - Constraints » Constrained Optimization (what's beneath the surface... |
|
Page 1 of 1 |
|
| Author |
Message |
| yarrow.roy at (no spam) gmail.com... |
 Posted: Wed Apr 22, 2009 5:06 pm |
|
|
|
Guest
|
Newbee in the area.
My question is about CP optimization solvers and Ilog CP Optimizer
specifically.
The appeal of a CP optimizer is the ability to deal with problems that
cannot be easily linearized or solved by traditional MP.
However I wonder about the efficiency of a CP system if it does not
incorporate, or hybrid with some of the OR relaxation methods...
So reading about the Ilog CP Optimizer:
"The CP approach to optimization is completely different than the MP
approach. CP finds efficient solutions—feasible combinations and good
assignments of resources and activities (...). It then works to
improve the solution until nothing better can be found."
I wish to get some clarifications on the following:
I read the statement as the solver finds a first solution (the ways to
get to a first solution is another question), then from this solution
works at finding a better solution, or proving there is none better.
I assume that the process of finding a better solution uses a mix of:
- branch and bound techniques or other OR inherited technics and
proper heuristic functions.
- proper variable ordering heuristics, etc.
Right?
The reason for that question is that I had discussion with people
telling me, that a way to solve a CP opt problem can be easily
achieved by using straight CSP and preferences (as stated by U.
Junker).
To my point of view this would be naive, and not fitting with the
Optimization mandate (finding a 'best' solution efficiently).
To clarify, consider a problem where you have a set of variables
(logic, sets, integers, etc.) and constraints (set, arithmetic, logic,
etc.). let's consider that the constraint graph is sparse in some
areas, and dense in others.
And let's consider than one of these variables is a price that is
defined as the sum of all the 'pricable' elements in the solution
(therefore a subset of the variables of the problem will add to this
price).
Then consider you want to minimize the price. Consider the underlying
domain of this price an integer range domain -- the modeler should not
have to compute all the possible prices, to define a proper enumerated
set of integers, of course. Let's consider the level of consistency
checking is not global.
Then tackling the optimization problem as solving the problem with a
variable ordering that sets the 'price' variable as the first choice
point in the search tree, and with a heuristic defined on the price
such as a 'min first' or even a domain splitting that aims at
preferring the lower values of the price, does not seem a good
technique at all to reach an optimized solution 'efficiently'. Such a
variable is a receiving end of all the items that are placed in the
solution, and for that reason is a bad first choice.
Right?
Thanks a lot for your time, - Yarrow |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Sun Nov 29, 2009 1:01 am
|
|