Linear programming relaxation

Given a problem on LP form, except the extra requirement that some variables (a MIP problem) or all variables (a DOP problem) are required to take on a discrete set of values. The LP-relaxation of a MIP or a DOP is what we get if we drop these requirements.

Once we drop the requirement, we are in a situation where we may solve the problem, using one of the many known solvers for LP problems. We must however later check that the discrete requirements are fulfilled, which is generally not true, except for some special cases. (Eg. problems with totally unimodular matrix specifications.)

If this is not true, we may start a Branch and bound type process, where we fixate a single non set variable to a variable within the set.