Integer Programming

Integer programming (IP) is a special class of combinatorial optimization problems, which tends to be difficult to solve. The variables in linear programming (LP) are non-negative real numbers, but in many real-world applications, variables can only take integer values such as the number of staff or number of products. This chapter shows that the LP relaxation method can obtain the globally optimal solution. Different approaches are used to tackle integer programs in general. For this purpose, there are a few methods including the branch and bound, cut and bound, cutting planes, heuristic methods, and others. The chapter introduces the basic "branch and bound" method. The branch and bound method can be applied to solve such mixed integer programming (MIP) problems without any modification. There are a diverse range of applications of LP, from transport problem to scheduling.