Discrete optimization, also known as integer optimization or combinatorial optimization, is a branch of optimization that deals with problems in which the variables are required to be discrete, or integer-valued, rather than continuous. Similar to linear optimization, the goal of discrete optimization is to find the best solution among a finite set of possible solutions, given certain constraints.
Understanding the Components of Mixed-Integer Linear Programming
Mixed-Integer Linear Programming (MILP) is an extension of Linear Programming (LP), a form of linear optimization that introduces the complexity of integer decision variables thus transitioning it into the realm of discrete optimization. In LP, decision variables can take on any real value within the defined constraints. However, in MILP, certain decision variables can only assume discrete integer values. This significant difference needs different solution methods due to the loss of the extreme point property, which is valid in LP but not in MILP.
Components of a Mixed-Integer Optimization Problem
- Objective Function:
The objective function in MILP is analogous to that in LP. It is a linear function that you aim to either maximize or minimize, depending on the nature of the problem. The objective function is expressed as a linear combination of the decision variables. However, the existence of integer variables can make the optimization process more complex in MILP.
- Decision Variables:
In LP, decision variables can be any real numbers, creating a continuum of possibilities. Since some variables in MILP must be discrete, this introduces the challenge of combinatorial optimization. The introduction of integer variables often represents real-world scenarios where certain quantities cannot be broken down into fractions, such as the number of machines in a factory or the number of people in a workforce.
- Constraints:
Constraints in MILP are linear inequalities or equalities that define the feasible region of the solution space. They limit the values that the decision variables can take. Like LP, constraints in MILP are linear and can include both equality and inequality relations. However, the feasible region in MILP cannot be a convex polyhedron due to the presence of integer decision variables, further complicating the search for optimal solutions.
Difference between Linear and Discrete Optimization
The major difference between linear and discrete optimization lies like the decision variables. This difference can make discrete optimization problems much more complex to solve than their linear counterparts. Even though a linear optimization problem can have an infinite number of solutions, efficient algorithms like the Simplex method can quickly find the optimal solution. Discrete optimization problems, on the other hand, often require a methodical search through all possible combinations of variables, which can be computationally intensive.
In the context of the PPO, a planning scenario is not continuous, that means, it is discrete, if the model includes the following:
- Discrete (integer) lot sizes for transport or PDS
- Discrete increase in production capacity
- Minimum lot sizes for transport or PDS
- Fixed PDS resource consumption
- Fixed PDS material consumption
Solution Methods for Discrete Optimization Problems
One of the primary methods used in discrete optimization is branch and bound. This method systematically partitions, or branches, the problem into smaller subproblems and uses bounds to eliminate, or prune, subproblems that do not contain the optimal solution. Branch and bound can be visualized as a decision tree, where each node represents a subproblem. Bounding is a crucial step in branch and bound, involving establishing upper and lower bounds for the objective function value of each subproblem. These bounds help prune branches that are unlikely to yield an optimal solution, reducing the search space. The overall goal of branch and bound is to find the best feasible solution by iteratively exploring the decision tree, branching on promising subproblems, and updating the bounds as new information becomes available. Another common technique in discrete optimization is dynamic programming, which breaks down a problem into smaller, overlapping subproblems and solves each subproblem only once, storing the results for future reference.
A branch and bound algorithm includes four important elements:
- Linear relaxation of the integer problem
The first element in a branch and bound algorithm is to create a linear relaxation of the original integer problem. This involves relaxing the integer constraints and solving the resulting linear programming problem. The solution obtained from this relaxation provides an upper bound on the optimal solution of the original problem.
Note
LP-relaxation is the term used when the requirement of integer linear optimization is abandoned in a problem of integer linear optimization. - Branching
After obtaining the linear relaxation, the algorithm proceeds to the branching step. This involves selecting a variable from the integer problem and creating two subproblems by branching on that variable. Each subproblem corresponds to a possible value of the selected variable. This branching process continues until all variables have been assigned values.
- Bounding
Once the branching is complete, the algorithm moves on to the bounding step. In this step, lower bounds are computed for each subproblem. These lower bounds are obtained by solving the linear relaxation of each subproblem. The lower bounds provide a way to prune subproblems that are guaranteed to have suboptimal solutions. This helps in reducing the search space and improving the efficiency of the algorithm.
- Optimality test
Finally, the algorithm performs an optimality test. This involves checking if the current best solution is optimal. If the optimality test fails, the algorithm backtracks to a previous node in the search tree and continues the search. This process continues until an optimal solution is found or all nodes in the search tree have been explored.
Simple Example of a Discrete Optimization Problem
Now, try to solve a discrete optimization problem using the branch and bound algorithm.
The feasible region of this discrete optimization problem is displayed in the following figure.
The figure illustrates the feasible region of the linear optimization problem depending on the two decision variables X and Y. The feasible region of the linear optimization problem is the blue area. The borders of this area are the two axes of the graph and the two lines representing the two constraints of the discrete optimization problem. The figure also shows the optimal solution of the linear optimization problem which is X=1.55 and Y=4.03. However, this solution cannot be the solution of the discrete optimization problem, because both of the variables are no integers.
Does rounding help? Rounding both variables to integers would yield X=2 and Y=4, but this solution is outside the feasible region and therefore cannot be a solution to the discrete optimization problem.
The figure illustrates the integer feasible solutions withing the feasible region of the linear optimization problem depending on the two decision variables X and Y. The feasible region of the linear optimization problem is the blue area. The borders of this area are the two axes of the graph and the two lines representing the two constraints of the discrete optimization problem. The integer feasible solutions (that is the solutions of the discrete optimization problem) are all combinations of X and Y being integer within the feasible region of the linear optimization problem.
To systematically solve the planning problem, you decide to branch at variable X. Since X cannot take the solution of the linear relaxation at X=1.55 in the optimal solution of the discrete problem, X either must be smaller or equal to 1 or larger or equal to 2. With these constraints added to either subproblem that you create two new subproblems that describe a new feasible region that excludes the optimal solution of the LP relaxation of the original problem.
Subproblem 1 (SP1) is the original problem with the additional constraint, that X must be smaller or equal to 1 and subproblem2 (SP2) is the original problem with the additional constraint, that X must be greater or equal to 2. For branch and bound, the calculation of upper and lower bounds are important.
First, subproblem 1 is solved. The figure visually represents the linear feasible region and the potential integer feasible solutions.
The (linear) feasible region and integer feasible solutions of the subproblem 1 are those that meet the constraints of the original problem and in addition the constraint that X must be smaller or equal to 1. The solution of the linear relaxation is X=1 and Y=3.75. The objective function value Z=15.67. The solution of the LP relaxation has produced an integer value for X, but none for Y. Therefore, the branching algorithm must continue. This time on variable Y with the additional constraints being:
- Y needs to be smaller or equal to 3.
- Y needs to be greater or equal to 4.
Likewise, the second subproblem 2 is solved. The next figure visually represents the linear feasible region and the potential integer feasible solutions.
The (linear) feasible region and integer feasible solutions of the subproblem 2 are those that meet the constraints of the original problem and in addition the constraint that X must be greater or equal to 2. The solution of the linear relaxation is X=2 and Y=3.75. The objective function value Z=17. The solution of the LP relaxation has produced an integer value for X, but none for Y. Therefore, the branching algorithm must continue. This time on variable Y with the additional constraints being:
- Y needs to be smaller or equal to 3.
- Y needs to be greater or equal to 4.
As the steps of the branch and bound algorithm are repeated, you gradually move closer to the optimal solution. To help make the right decisions for branching, upper, and lower bounds play an important role:
- Upper bounds
An upper bound refers to an estimate or limit on the maximum value that a particular objective function can attain. It represents an optimistic view of the best possible solution achievable within the problem's constraints. In other words, an upper bound sets an upper limit on the quality of the solutions that can be found.
- Lower bounds
On the other hand, a lower bound represents a pessimistic estimate or limit on the minimum value that the objective function can attain. It provides a lower limit on the quality of the solutions that can be found. A lower bound is typically obtained by using heuristics, relaxation techniques, or other methods to find a feasible solution that is guaranteed to be worse than the optimal solution.
Upper bounds help in assessing the quality of the solutions found during the optimization process. If a solution's objective function value exceeds the current upper bound, it can be discarded as it cannot be part of the optimal solution. Lower bounds, on the other hand, provide valuable information about the potential quality of the optimal solution. They can guide the search process by providing a benchmark against which the quality of the solutions found can be compared.
The first two subproblems for SP1 do not need further branching, because they are either integer feasible (SP7) or not feasible (SP8). The same is not true for the SP2. Whereas SP4 is infeasible, SP3 has a solution to the linear relaxation that is not integer feasible with X taking the value 3.2. Thus, based on SP3, two new subproblems be created by branching again on the decision variable X. The resultant subproblems are integer feasible (SP5) or can be pruned, although they are not integer feasible. The objective function value of the linear relaxation of SP6 is smaller than the integer feasible solution of SP5. Therefore, SP5 has produced the optimal solution of the original discrete optimization problem with X=3 and Y=3 and an objective function value of 15.