# Assignment Problem with continuous decision variable

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?

• integrality property Jun 1, 2022 at 12:06
– Rob
Jun 1, 2022 at 13:54
• Your second constraint is a bit odd. I would expect the machines to have individual capacity limits.
– prubin
Jun 1, 2022 at 16:08
• @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. Jun 1, 2022 at 18:55

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!