From: Kish Shen <kisshen_at_cisco.com>

Date: Thu, 03 Jan 2008 07:47:50 +0000

Date: Thu, 03 Jan 2008 07:47:50 +0000

Amine Marref wrote: > Hi Folks, > > Can anybody spare some time to answer this very question. > > I use Eclipse as a constraint solver in my research. I am not sure > though that this is the right investment. > > The problems I model *all* have the following properties. > > * All variables are integers. > * At least two thirds (2/3) of the variables have domain [0..1]. > * Each variable in the other remaining third (1/3) of variables can take > a finite number of different values only, usually less than 20. > * The number of variables is in tens of thousands (50000 variables is > the average). > * All constraints are linear: addition, subtraction, and implication are > used. > * The objective function is non-linear, expressed as: (Obj=B1*C1 + B2*C2 > + ... + Bn*Cn) where Bi, Ci are integer variables. > > Currently I use > bb_min(search(Vars,0,input_order,indomain_split,complete,[]) from > "branch_and_bound" to do the search (Vars is the list of all variables > in the program). > > The search takes ages. > > Any suggestions for improvement? Or is there a more appropriate > constraint solver for this? > > Thanks a lot, > > Amine. > > Hi Amine, I assume you are already using the ic (lib(ic)) solver of ECLiPSe to solve your problem? It is difficult to make any suggestions without more knowledge of your problem, except to say that if your problem is taking too long to optimise, then you may need to find more ways of reducing the search space, e.g. by producing a good estimation of the bounds on your optimal objective value, and to post more effective constraints. You could try using an external Mathematical Programming solver via lib(eplex) to solve your problem, or you can use it in co-operation with other solvers in ECLiPSe in a hybrid way -- there is a lot of research in this area, and you may want to look through the relevant conference proceedings (e.g. the CP-AI-OR conferences) for the work in this area. With ECLiPSe 5.10, you will need to use either CPLEX and XPRESS for your problem with eplex, as you have a quadratic objective function, and solving such QP problem with the open-source COIN-OR solvers is not supported with eplex in 5.10 (it is supported by 5.11, which is not yet released).You will need to be able to express your problem constraints as a MP problem (i.e. equalities and inequalities over linear expressions) to use this. Cheers, KishReceived on Thu Jan 03 2008 - 07:48:14 CET

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*