Assignment Problem with continuous decision variable

Question

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:

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?

Answer 1

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!