Integer Linear Programming Flashcards
What is Integer Linear Programming (ILP)?
ILP is a type of optimization that seeks integer solutions to linear programming problems, useful where variables must be whole numbers, such as in resource allocation or scheduling.
How does ILP differ from LP in terms of solutions?
ILP solutions must be integers, which means the feasible region is discrete and not continuous as in LP, making ILP inherently harder to solve.
What are the types of ILP problems?
ILP problems can be categorized into binary (variables are 0 or 1), pure (all variables are integers), and mixed (combination of integer and continuous variables).
What are logical constraints in ILP and how are they modeled?
Logical constraints handle conditions like “if-then” or “either-or” and are modeled using binary variables and inequalities. For example, 𝑥1 + 𝑥2 ≥ 1 can model “x1 OR x2”.
Give an example of a real-world ILP problem.
Allocation of resources such as Covid vaccines to vaccination centers with the goal of minimizing wastage, considering constraints like availability of staff and operational hours.
What is the Branch-and-Bound algorithm?
A systematic method for solving ILP problems by sequentially breaking down the problem into smaller subproblems (branching), evaluating bounds on the optimal solution of subproblems, and pruning suboptimal solutions (fathoming).
What is LP relaxation in the context of ILP?
LP relaxation involves solving the LP problem obtained by ignoring the integer constraints of the ILP, which helps in providing bounds for the Branch-and-Bound algorithm.
What are the steps in Branch-and-Bound for solving ILPs?
The steps include initializing bounds and feasible solutions, branching to create subproblems, bounding by solving LP relaxations, and fathoming subproblems based on bounds or feasibility.
How are subproblems fathomed in Branch-and-Bound?
Subproblems are fathomed if their bound is worse than the best found solution, if their LP relaxation is infeasible, or if an integer optimal solution for the LP relaxation is found.
Why is solving ILP considered difficult?
ILP is NP-complete, which means there is no known polynomial-time algorithm to solve all instances of ILP efficiently, unlike LP which can be solved in polynomial time under typical conditions.
