8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi Euglo, although @prubin’s answer is clear and self explanatory but let me ask this: should the model be in Java language only? If you are familiar with Python and it’s optimizations module (Pyomo), there are plenty of possibilities that I think can be used for your problem. Edit your question if it’s the case and if you need help. $\endgroup$ – Oguz Toragay Feb 19 at 7:44
  • $\begingroup$ @OguzToragay I added the relevant details. Unfortunately it has to be done in Java, but I appreciate any pointers to solutions in other languages as well — which, although irrelevant in this concrete case, might be useful if I have similar problems in the future. $\endgroup$ – Eugleo Feb 19 at 9:26
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ That's a great answer, thanks! I edited my question to better capture that I'm specifically looking for a solution in Java. Could you please edit the answer and include some recommendation for a Java CP-solver library? I found CP-SAT, a part of Google OR-Tools — would that be useable? $\endgroup$ – Eugleo Feb 19 at 9:41
  • $\begingroup$ I'm interested in OR, so I'm glad I learned about CP-solvers. However, in this concrete case, I'll have around 20 events, each with 10 possible dates. Are those low enough numbers to justify a brute-force method instead of the CP-solver one? $\endgroup$ – Eugleo Feb 19 at 9:43
  • 1
    $\begingroup$ I don't think enumerating all possible solutions would be possible with those dimensions. $\endgroup$ – prubin Feb 19 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.