Scheduling events in order to maximize preparation time

Question

Problem statement

I'm given a set of events $E$, and $\forall e \in E$ also:

1. a set of plausible dates on which the event can happen $D_e$
2. importance (weight) $w_e$
3. ideal preparation time duration $i_e$

I define preparation time for an event to be the number of days between that event and the previous event. I'd like to schedule the events so that:

1. on each day, there is at maximum one event scheduled
2. each event $e$ is scheduled on some day, and that day has to be in $D_e$
3. the preparation time of each event should be in some way proportional to its importance (the best case is for each event to have at least $i_e$ preparation time)

Solution details

I chose this topic as my semestral project for a Java class, so I'd like to implement the solution with the help of some Java library. I don't mind getting pointers for solutions in other languages as well, along the lines of "I'd use X normally, but given your situation, use the java bindings for Y".

I thought about using an optimizing SAT solver, but maybe there's some other, better way. If I'm not mistaken, I'll have to "translate" my abstract constraints into linear (in)equations, in order to be able to use a SAT solver. I can "linearize" the first and second constraint, but I'm not sure how to formulate the objective function that's to be maximized according to the third point.

The questions

1. Would you solve this with a SAT solver, or in some other way?
2. How would you formulate the objective function, most importantly the preparation time of event $e$, in such a way that it could be used in the SAT solver (or the alternative method of your choosing)?

Bonus question: Which Java library should I use to implement the [method you recommended in the first answer]?

Please note that I'm a total OR newbie, not educated about linear programming, constrained optimization, and such matters. If anything is unclear, ask in the comments and I'll try my best to clarify it.

Answer 1

If you use a constraint programming (CP) solver, I do not think you will need to convert constraints into algebraic expressions (at least not linear ones). Your first requirement can be handled by an "alldifferent" constraint, for which every CP solver I've heard of has an implementation.

Your second constraint just becomes the definition of the domain for the variable deciding when event $e$ occurs. You can try to get the ideal preparation time for every event through implication constraints

$$d_e = t \implies x_\tau = 0 \text{ for } \tau = t - i_e + 1, \dots, t - 1,$$

where $d_e$ is the date of event $e$ and $x_\tau$ is 1 if an event is scheduled for day $\tau$ and 0 if not. If you have to live with less than ideal preparation times, you can capture the deficiency in preparation time for event $e$ as

$$\max(0, i_e - (d_e - \max(\{t < d_e : x_t = 1\}))),$$

and penalize it in an objective function.

You can also formulate the problem as a mixed integer linear program (MILP) and use an appropriate solver. I can't predict whether CP would be faster than MILP or vice versa, but for small dimensions (not too many events, not too long a horizon) either should work well. I would probably try a CP model first.

Edit: I do not have much experience with CP solvers, but Håkan Kjellerstrand has a page on constraint programming that lists a number of CP solvers with Java APIs. CP Optimizer, part of IBM's CPLEX Studio suite, is a commercial CP solver with a Java API.