4 - Mixed integer programming

Question 1

Definition of a Mixed Integer Program (MIP)

Answer 1

Question 2

Definition of a Mixed Binary Linear Program (MBP)

Answer 2

A mixed binary linear program (MBP), or mixed 0-1 program, is a MIP in which the integer variables y are further restricted to take binary values. This means that the feasible set X of a MBP is defined by

Question 3

Linear Relaxation of a Mixed Integer Program

Idea and Definition

Answer 3

Question 4

If in the solution to the linear relaxation all variables (that should be integer) have integer values, …..

Answer 4

then it is also an optimal solution for the (mixed)
integer problem

Question 5

Lower bounds for a MIP

Answer 5

Question 6

Upper bounds for a MIP

Answer 6

Question 7

Performance of an algorithm

2 performance measures

Answer 7

Question 8

Running time of an algorithm

Definition

Answer 8

The running time of an algorithm on a particular instance is defined as the number of elementary operations performed. The elementary operations are the elementary arithmetic operations (+, −, ×, /) and the comparison of two numbers.