Mixed integer Programming¶
Introduction¶
Mixed Integer Programming (MIP) can be regarded as an extension of Continuous Linear Programming where any of or all the defined decision variables cannot take fractional values. MIP introduces two new types of variables:
Integer variables: Integer variables can only take Integer values. Normally, Integer variables are introduced by logical restrictions that make rational valuables unfeasible. For instance, in some instances of production mix problems, it does not make sense to produce fractional parts of a product and treating them as real number is just an approximation.
Binary variables: Binary variables or Boolean variables can only take values 1 or 0. Normally, binary variables are used to factor into our model binary decisions, e.g. to decide whether to use a machine configuration or another, or whether to select one element from a set or not.
In CLP, the continuity of the decision variables ensures that the feasibility region and the objective function intersect in a vertex of the feasible region at the optimal value. But this is no longer the case when some decision variables are Integer values. Intuitively, one can think that the optimal value may be found in one of the feasible Integer values around the theoretical intersection, as long as the solution is feasible. This makes the number of candidate solutions larger and consequently, MIP problems are more difficult to solve. From a mathematical point of view, when the decision variables are not continuous, the feasible region and the objective function are no longer convex. Convexity of feasibility region and objective function ensures that the optimal solution is at one vertex. We will explain this concept further in Non-Linear Programming. For now, it is sufficient to understand that in MIP, the feasibility region is no longer convex since not all values are possible and this makes it harder to find a solution.
This limitation makes convergence to an optimal solution more complex. MIP solution is several orders of magnitude more complex that linear programming. For instance, the assumptions made to design the Simplex algorithm do no longer hold and although adaptations may find an optimal solution, convergence is so slow that they cannot be applied to practical problems.
Set up¶
In general, the set-up of MIP problems is the same as the set-up of CLP problems, except that some decision variables can only take Integer values. For instance:
decision variables¶
Let us note our decision variable as \(X = [x_1, x_2, ..., x_n]\) where \(n\) is the number of decision variables. In continuous linear programming, the decision variables could take any real value, in mathematical notation this is expressed as:
\(x_j \in \mathbb{R}\)
Now, in integer programming, decision variables can only take integer numbers. Without loss of generalization, let us consider that our decision variables can only take positive integers, or natural numbers. We refer to this type of decision variables as integer variables, and are noted as:
\(x_j \in \mathbb{N}\)
A special type of integer variables are binary variables which are variables that can only take values 0, or 1. These variables are very convenient to model ‘yes or no’ decisions or ‘true or false’ (boolean) logic decisions into our problem. We note can use this notation for binary variables:
\(x_j \in [0,1]\)
In general, not all decision variables have to be necessarily of the same type. Integer Programming (IP) problems only have integer or binary decision variables, whereas MIP problems can have any combination of decision variables.
Objective Function¶
As with CLP, our objective function is a linear function of the decision variables, noted as \(z\) and which we would like to maximize or minimize. For instance, if our objective function is of type maximize, we can use:
\(\max z = \sum_{j=1}^{n}{c_j·x_j}\)
Constraints¶
The objective function will be subject to some limitations or constraints:
\(s.t.\)
\(\sum_{j=1}^{n}{a_{1j}·x_j}\leq b_1\)
\(\sum_{j=1}^{n}{a_{2j}·x_j}\leq b_2\)
\(...\)
\(\sum_{j=1}^{n}{a_{mj}·x_j}\leq b_m\)
Let us now see some prominent examples of Integer Programming types. The next sections cover the formulation of some well known combinatorial optimization problems as IP problems.
Knapsack Problem¶
The Knapsack problem is an optimization problem that is often found in practical applications. The classical formulation reads
Given a set of items, each with a weight and a value, we need to determine the number of each item to include in a collection so that the total value is maximised while the total weight is less than or equal than the maximum weight the knapsack can hold.
Just like packing a knapsack for a nice adventure!
Decision variables¶
The decision variables \(x_j\) are binary decision variables that determine whether we include item \(j\) in the Knapsack:
\(x_j \in [0,1]\) {0: item not included, 1: item included} \(\forall j\)
That is, the decision variable can only take values 0, or 1. The value 0 means that the object is not selected and therefore has no impact in the objective function. Likewise, the value 1 means that the object is selected.
Objective coefficient¶
Each item \(j\) will have a different value \(v_j\). We can express the objective function as the value of the items selected:
\(\max z = \sum_{j=1}^{n}{v_j·x_j}\)
Constraints¶
Now, our only constraint is related to the maximum weight \(W\) the knapsack can support. Each item will have a different weight \(w_j\), and the sum of the weights \(w_j\) of the selected variables has to be less or equal than the maximum weight.
\(\sum_{j=1}^{n}{w_{j}·x_j}\leq W\)
Note that, if a given \(x_j\) is zero, the product \(w_{j}·x_j\) will also be zero and will have no impact on the total value of the left hand side summation.
Now, it is important to note that in this formulation, weights and values as abstract concepts, and the same formulation can be applied to many practical problems.
Assignment Problems¶
Assignment problems are a fundamental class of combinatorial optimization problems. In essence, assignment problems consists of assigning elements of a set of resources R (like workers, machines, etc.) to a set of tasks T to optimize a certain objective (like minimizing cost or maximizing efficiency), subject to various constraints.
Indices¶
Now, since we have two different sets, we will use two different indices to uniquely identify the elements in each set:
i: We will use index i to identify each element in set R. Let us note the size of set R as \(m\), therefore, \(i \in [1, 2, ..., m]\)
j: We will use index j to identify each element in set T. The size of set R is noted as \(n\), therefore, \(i \in [1, 2, ..., n]\)
Decision Variables¶
Let us define a binary variable \(x_{ij}\) for each resource i and task j. \(x_{ij} = 1\) if resource i is assigned to task j, and 0 otherwise:
\(x_{ij} \in [0,1]\) {0: resource i is not assigned to task j, 1: otherwise} \(\forall i, \forall j\)
Note that there are a total of \(m*n\) decision variables!
Objective function¶
The objective is to minimize costs or maximize benefits associated with assigning a particular resource to a particular task. As with Knapsack problems, we need to think of costs or benefits as abstract concepts, and the model can be applied to many practical applications.
For instance, let us note as \(c_{ij}\) the cost of assigning resource i to task j. The objective function then becomes:
\(\min z = \sum_{i=1}^{m}\sum_{j=1}^{n}{c_{ij}*x_{ij}}\)
Constraints¶
Now, the constraints need to ensure that one element of R is assigned to one element T, that is, we need to ensure that there are not two or more resources assigned to a task:
\(\sum_{j=1}^{n}{x_{ij}} = 1 \quad \forall i\)
Note first that the for a given \(i\), the left hand side \(\sum_{j=1}{n}{x_{ij}}\) is the sum of all the decision variables associated to a resource \(i\). Since the different \(x_{ij}\) can only be 0 or 1, by establishing an upper bound limit of 1 to the sum of all the elements, we ensure that the resource can only be assigned at most to one task.
Similarly, we need to ensure that a task is only associated to one resource:
\(\sum_{i=1}^{m}{x_{ij}} = 1 \quad \forall j\)
Note that the expression is similar, but now the left hand side \(\sum_{i=1}^{m}{x_{ij}}\) represents the sum of all the decision variables associated to task \(j\)
Sequencing Problems¶
Traveling Salesman Problem¶
Recall the classic formulation of the Travelling Salesman Problem (TSP):
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city
In practical applications, cities represent different steps in a process, and distances represent the cost of a sequence of steps in the process, from one step to another.
Thus, for the setup of the TSP as an IP, we have the following variables and coefficients:
\(x_{ij}\): Binary decision variables that represent a sequence from source i to destination j. 1 means that the step is selected in the final sequence, 0 otherwise.
\(c_{ij}\): Represents the cost the step in the sequence, in the classical formulation, the cost of travelling from city i to city j.
\(u_i\): Integer variable that represents the step of \(i\) in the sequence. If \(u_i\) is equal to \(t\) then city \(i\) is departed at step \(t\).
The IP formulation is then as follows:
\(\min z = \sum_{i=1}^{N}{\sum_{j=1}^{N}{c_{ij}*x_{ij}}}\)
\(s.t\) We can only depart from 1 city:
\(\sum_{j=1}^{N}{x_{ij}} = 1 \quad \forall i\)
We can only arrive to a city from a city:
\(\sum_{i=1}^{N}{x_{ij}} = 1 \quad \forall j\)
We cannot travel in loops in a city:
\(x_{ij} = 0 \quad \forall i=j\)
We travel from city i to city j exactly at step \(u_i\):
\(u_i - u_j + n*x_{ij} = n-1 \quad \forall i \in 2 \leq i \neq j \leq n\)
There are no loops, we do not allow \(u_i\) to be arbitrarily large:
\(0 \leq u_i \leq n- \quad \forall i \in 2 \leq i \leq n\)
Algorithms¶
There are different techniques used to solve MIP problems, among which we can highlight the following:
Relaxation¶
Relaxation is basically formulating the MIP problem as if all decision variables where continuous, and therefore reducing the MIP problem to a CLP problem. Relaxation allows the decision maker to use the Simplex method and perform a sensitivity analysis. The Solution may be not feasible, but it might provide some insights into the possible solution.
Cutting Planes (Gomory’s Algorithm)¶
The Gomory´s algorithm is an extension of relaxation. First, the problem is formulated as a CLP. When the solution is found, new constraints are introduced to cut the fractional part of one of the Integer variables out of the feasibility region. This yields a new CLP that can be solved with the Simplex method. This process is repeated until a solution is found where all Integer variables actually take Integer values.
Search (Branch and bound)¶
Branch and bound is one of the most common methods to solve combinatorial optimization and MIP problems. This type of algorithms explore the possible solutions iteratively, by dividing the set of possible solutions into smaller sets, then finding a bound of the objective function in each subset and selecting the subset, or branch with the optimal bound.
Let us see the set-up for a minimization problem. The objective function is:
\(\min z = f(x)\)
where x is the decision variable which can take values from a finite set \(C\), i.e. \(x \in C\).
Let us divide the set \(C\) into two subsets \(C_1, C_2\) and find a minimum bound of the objective function in each subset such that:
\(f(x) \leq c_1 \forall x \in C_1\)
\(f(x) \leq c_2 \forall x \in C_2\)
Now, let us assume that \(c_1 \leq c_2\). Since we are looking for the minimum value of \(z\), we can discard the entire set \(C_2\) from the search and continue looking for the solution in branch \(C_1\).
Now again, let us divide \(C_1\) into two subsets \(C_{11}, C_{12}\). We can find again a minimum bound for \(f(x)\) in each subset:
\(f(x) \leq c_{11} \forall x \in C_{11}\)
\(f(x) \leq c_{12} \forall x \in C_{12}\)
Again, we can compare bounds and select the branch with the minimum bound. Note that, at each iteration, we are selecting a better suboptimal solution. Let us note as \(\alpha\) the index of the subset of \(C\) at a given iteration. If \(C_\alpha\) contains only 1 element \(\alpha\) and \(c_\alpha = f(\alpha)\) is lower than the minimum bound of the other subsets, then \(\alpha\) is the optimal solution.
Genetic Algorithms¶
Genetic algorithms can also be used to solve MIP problems. You can find a description here