ISYE 6669 ISYE 6669 Final Exam

ISYE 6669 / ISYE 6669 Final Exam (Latest Update 2025 / 2026) Deterministic Optimization | Questions & Answers | Grade A | 100% Correct - Georgia Tech

Question:

What is the general formulation for the set packing problem?

Answer:

Given weights w for binary variables x where each constraint contains a subset of x. Maximize w given that each subset is disjoint.

Question:

What is the network flow supply constraint?

Answer:

Leaving flow - entering flow = supply

• / 3

Question:

What is so special about network flow problems when dealing with integers and LP?

Answer:

If all supply and capacity data are integers, then every extreme point (ie BFS) will be an integer. Thus the network flow problem can be solved using simplex even though it is a Mixed Integer Linear Program (ie not Standard Form LP).

Question:

How do you relax an MILP? What are some properties of the relaxed LP?

Answer:

Turn the integer variables into continuous variables. If the LP relaxation is infeasible, so is the MILP. If the LP has an optimal solution, the MILP may still be infeasible or also have an optimal solution. If LP is unbounded, then MILP is unbounded or infeasible. the relaxed optimal solution is always less than or equal to the MILP optimal solution. If the optimal solution to the relaxed problem is integral, then that is the optimal solution to the MILP.

• / 3

Question:

What is a stronger formulation for a MILP? What benefits do we get from stronger formulations?

Answer:

A more restrictive set of constraints that contain the same feasible solutions.This leads to better optimality gaps, better relaxation bounds, and sometimes relaxation LP's with feasible solutions to the MILP.

Question:

How do we create a stronger formulation to a MILP?

Answer:

By adding new tightening inequalities, by tightening constraint coefficients to current constraints, and by introducing new variables and constraints to those variables.

Question:

What does a two stage stochastic problem consist of? What is the objective of the problem?

Answer:

A here and now decision and a wait and see decision. Minimize production cost and expected future cost

• / 3