[gecode-users] Recovery Scheduling as CSP/COP

[Stanimir Dragiev]

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