-1
$\begingroup$

I have to solve a problem from industry where there are a number of machines which should be assigned to a number of tasks. The difference from the general assignment problem is tough, that the decision variable x is not a binary, it is a value between [0,1]. So that one machine can do 0.5(50%) of the task and another one can complete the task,does that make sense? I definied the problem like this:

enter image description here

When I program this problem in python with docplex, the solver is giving me only values of 1. Why there are no continuous values like 0.5 etc. Is there even a possibility that the mathematical optimal solution is a continuous value, or will this model always give binary results because there is a mathematical reason and maybe proof to that? So Does it even make sense to declare the decision variable as contionuous rather than binary?

$\endgroup$
4
  • 2
    $\begingroup$ integrality property $\endgroup$
    – Kuifje
    Commented Jun 1, 2022 at 12:06
  • 1
    $\begingroup$ Please use MathJax on this site, instead of uploading equations as images. Thank you. $\endgroup$
    – Rob
    Commented Jun 1, 2022 at 13:54
  • $\begingroup$ Your second constraint is a bit odd. I would expect the machines to have individual capacity limits. $\endgroup$
    – prubin
    Commented Jun 1, 2022 at 16:08
  • $\begingroup$ @Harun Gul, welcome to ORSE. Besides other useful comments and answers please be aware that, the problem you mentioned is classified as mixed-integer programming, but still there are the cases you can formulate your problem as a linear program to get what you want. $\endgroup$
    – A.Omidi
    Commented Jun 1, 2022 at 18:55

1 Answer 1

2
$\begingroup$

Is there even a possibility that the mathematical optimal solution is a continuous value

I would say it depends on the parameterization, i.e., the values of c and t and b in your problem. From your description, it seems entirely possible to have a parameterization that leads to an optimal solution with integer values. Generally, it is a good practise to start with a tiny example which you can fully solve and understand manually

I would suggest to test your implementation with a minimal example which you construct in a way that you know the optimal solution is fractional. Here is a suggestion:

Lets say there is just one task, so $J = \{1\}$ and two machines $I = \{1,2\}$ You have the following constraint:

$$4x_1 + 2x_2 \leq 3$$ I am omitting the task index here. Now, $t_1$ is larger than $b$, so $x_1=1$ would be an infeasible solution. Finally, you can prevent $x_2=1$ from becoming optimal by selecting objective coefficients that favor $x_1$, e.g., $c_2=5$ and $c_1=1$. Independent of the values for the $c_i$,as long as the second machine is more expensive than the first, the optimal solution should be $x_1=x_2=0.5$ because you still have the constraint that the one task has to be completely fulfilled, so

$$x_1 + x_2 =1$$ still has to be fulfilled.

Hope this helps figuring out what's going on!

$\endgroup$

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.