Mixed Integer Programs (MIPs)

Many problems can be modeled satisfactorily as Linear Programs (LPs), i.e., with variables that are only restricted to having values in continuous intervals. However, a common class of problems requires modeling using discrete variables. These problems are called Mixed Integer Programs (MIPs). MIP problems are often hard to solve and may require large amounts of computation time to obtain even satisfactory, if not optimal, results.

Perhaps the most common use of the FICO Xpress Optimization Suite is for solving MIP problems and it is designed to handle the most challenging of these problems. Besides providing solution support for MIP problems the Optimizer provides support for a variety of popular MIP modeling constructs:

Binary variables – decision variables that have value either 0 or 1, sometimes called 0/1 variables;

Integer variables – decision variables that have integer values;

Semi–continuous variables – decision variables that either have value 0, or a continuous value above a specified non–negative limit. Semi–continuous variables are useful for modeling cases where, for example, if a quantity is to be supplied at all then it will be supplied starting from some minimum level (e.g., a power generation unit);

Semi–continuous integer variables – decision variables that either have value 0, or an integer value above a specified non–negative limit;

Partial integer variables – decision variables that have integer values below a specified limit and continuous values above the limit. Partial integer variables are useful for modeling cases where a supply of some quantity needs to be modeled as discrete for small values but we are indifferent whether it is discrete when the values are large (e.g., because, say, we do not need to distinguish between 10000 items and 10000.25 items);

Special ordered sets of type one (SOS1) — a set of non–negative decision variables ordered by a set of specified continuous values (or reference values) of which at most one can take a nonzero value. SOS1s are useful for modeling quantities that are taken from a specified discrete set of continuous values (e.g., choosing one of a set of transportation capacities);

Special ordered sets of type two (SOS2) – a set of non–negative variables ordered by a set of specified continuous values (or reference values) of which at most two can be nonzero, and if two are nonzero then they must be consecutive in their ordering. SOS2s are useful for modeling a piecewise linear quantity (e.g., unit cost as a function of volume supplied);

Indicator constraints – constraints each with a specified associated binary 'controlling' variable where we assume the constraint must be satisfied when the binary variable is at a specified binary value; otherwise the constraint does not need to be satisfied. Indicator constraints are useful for modeling cases where supplying some quantity implies that a fixed cost is incurred; otherwise if no quantity is supplied then there is no fixed cost (e.g., starting up a production facility to supply various types of goods and the total volume of goods supplied is bounded above).

All of the above MIP variable types are collectively referred to as global entities.