[gecode-users] Recovery Scheduling as CSP/COP

[Christian Schulte]

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: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Stanimir Dragiev
Sent: Friday, April 13, 2007 8:21 PM
To: users at gecode.org
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
users at gecode.org https://www.gecode.org/mailman/listinfo/gecode-users