Stating a MIP problem

Defines the kind of problems that the mixed integer optimizer solves.

A mixed integer programming (MIP) problem may contain both integer and continuous variables. If the problem contains an objective function with no quadratic term, (a linear objective), then the problem is termed a Mixed Integer Linear Program (MILP).

Tip:

The all zero objective function associated with a feasibility problem is also a linear objective.

If there is a quadratic term in the objective function, the problem is termed a Mixed Integer Quadratic Program (MIQP). If the model has any constraints containing a quadratic term, regardless of the objective function, the problem is termed a Mixed Integer Quadratically Constrained Program (MIQCP).

In IBM ILOG CPLEX documentation, if the discussion pertains specifically to the MILP, MIQP, or MIQCP case, then that term is used. For the majority of topics that pertain equally to MILP, MIQP, and MIQCP, the comprehensive term MIP is used.

Integer variables may be restricted to the values 0 (zero) and 1 (one), in which case they are referred to as binary variables. Or they may take on any integer values, in which case they are referred to as general integer variables. A variable of any MIP that may take either the value 0 (zero) or a value between a lower and an upper bound is referred to as semi-continuous. A semi-continuous variable that is restricted to integer values is referred to as semi-integer. Using semi-continuous variables: a rates example says a bit more about semi-continuous variables later in this manual. Special Ordered Sets (SOS) are discussed in Using special ordered sets (SOS). Continuous variables in a MIP problem are those which are not restricted in any of these ways, and are thus permitted to take any solution value within their (possibly infinite) lower and upper bounds.

In CPLEX documentation, the comprehensive term integer variable means any of the various types just mentioned except for continuous or SOS. The presence or absence of a quadratic term in the objective function or among the constraints for a given variable has no bearing on its being classified as continuous or integer.

The following formulation illustrates a mixed integer programming problem, which is solved in the example program ilomipex1.cpp or mipex1.c , discussed later in this chapter: