-1
$\begingroup$

I have a constraint optimization problem as follows:

  • I need to assign $m$ tasks to $n$ days, with $n \geq m$.
  • Each day can host 0 to $m$ tasks.
  • Each task either belongs to type $A$ or $B$.
  • I want to assign the tasks to the days such that tasks of the same type are grouped as much as possible on the same days (minimize mixing tasks of different types on the same day)
  • I have a set of constraints indicating the days on which each task can occur.
  • Moreover, the number of days that is used to host all the tasks should also be minimized. For instance: If the constraints allow hosting 2 tasks of the same type either on 2 different days or otherwise on the same day, hosting the 2 tasks on the same day should have preference.

I'm having issues finding a formulation of this problem that can be solved. My first thought is to use an $m\times n$ matrix $M$ where if $M(i,j) \neq 0$ it means that task $i$ occurs on day $j$. $M(i,j) = 1$ if the task is of type $A$, $M(i,j) = -1$ if the task is of type $B$.

I think part of my optimization objective should express that I want to minimize Shannon entropy: $-\sum p \dot \log(p)$. The zeros in my matrix are not relevant for the entropy calculation so when I compute $p$ I need to divide 2 variables: The number of tasks of group $A$ or $B$ divided by the total number of tasks on that day. I don't know the number of tasks on a given day beforehand since this is part of the optimization so I get a division of 2 variables.

I also tried an alternative for entropy in the objective function: I sum all the 1's and -1's on each day and then take the absolute value: The larger this sum, the higher the orderliness of that day. But again, when wanting to compare the 'orderliness' of 2 days with a different number of activities on them, I have to divide by the number of activities on that day, which is again division of 2 variables.

I've tried solving this problem with OR-tools and CVXPY but I get error messages like: The problem does not adhere to "disciplined convex programming". As I understand it, the division of 2 variables is a problem. Even worse, it is possible that a day has 0 activities and then I get a division by zero.

Is there any other formulation of this optimization problem that would not cause these problems?

$\endgroup$
5
  • $\begingroup$ You can probably model this as an integer linear program if you can quantify "minimize mixing tasks" more precisely. Do you want to minimize the number of days where tasks are mixed (regardless of how many tasks are being mixed on any given day)? If not, can you provide a formula for the penalty for mixing $a$ tasks of type A and $b$ tasks of type B on the same day? $\endgroup$
    – prubin
    Mar 8, 2023 at 16:36
  • $\begingroup$ Hi @prubin, yes, I am proposing 2 penalties for mixing the tasks of different types in my question (e.g. entropy) but the problem is that these penalties contain a division by a variable (number of tasks on a day), which could even be 0. $\endgroup$
    – Waldo
    Mar 9, 2023 at 10:14
  • $\begingroup$ It might help if you edited the question to show the explicit formula you have in mind for the penalty. $\endgroup$
    – prubin
    Mar 9, 2023 at 16:25
  • $\begingroup$ This is a possible formulation in or-tools (not using entropy but summing 1's and -1's), but I'm not sure it's useful without the rest of the code: model.Maximize(w1*lp.Sum([day_cost_abs[j] for j in range(data["nb_slots"])])/data["nb_tasks"] + w2*lp.Sum([is_col_zero[j] for j in range(data["nb_slots"])])) $\endgroup$
    – Waldo
    Mar 10, 2023 at 16:00
  • $\begingroup$ The only division I see is by data["nb_task"]. Is that a variable?? The name would suggest it is a parameter ("data"). $\endgroup$
    – prubin
    Mar 10, 2023 at 16:38

2 Answers 2

0
$\begingroup$

You could try implementing the condition $x * y = z$ by expanding $x$, $y$, and $z$ as binary vectors $x^b$, $y^b$,$z^b$. I.e. $\Sigma x^b = \Sigma y^b = \Sigma z^b = 1$, $z^b_{i \cdot j} >= x^b_i + y^b_j - 1$. Then you can recover $z = \Sigma_i i \cdot z^b_i$. But this will probably be slow. Maybe try big-$M$ reformulation (or enforcement variables) to assign a score for each day to each combination of $A$ and $B$ task counts.

$\endgroup$
0
$\begingroup$

You can define a parameter $\tau_t= 1$ if tasks $t$ is from set A, -1 otherwise. In that case your $ m_{t,d}=1$ if task $t$ is assigned on day $d$, becomes a binary. you can use $ \sum_t \tau_t m_{t,d}$ to sum up for the day.

As for division of two variable like $ x\over y$ always define another variable $z$ with a bilinear constraint $ y*z = 1$. Then it comes expression involving division as quadratic $ xz$. As for ${x\over y}log {x\over y}$, it will be turned into $ xz(logx+logz)$.
Depending upon solver you need to smoothen log.

$\endgroup$
1
  • $\begingroup$ Thanks for your suggestion. I have tried implementing this in CVXPY, however, I get "DCPError: Problem does not follow DCP rules." Specifically for the bilinear and the log constraint. $\endgroup$
    – Waldo
    Mar 16, 2023 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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