4. Mixed integer problems

Question 1

Fig. definition MIP

Answer 1

• Z(X) denotes the optimal objective value over the feasible set X
• x and y denote the n-dimensional vector of non-negative continuous variables and the p-dimensional vector of non-negative integer variables, respectively

Question 2

Fig. Set of feasible solutions MIP

Answer 2

• c ∈ Rn and f ∈ Rp are the row vectors of objective coefficients
• b ∈ Rm is the column vector of right-hand-side coefficients of the m constraints
• A and B are the matrices of constraints with real coefficients of dimensions (m × n) and (m × p), respectively

Question 3

Fig. definition Mixed Binary Linear Program (MBP)

Answer 3

Question 4

Linear Relaxation (LR) of a Mixed Integer Program

Answer 4

obtained by removing the integrality restrictions on the y variables

Question 5

Key points LR

Answer 5

1: If in the solution to the linear relaxation all variables (that should be integer) have integer values, then it is also an optimal solution for the (mixed) integer problem
2: The optimal objective value for the linear relaxation will be lower than the one of the (mixed) integer program

Question 6

Lower bounds for a MIP

Answer 6

minimization -> linear relaxation
maximization -> any feasible solution

Question 7

Upper bounds for a MIP

Answer 7

minimization -> any feasible solution
maximization -> linear relaxation

Question 8

Fig. X and Px for MIP

Answer 8

Question 9

Running time of an algorithm

Answer 9

• defined as the number of elementary operations performed
• elementary operations are the elementary arithmetic operations (+, −, ×, /) and the comparison of two numbers.