Answer each question with True or False. You do not need to justify your answers. 1. (4 points) When the primal linear program is infeasible, the dual linear program may still be feasible. 2. (4 points) Suppose a primal linear program has multiple optimal solutions, and its dual linear program also has multiple optimal solutions. Then, any pair of a primal optimal solution and a dual optimal solution satisfies all the primal complementary slackness and dual complementary slackness conditions. 3. (4 points) Suppose you use the branch-and-bound algorithm to solve an integer program with a minimization objective. If, at a node in the branch-and-bound tree, the LP relaxation's optimal objective value of this node is strictly lower than the objective value of the best integer solution found so far, then we can stop branching at this node. 4. (4 points) Suppose an integer linear program has a nonempty bounded feasible region. Every extreme point of its integer hull must be an integer feasible solution. 5. (4 points) If a standard form LP has an unbounded optimum, then the simplex method, when applied to solve this LP, will never terminate