Dear Stanimir, let me just take those questions which are specific to Gecode, I believe that the more general questions relating to how to model your problem are best asked in a more general setting (as in the constraints yahoo group or the comp.constraints newsgroup).
- There is no notion of relaxation built-in. - As it comes to starting point, just use those values you would like to keep from your previous solution and try to assign them to the variables in the new model. All the best Christian -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Stanimir Dragiev Sent: Friday, April 13, 2007 8:21 PM To: [EMAIL PROTECTED] Subject: [gecode-users] Recovery Scheduling as CSP/COP Hello to all on the list, I am new to Constraint Programming and GECODE, except that I took a look at some of the examples, particularly at queens, and implemented some examples of my own extending the Space class. I selected GECODE to accomplish a task within the work on my Diploma Thesis, because of its C++ interface and good performance. I post here the description of the problem I am solving and some questions in the hope that some of you might have had similar problems to solve and have hints and recommendations for doing it better. *Summary* I try to represent following problem as Constraint Optimization problem: Recovery scheduling in a dynamic (and heterogeneous) resources environment (with possible shortcoming of resources) with spatial and time dependencies between single jobs. *Approach* - representation I represent a schedule as a 3 dimensional matrix of positive integers. A point (an integer) with coordinates (j,r,t) stands for the amount of entities of resource <r> used by job <j> at time <t>. (Actually, this is a 4D structure ...) - constraints Since I didn't find commonly used or well known scheduling constraints framework to adapt to my problem, I defined my own ones using logical notation. In general the problem may be over-constrained, so I needed to extend relaxable constraints by "OR TRUE". - optimization Of course, it is desirable to have not simply one or all solutions satisfying the constraints, but also to specify some objective function, so that _in some terms_ optimal solution comes out. But having relaxable constraints this becomes a _must do_, if I see it correct.(Otherwise the trivial solution with no satisfied constraints comes out) - starting point Since this is a recovery scheduling, I can assume that the schedule available before the crash was optimal, and due to performance issues I would like to set it as starting point for the optimization, rather than start building solutions from scratch... *Implementation* - representation 3D structure of IntVars, including functions to return IntVarArray for every tuple (j,r,1..T), (j,1..R,t), (1..J,r,t) in order to use linear(...) without conversions. (Example: (1..J,r,t) holds the amounts of resource r used by the jobs at time t. So I can constrain the sum of them to be less then the capacity using linear()) - constraints I am aware that the cumulative() constraint is pretty mighty, but I really couldn't figure out how to use what it offers for my needs. So I did (am doing) it combining linear() rel() and post() (Example: for the constraint "resource r_x is not overloaded at time t_x" the sum of the elements of the IntVarArray (., r_x, t_x) should be less then capacity(r_x)). Perhaps not the most legal and efficient way? I think cumulatives(...) does not fit for my needs also because I want to have more fine grained control over which constrains are relaxed, and which not. I need this in order to be able to state sth. like "IF job j_x depends on j_y AND j_y is not scheduled THEN drop j_x too." - optimization I expected that there are means to "post" an objective functions and go relax :o) while GECODE optimizes the solutions found. But I didn't found any. So, what I think should work, is to post additional constraint dealing with this in the following way: IF for constraint("Solution_cost < N") there are non-trivial solutions THEN post constraint("Solution_cost < N-1"); - starting point I have currently no idea how this could work. Questions: #. Is there a way to post relaxable constraints and set priority on them? #. Is there a better way of implementing optimization #. (How) can I specify a "starting point" for generating solutions? Thank you in advance for any comments you make! greetz stanio _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
