Feasibility Problem

A feasibility problem examines if there exists a solution that satisfies a set of constraints, rather than finding the optimal solution. The goal is to determine possible feasibility.

Java - Subset Sum example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
boolean hasSubsetSum(int[] set, int sum) {
  boolean[][] dp = new boolean[set.length+1][sum+1];

  for (int i = 0; i <= set.length; i++) {
    dp[i][0] = true;
  }
  
  for (int i = 1; i <= set.length; i++) { 
    for (int j = 1; j <= sum; j++) {
      if (set[i-1] <= j) {
        dp[i][j] = dp[i-1][j] || dp[i-1][j-set[i-1]];  
      } else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  return dp[set.length][sum]; 
}

C++ - Hamiltonian Path example:

1
2
3
4
5
6
7
8
9
bool hasHamPath(vector<vector<int>> graph) {
  vector<bool> visited(graph.size(), false);
  return hamiltonianPath(graph, 0, visited); 
}

bool hamiltonianPath(vector<vector<int>>& graph, int v, vector<bool>& visited) {
  // Backtracking algorithm
  return false; 
}

Python - Clique example:

1
2
3
def hasClique(graph, k):
  # Backtracking/DFS  
  return False

Feasibility problems appear in scheduling, resource allocation, and constrained optimization.

A feasibility problem is a type of optimization problem where you are more interested in finding a feasible solution that satisfies all constraints rather than optimizing an objective function. It asks a simple question: “Is there a solution that meets all the given constraints?”

Algorithm

Identify Constraints: List all constraints that a solution must satisfy.
Find Feasible Solution: Use algorithms or logical deduction to find any solution that satisfies all constraints.

Let’s consider an example where you have 5 tasks and 3 workers. The goal is to find out if all tasks can be assigned to workers such that no worker has more than 2 tasks.

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class Feasibility {
    public static boolean isFeasible(int tasks, int workers, int maxTasksPerWorker) {
        return tasks <= workers * maxTasksPerWorker;
    }

    public static void main(String[] args) {
        int tasks = 5;
        int workers = 3;
        int maxTasksPerWorker = 2;
        System.out.println("Is feasible: " + isFeasible(tasks, workers, maxTasksPerWorker));
    }
}

C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <iostream>

bool isFeasible(int tasks, int workers, int maxTasksPerWorker) {
    return tasks <= workers * maxTasksPerWorker;
}

int main() {
    int tasks = 5;
    int workers = 3;
    int maxTasksPerWorker = 2;
    std::cout << "Is feasible: " << std::boolalpha << isFeasible(tasks, workers, maxTasksPerWorker) << std::endl;
    return 0;
}

Python Code:

1
2
3
4
5
6
7
def is_feasible(tasks, workers, max_tasks_per_worker):
    return tasks <= workers * max_tasks_per_worker

tasks = 5
workers = 3
max_tasks_per_worker = 2
print(f"Is feasible: {is_feasible(tasks, workers, max_tasks_per_worker)}")

In this example, we’ve used a simple formula to determine if it’s feasible to distribute tasks among workers under the given constraints. All the code snippets in Java, C++, and Python perform this check.