Introduction
Mathematical programming (MP) is a very useful tool for solving complex problems that can be modeled as an objective function with a set of mathematical constraints. A wide variety of research disciplines currently use MP techniques to aid in complicated decision-making, from management science to engineering to the military. Since MP is concerned with finding optimal ways of using limited resources to achieve an objective, it is often simply referred to as optimization.
In MP, an optimization is a minimum or maximum of an objective function which takes the form
\begin{aligned}
\min \text{ (or } \max\text{) } f(x_1, x_2, \ldots, x_n) \end{aligned}where [latex]\{x_1, x_2, \ldots, x_n\}[/latex] is the set of decision variables that characterizes the problem. These variables may represent anything from the number of certain types of products that need to be produced by a factory to starting times for various jobs in a schedule. The objective is usually to minimize or maximize a linear function of these variables, subject to mathematical constraints of the form:
\begin{aligned}
f_1(x_1, x_2, \ldots, x_n) &\leq b_1 \\
\ldots \\ f_k(x_1, x_2, \ldots, x_n) &\geq b_k \\
\ldots \\ f_m(x_1, x_2, \ldots, x_n) &= b_m \\
\end{aligned}
where [latex]\{b_1, b_2, \ldots , b_m\}[/latex] is a set of constants and [latex]\{f_1, f_2, \ldots , f_m\}[/latex] is a set of functions with parameters [latex]\{x_1, x_2, \ldots, x_n\}[/latex] that collectively represent either an equality or inequality constraint. These functions may be linear or non-linear, and these two types of problems have different optimization techniques for solving them.
Linear Programming
Linear programming (LP) problems are MP formulations where the objective and each constraint are a linear function of [latex]\{x_1, x_2, \ldots, x_n\}[/latex]. Hence, an LP formulation would look like:
\begin{aligned}
\min \text{ (or } \max\text{): } &c_1x_1 + c_2x_2 + \ldots + c_nx_n\\
\text{subject to: } &a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1\\
&\ldots \\
&a_{k1}x_1 + a_{k2}x_2 + \ldots + a_{kn}x_n \geq b_k\\
&\ldots \\
&a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n = b_m\end{aligned}Example LP Problem
Suppose a company makes two products, [latex]P_1[/latex] and [latex]P_2[/latex], and has two factories that produce
these products. Factory 1 produces 4.5 kg of [latex]P_1[/latex] per day, and 4 kg of [latex]P_2[/latex] per day. Factory
2 produces 7 kg of [latex]P_1[/latex] per day but only 3 kg of [latex]P_2[/latex] per day. Product [latex]P_1[/latex] can be sold for
$2 per kg, and product [latex]P_2[/latex] can be sold for $3 per kg. Assuming that both factories operate at a
constant rate, this means that when operating at full capacity, the total processing time necessary for Factory 1 to produce [latex]X[/latex] units of [latex]P_1[/latex] and [latex]Y[/latex] units of [latex]P_2[/latex] would be [latex]\frac{2}{9}X + \frac{1}{4}Y[/latex]. Likewise, the total time needed to produce [latex]X[/latex] units of [latex]P_1[/latex] and [latex]Y[/latex] units of [latex]P_2[/latex] for Factory 2 would be [latex]\frac{1}{7}X + \frac{1}{3}Y[/latex]. Since it is not possible for the factories to produce negative quantities of each product, we specify that [latex]X\geq 0[/latex] and [latex]Y \geq 0[/latex]. We want to show that the daily processing requirements do not exceed production capacity at each factory, which gives us the following formulation:
\begin{aligned}
\min \quad&(-2X-3Y)\\
\text{s.t.: }\quad&\frac{2}{9}X + \frac{1}{4}Y \leq 1\\
&\frac{1}{7}X + \frac{1}{3}Y \leq 1\\
&X,Y\geq 0\\
\end{aligned}
The linear constraints and optimal objective function value are shown in this image. The shaded region represents the feasible region, or the set of points which, when chosen, satisfy all of the constraints specified in the problem. As seen in the graph, the feasible region is a polygon whose edges correspond to the linear constraints. The objective function line is moved outward (increasing its [latex]x[/latex]- and [latex]y[/latex]-intercept values) until it is tangent to the feasible region at one of its corner points. This point represents the optimal value for [latex]X[/latex] and [latex]Y[/latex], the point at which the value of the objective function is maximized.
Certain LP formulations may have multiple or infinitely many optimal solutions, such as when the objective function is parallel to one of the linear constraints. An LP problem may also have an unbounded optimal solution, or it may be considered infeasible when the constraints do not allow for any solution that satisfies all of them.
Simplex Method
The Simplex Method is a widely used computational tool for solving LP problems. It is a fairly simple algorithm, and it has been proven to find optimal solutions (if there are any) to all instances of LP problems. In addition, as a byproduct it provides useful data, such as how an optimal solution varies with respect to the problem data and reports when a solution is unbounded or infeasible. The Simplex Method works because a single optimal solution to any LP problem always has to occur on a corner point of the feasible region. Therefore, only these points need to be considered in the search for an optimal solution.
The Simplex Method works by first converting all constraints that are inequalities into equalities. It does this by defining an extra positive-valued slack variable for each of these constraints, subtracting it from each [latex]\geq[/latex] constraint and adding it to each [latex]\leq[/latex] constraint. Using the previous example, the resulting LP formulation with slack variables [latex]S_1[/latex] and [latex]S_2[/latex] would look like this:
\begin{aligned}
\min \quad&(-2X-3Y)\\
\text{s.t.: } \quad&\frac{2}{9}X + \frac{1}{4}Y + S_1 = 1\\
&\frac{1}{7}X + \frac{1}{3}Y + S_2 = 1\\
&X,Y,S_1,S_2\geq 0\\
\end{aligned}The constraints are now a series of 2 equations with 4 variables. The Simplex Method then proceeds to set any 2 of these variables to 0 (or their lower bound), and solves for the other 2 variables. This solution is guaranteed to be on one of the corner points of the feasible region, and is called a basic feasible solution.
Rather than enumerating all basic feasible solutions and choosing the best one, the Simplex Method begins instead at a random corner point, and moves to an adjacent corner point. It does this only if the solution there is better than the previous one until it can find no better solution. By using this “greedy” approach, it is possible to find the optimal solution using fewer iterations than would otherwise be needed.
Mixed-Integer Linear Programming
Many MP problems exist where it is necessary to restrict the decision variables to integer or binary values. Examples include cases where the decision variable represents a non-fractional entity such as people or bicycles, or where a decision variable is needed to model a logical statement (such as whether or not to assign task A to agent B). These problems are called Mixed-Integer Linear Programming (MILP) problems, and are often much harder to solve than LP problems. This is because instead of having feasible solution points at the easily computed corners of the feasible region, they are usually internal and more difficult to locate. For example, constraining [latex]X[/latex] and [latex]Y[/latex] from the previous LP formulation to have integer values, the feasible solution points are shown in this image below:
The first step in solving a MILP problem such as this is to solve the linear relaxation of that problem. This simply means removing the constraints that any decision variables have integer values and solving the resulting LP problem using an algorithm such as the Simplex Method. The result is one of the following outcomes:
- The LP problem is infeasible, so the MILP problem is also infeasible.
- The LP is unbounded and is probably not a well-posed problem.
- The LP has a feasible solution and all integrality constraints are satisfied, so the MILP has also been solved.
- The LP has a feasible solution, but not all of the decision variables have integer values.
No further work is necessary for outcomes 1, 2 and 3, but more work is required to find the optimal solution for case 4. In most cases the Branch and Bound technique is used in this case to find the integer solution, as explained in the next section.
Branch and Bound
The idea behind Branch and Bound is to divide the feasible region into sub-problems according to integer values and to use LP techniques recursively to tighten upper and lower bounds around the optimal solution until they meet or until an LP relaxation results in an integer solution.
After the initial LP relaxation of the problem has been solved, the resulting decision variable values are analyzed. A non-integer-valued variable is chosen, and then two sub-problem branches are created which are the same as the previous LP problem, except that the variable chosen is constrained to be greater than or equal to its upper integer bound (rounding the decimal solution up) in one case, and less than or equal to its lower integer bound (rounding the decimal solution down) in the other case.
Each of these sub-problems is recursively solved and branched again using LP techniques and choosing a different variable, until we have one of the 3 cases:
- The LP problem of the branch is infeasible,
- The solution to the LP problem is integer-valued, or
- The solution to the LP problem is worse than a previously computed solution.
In a maximization problem, the optimal objective function value of the LP relaxation is always an upper bound on the optimal integer solution. Likewise, any integer feasible point found is always a lower bound on the optimal integer solution. These values are used to update the upper and lower bounds at every step, narrowing down the possible solutions until the optimal integer solution is found.
Branch and Bound works better for LP problems than completely enumerating every possible integer solution, but its running time may still grow exponentially with respect to the problem size in some cases. The total running time of Branch and Bound depends mostly on how well the LP relaxation approximates the convex hull of the feasible integer
set. The convex hull of a feasible set of points [latex]S[/latex] of a LP is defined as the smallest polyhedron that contains [latex]S[/latex]. Formally, the convex hull for [latex]S[/latex] is defined as:
C = \left\{\sum_{i=1}^k \lambda_ix^i \quad\middle|\quad x^i \in S, \lambda_i\geq 0, \sum_i \lambda_i = 1 \right\}The closer the LP relaxation is to this bound, the less time it takes for Branch and Bound to find the optimal integer solution.
Combinatorial Optimization
Combinatorial optimization is an emerging field at the forefront of combinatorics and theoretical computer science, which aims to use combinatorial techniques to solve discrete optimization problems, such as the best way to route data through a network. A discrete optimization problem tries to find the best potential answer from a finite range of possibilities.
Combinatorial optimization aims to enhance an algorithm by utilizing mathematical methods, either to reduce the size of the set of feasible solutions or to speed up the search itself. From a combinatorics point of view, it interprets difficult problems in terms of a defined set of objects for which much is already known such as graphs and collections.
The term ‘combinatorial optimization’ generally refers to approaches used to solve these problems and, for the most part, does not include instructions about how to transform real-world issues into abstract mathematical questions, or vice versa.
This topic arose from graph theory problems such as edge colorings in undirected graphs and matchings in bipartite graphs. Most of the initial development is largely attributed to theorems in graph theory and their duals. With the introduction of LP, such approaches have been adapted to issues such as assignment, maximal flow and transportation.
Conclusion
Mathematical programming (MP), and especially linear programming (LP), is one of the most well-developed and utilized branches of management science. It concerns the optimal allocation of resources among competing actions, under a set of constraints imposed by the nature of the problem being studied. These constraints could reflect financial, technological, marketing, organizational, or many other considerations. In broad terms, MP can be defined as a mathematical representation aimed at planning the best possible allocation of scarce resources. When the mathematical representation uses linear functions exclusively, we have an LP model. When the mathematical representation is restricted to integers, we have an integer linear programming model (ILP). If some decision variables are not discrete, then we have a mixed-integer linear programming (MILP) model. The process of using MP to solve problems in combinatorics is called ‘combinatorial optimization’.