PLE 2024

Which of the following is a characteristic of Integer Linear Programming (ILP)?

• It can only be solved using graphical methods.

• It allows for variables to be either integers or continuous

• It involves optimizing a linear function subject to linear constraints.

• It is a special case of linear programming (LP) where all variables must be integers.

True or false question. In the branch-and-bound (B&B) method, the optimal solution to the LP relaxation always provides a lower bound on the optimal solution to the ILP problem.

• True

• False

Completion question:. In B&B, each subproblem is created by adding a ________ constraint to the original problem.

• Branching constraint

• Planning contraint

• Aditional Variable

• Other answer

What is the key characteristic of Integer Linear Programming (ILP)?

• It can only be solved using graphical methods.

• It allows for variables to be either integers or continuous

• It involves optimizing a linear function subject to linear constraints.

• It is a special case of linear programming (LP) where all variables must be integers.

The document states that "the non-integer solution to the original problem" is eliminated in both subproblems. Explain why it is important to eliminate this solution.

• The non-integer solution is eliminated because it is not a feasible solution to the ILP problem, which requires all variables to be integers. Including this solution in the search space would lead to incorrect results

• In ILP, we optimize a situation with integer-valued variables representing real-world quantities like the number of items produced. The document mentions eliminating the "non-integer solution" from both subproblems created during the branch-and-bound method. This is crucial because this solution violates the fundamental characteristics of ILP. Imagine solving a problem about producing chairs. The optimal solution might be 10.5 chairs in continuous relaxation (ignoring integer constraints), but that's physically impossible. We eliminate this non-integer solution to focus on feasible options like producing 10 or 11 chairs, representing real-world possibilities.

• The non-integer solution is eliminated because integer linear programming (ILP) requires all variables to be whole numbers. Including this solution would lead to unrealistic and invalid results for the problem. Imagine building half a table—it wouldn't make sense!

• All the answers are true