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 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 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).

Piecewise linear constraints – constraints that define a piecewise linear relationship between two variables. These are defined via a set of breakpoints with linearly interpolated values between and beyond them (with the slope before the first and after the last point continuing the slope between the first/last two points). The piecewise linear functions are allowed to be discontinuous by defining multiple points with the same value of the input variable x, in which case the output variable y is allowed to take any value between the corresponding y-values of these breakpoints, while the first of them will define the slope before and the last will define the slope after this x-value. Piecewise linear constraints are useful to model e.g. transportation costs that are constant/linear in specific intervals but may jump between the different brackets.

General constraints – specific type of MIP constraints to model min, max, and, or, and absolute value relationships between two or more variables.

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