2
$\begingroup$

Is it possible to easily check if an instance of the 0-1 knapsack problem is unsolvable? Example: Assign 10 40-min tasks to 8 employees that have 60 minutes available each. Clearly, this instance is unsolvable as a 0-1 knapsack problem (but solvable as a fractional knapsack problem). I don't want to solve the 01-knapsack problem, but just detect if it is NOT solvable. Thanks in advance!

EDITED PROBLEM 1 - THOROUGH PROBLEM DESCRIPTION

Below is a more thorough problem description.

Tasks

I have a set of tasks with a given duration and a given time window each task has to be performed within (e.g the task duration for a given task could be 20 minutes and it has to be performed in the time interval 08:00-09:00). In addition, each task has a required skill, meaning that the employee carrying out the task needs to have a certain competence level (e.g tasks with required skill equal to 2 can only be carried out by employees with a competence level greater than or equal to 2).

Employees

I have a set of employees that work shifts. E.g an employee work from 08:00 to 13:00. Each employee has a given competence level, described above. The tasks are supposed to be allocated to the employees, and an employee cannot perform more than one task at the same time. E.g the same employee cannot perform BOTH task 1 (duration 10 minutes and time window 08:10-08:20) and task 2 (duration 30 minutes and time window 08:10-08:45). In addition, there are some tasks that a given employee cannot perform due to other reasons.

Problem

I want to check (preferably in polynomial time) a given problem instance (with tasks and employees) is not solvable, meaning that there exists some conflict such that it is impossible to allocate all tasks (see example above in original question formulation). To my understanding, it is NP-hard to solve the problem, but I just want to prove/detect that a given instance is unsolvable. Is it possible to easily check if there does not exist a possible assignment of tasks to employees?

EDIT 2 - BETTER DEFINITION OF THE GOAL

To be clear, I don't want an algorithm that ALLWAYS finds out if an instance is unsolvable or not. I am just looking for a way (an algorithm) that as OFTEN AS POSSIBLE finds out if the instance is unsolvable, and if the algorithm is uncertain (some efficient test did not detect that the instance was unsolvable) then I am fine with the problem instance being either solvable or unsolvable. So the algorithm I am looking for should detect as many "unsolvable instances" as possible, but not all.

Thanks in advance for your answers and contributions!

$\endgroup$
  • $\begingroup$ Can you define clearly the meaning of "a 0-1 knapsack problem is unsolvable"? Do you actually have a bin-packing problem? $\endgroup$ – Apass.Jack Mar 4 at 19:53
  • $\begingroup$ @Apass.Jack Clearly given the example, unsolvable means there does not exist a solution. And by "easily" I assume it means an efficient algorithm. And this problem is NP-complete. So the answer is unknown. $\endgroup$ – Reinstate Monica Mar 4 at 20:26
  • $\begingroup$ Can you edit the question to give a general specification of what you mean by "0-1 knapsack problem"? What are the inputs, and what is the desired output? A single example is not a substitute for a general description of the problem. Also, since your problem is likely to be NP-complete, please edit the question to tell us what counts as "easily check". Are you looking for a polynomial-time algorithm? An algorithm that will be efficient in practice? If the latter, what would be typical values of the parameters (number of tasks, number of employees, etc.)? Thank you! $\endgroup$ – D.W. Mar 4 at 21:11
  • $\begingroup$ @D.W. I have updated the problem description now. I might agree with previous comments that this problem is more similar to a bin-packing problem than the 0-1 knapsack problem (by 0-1 knapsack problem I mean that the objects (tasks) cannot be divided in fractions and allocated to multiple knapsacks (employees)). The inputs are presented above, my desired output is just to check if the problem instance is unsolvable, before I run it through my actual solving algorithm. Yes, efficient in practice - I get the input from others, so want to detect already at that stage if the input is not solvable. $\endgroup$ – Carl Holm Mar 5 at 12:21
  • $\begingroup$ @D.W. Typical value of parameters are 10 employees working from 08:00-15:30. 75 tasks, all with different duration and time windows. Typical duration is in almost all cases below 1 hours, on average around 15 minutes. Each task's time window is also varying a lot. E.g some have from 08:00-14.00 while others have from 11:10-11:20. $\endgroup$ – Carl Holm Mar 5 at 12:26
1
$\begingroup$

This is a complex set of constraints. The standard way to solve this kind of problem is using integer linear programming (ILP). Solving ILP instances is NP-hard -- so there is unlikely to be any polynomial-time algorithm -- but in practice, on real-world scheduling problems, solvers can often find a solution in a reasonable amount of time. For your parameters (10 employees, 75 tasks, a few dozen time slots), I would expect that ILP might be very effective. This kind of approach is widely used in operations research for scheduling.

So, use an ILP solver. You can even set a time limit, and then it will return either "solution found", "no solution exists", or "time exceeded". That will meet your requirement of identifying some instances that are unsolvable, efficiently.

$\endgroup$
0
$\begingroup$

Your problem is a bin packing decision problem with the possibility of additional constraints on which items each bin can hold. To be clear, the decision problem is simply deciding whether a given set of items fits in a given set of bins. This problem is a superset of the regular bin packing decision problem, which is NP-complete, so your problem is NP-complete.

Therefore an efficient solution exists iff P = NP.

$\endgroup$
  • $\begingroup$ Thank you for your answer! To be clear, I don't want an algorithm that ALLWAYS finds out if an instance is unsolvable or not. I am just looking for a way (an algorithm) that as OFTEN AS POSSIBLE finds out if the instance is unsolvable, and if the algorithm is uncertain (some efficient test did not detect that the instance was unsolvable) then I am fine with the problem instance being either solvable or unsolvable. So the algortihm I am looking for should detect as many "unsolvable instances" as possible, but not all. Does this change your answer? I have posted this comment as an edit as well. $\endgroup$ – Carl Holm Mar 5 at 13:16
  • $\begingroup$ @CarlHolm The requirement that you just want to check some instances was not in the question when I answered it. And "as often as possible" is not precisely defined. On this site it is considered bat etiquette to edit questions to change what they are asking. $\endgroup$ – Reinstate Monica Mar 5 at 13:55
  • $\begingroup$ I agree with you, I updated the question as your answer enlightened me on what I actually was seeking. Elaboration on "as often as possible": To my understanding, it is not possible with a 100% guarantee to detect if a problem instance is unsolvable without actually trying to solve that specific bin packing problem. But you could obviously make some preliminary tests, such as that the sum of bin sizes must be greater than or equal to the sum of the volume of objects to pack. But this check does not classify my original example as "unsolvable". Does my clarification change your answer? $\endgroup$ – Carl Holm Mar 5 at 15:31
0
$\begingroup$

The problem you are talking about is NP-Hard (as you have stated). But, I think there is a "simple" way to get a pseudo-polynomial time complexity algorithm to detect for a possible solution.

First let us simplify the problem to a single employee and their list of $N$ tasks that they could potentially complete where said employee has $F$ time to complete tasks. For this algorithm, we are going to ignore any priorities of the tasks. Therein, we are looking at an example of the Subset Sum Problem. This problem, although NP-Hard as well, has a pseudo-polynomial time dynamic programming solution with the time complexity of $O(FN)$. Since for your problem $F$ is constant for that day, the algorithm should essentially be $O(N)$.

Given that there are $E$ employees, we just apply the same algorithm to each of their assigned tasks to see if every employee ends up with a solution. Therein, the total time to check whether or not there is a solution comes out to $O(EN)$. Of course there might be some extra costs involved, such as producing the tasks that each employee can work, but it should still essentially be polynomial.

Now, this algorithm does not take into account priorities and dependencies of tasks. But, it should at least help in quickly determining there is not a solution. If it does indicate there might be a solution, you at least have a potential solution to work from.

TL;DR

There is an algorithm that has at least $O(EN)$ time complexity, where $E$ is number of employees and $N$ the number of tasks, that if indicates there is not a solution there is no solution. But, if it indicates there is a solution there still might not be a solution because of task priorities/dependencies/etc...

$\endgroup$

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.