title: Minimize number of unallocated tasks in PuLP
body: <p>I'm new to linear programming and am trying to use PuLP to allocate tasks to volunteers. I've generated some fake data below. In this fake dataset, each of 50 volunteers (numbered V1 to V50) were given a list of 100 tasks (numbered T1 to T100). They were asked to indicate which 7 tasks they were most willing to take up, and how many tasks they wanted to take up (they are allowed to take up to 3 tasks). Each task was also assigned a number between 1 to 3 which indicates how time-consuming the task is.</p>
  <p>I want to allocate the tasks to the volunteers in a way that ensures everyone gets a task, and that they don't get too many tasks / too heavy a workload. In my initial code, I also added a constraint that all tasks should be assigned at least one volunteer. However, with my real dataset (and also in this test dataset), I keep getting an infeasible solution because there aren't enough volunteers to cover all the tasks. I looked at other answers which suggested that I could loosen the constraint by adding a penalty. <strong>How do I either penalize unassigned tasks, or change my objective statement to minimize the number of unassigned tasks?</strong> My current objective statement just maximizes the number of assignments instead.</p>
  <pre><code>### CREATING DATA
  
  # Setting parameters
  np.random.seed(42)
  num_tasks = 100
  num_volunteers = 50
  
  # Creating list of 100 tasks numbered T1 to T100
  tasks = [f&quot;T{i}&quot; for i in range(1,num_tasks + 1)]
  
  # Each task is labelled with a number 1 - 3 that indicates estimated time taken to complete
  task_load = dict(zip(tasks, [np.random.choice([1,2,3]) for i in range(num_tasks)]))
  
  # Creating list of 50 volunteers numbered V1 to V50
  volunteers = [f&quot;V{i}&quot; for i in range(1,num_volunteers+1)]
  
  # Each volunteer is asked to choose 7 tasks to be assigned
  volunteer_choices = dict(zip(volunteers, [list(np.random.choice(tasks, size = 7)) for i in range(num_volunteers)]))
  
  # Each volunteer can choose to take between 1 - 3 tasks
  volunteer_max_tasks = dict(zip(volunteers, [np.random.choice([1, 2, 3]) for i in range(num_volunteers)]))
  
  
  ### DEFINING MODEL
  
  # Define model
  model = LpProblem(name = &quot;resource-allocation&quot;, sense = LpMaximize)
  
  # Define decision variables
  variables = LpVariable.dicts(&quot;Pair&quot;, (volunteers, tasks), 0, None, LpBinary)
  
  # Set list of all possible pairs
  pairs = [(v, t) for t in tasks for v in volunteers]
  
  # Set objective
  model += (lpSum([variables[v][t] for (v, t) in pairs]))
  
  
  ### SETTING CONSTRAINTS
  
  # All volunteers must be assigned at least one task
  for v in volunteers:
      model += (lpSum([variables[v][t] for t in tasks]) &gt;= 1)
  
  # Volunteers cannot be assigned to more tasks than they are willing to take on
  for v in volunteers:
      model += (lpSum([variables[v][t] for t in tasks]) &lt;= volunteer_max_tasks[v])
  
  # Volunteers cannot be assigned too high a work load
  for v in volunteers:
      model += (lpSum([variables[v][t] * task_load[t] for t in tasks]) &lt;= 6)
      
  # Volunteers cannot be assigned a task they didn't choose
  for v in volunteers:
      for t in tasks:
          if not (t in volunteer_choices[v]):
              model += (variables[v][t] == 0)
      
  # All tasks must get a volunteer (CAN I LOOSEN THIS?)
  for t in tasks:
      model += (lpSum([variables[v][t] for v in volunteers]) &gt;= 1)
  </code></pre>
  <p>I have to reiterate that I'm extremely new to linear programming. I'm not much of a programmer (just someone from an understaffed NGO with a bit of self-taught Python knowledge) and I started looking into PuLP specifically to solve simple task allocation problems like this. So I hope in your answer, instead of &quot;narrating&quot; the solution (e.g. &quot;Create a variable for X and then include it in your objective function&quot;) you can write out the code instead, if possible? Some questions that seem related are <a href="https://stackoverflow.com/questions/57288073/minimize-the-number-of-outputs/57316021#57316021">this</a> and <a href="https://stackoverflow.com/questions/67482439/how-do-i-make-a-constraint-elastic-in-pulp">this</a>? But I was unable to figure out how to adapt it to my problem.</p>
  <p>I originally also had a last constraint which limits the number of volunteers assigned to each task to 3, but I removed it in an attempt to massage out a feasible solution.</p>
  <pre><code># Each task cannot be assigned more than 3 volunteers
  for t in tasks:
      model += (lpSum([variables[v][t] for v in volunteers]) &lt;= 3)
  </code></pre>
  <p><strong>CLARIFICATIONS ON OBJECTIVES:</strong>
  We generally want to ensure that every volunteer who signed up for the program gets a task! For context, examples of programs that require task allocation may include outreach programs with schools, where every student is tasked to work on small project(s) related to our cause so that they can learn more about it. <strong>As such, we don't have so much concerns about efficiency (getting as little workers to do as many tasks as possible), so much as ensuring every student gets a task in a way that minimizes the number of unassigned tasks.</strong> I hope that makes a little more sense with context...</p>