4
$\begingroup$

I have a problem where there are stations, types and tasks which has to be assigned to each other. Now for me the thing is I want the variable $x$ to be not binary like in assignment problem for example but between $[0,1]$. Now I wanted to add a constraint which says something like that: the tasks are fractional (able to split) yes but there should not be too tiny splits because it is just not good for the implication in the real production process. Therefore I thought of a parameter for example $Z^\min$ which I give a value of e.g. $10$. I need to say that the duration of every $x$-tuple (station, type, task) is larger than at least $10$. So that even there is a split an $x(1,1,1) = 0.5$ so only half of the original task is assigned, there is never an assignment of $x$ which makes the duration smaller than 10. Therefore I have an approach and think it is makes sense but wanted to take other opinions on that. Here the one constraint I talked about and following the complete model:

\begin{align} & \sum_{j=1}^{J} d_{ijk}\cdot x_{ijk} \geq Z^{\min} \cdot x_{ijk} &&\text{$\forall \, i \in I$, $\forall \, k \in K$} \end{align}

\begin{aligned} &\text{min} &&\sum_{i=1}^{I}\sum_{j=1}^{J}\sum_{k=1}^{K} c_{ijk}\cdot x_{ijk} &&+\sum_{i=1}^{I}\sum_{j=1}^{J} f_{ij} \cdot \gamma_{ij} \\ &\text{s.t.} &&\sum_{i=1}^{I}\sum_{j=1}^{J} x_{ijk} &&= 1 &\text{$\forall \, k \in K$} \\ &&&\sum_{j=1}^{J} \gamma_{ij} &&= 1 &\text{$\forall \, i \in I$} \\ &&&\sum_{j=1}^{J}\sum_{k=1}^{K} d_{ijk}\cdot x_{ijk} &&\leq C ^ {\max} \cdot \gamma_{ij} &\text{$\forall \, i \in I$} \\ &&& \sum_{j=1}^{J} d_{ijk}\cdot x_{ijk} &&\geq Z^{\min} \cdot x_{ijk} &\text{$\forall \, i \in I$, $\forall \, k \in K$} \\ &&&\sum_{i=1}^{I} i \cdot x_{ik} && \leq \sum_{i=1}^{I} i \cdot x_{im} &\text{$\forall \, j \in J$} \\ &&& x_{ijk} \in [0,1], && \gamma_{ij} \in \{0,1\} \end{aligned}

$\endgroup$

1 Answer 1

3
$\begingroup$

Your proposed constraint is indexed over $i$ and $k$, but the expression on the RHS depends also on $j$. It sounds like you want the LHS to be either $0$ or at least $Z^\min$, which you can enforce by introducing a binary variable $y_{ik}$, changing the RHS to $Z^\min y_{ik}$, and imposing an additional constraint $\sum_j d_{ijk} x_{ijk}\le M_{ik} y_{ik}$, where $M_{ik}$ is a (small) upper bound on the LHS when $y_{ik}=1$. Essentially, you want to enforce that $\sum_j d_{ijk} x_{ijk}$ is semicontinuous.

Your third and fifth constraints have similar parsing errors.

$\endgroup$
3
  • $\begingroup$ What if I only say >= Z^min for the RHS because let me explain with an example. If the task 1 specifically on station 1 and type 1 so basically tuple (1,1,1) has a duration of 50 originally, but the task is splitted up so that x(1,1,1) is only 0.5, than the duration of the task on that combination while last 25 seconds. And all these kind of combinations must be at leat for example a given value of 10. And if it is not than this kind of assignment will not be made. Think that your approach is over my scope a bit. $\endgroup$
    – Harun Gül
    Sep 26 at 7:41
  • $\begingroup$ That change would also prevent the LHS from being $0$. Is that what you want? $\endgroup$
    – RobPratt
    Sep 26 at 13:01
  • $\begingroup$ If the LHS would be 0 there would be the problem that it would say: 0 >= Z which is false. For that case I tried to do put the x also on the RHS. Maybe is there just an error with the Indexing on the sum and on the for all i and k? $\endgroup$
    – Harun Gül
    Sep 26 at 14:58

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.