Large Scale Math Optimization
How It Works
Decision making is vital for all types of companies. Regarding business operations and/or industrial engineering the optimal decisions can be the cause that makes the difference between profitability and unworthiness or success and failure. Operations Research (OR) uses Mathematical methods to assist decision making in almost all types of industries. OR uses tools from a broad Math range striving to determine right resources mixtures, among large sets of possible combinations. These mixtures should produce maximums of gains or minimums of losses. An expected maximum of gain or minimum of loss can be expressed through a mathematical function called objective function. Usually, this function is subject to a set of physical constraints, which are also translated to mathematical ones. Otherwise, the problem is considered to be unconstrained. A large category of business operations or industrial engineering problems can be formulated through linear objective functions and linear constraints, which constitute the so called Linear Problems (LP). However, the corresponding nonlinear ones are not rare. Special interest due to their difficulty to solve, show the Integer linear Problems (ILP) or the Mixed Integer ones (MIP), which deal with integers or a mix of integers and real numbers. Binary variables taking (0, 1) values are most commonly used, since they clearly represent decisions, while sequences of integers of the form 0, 1, 2, 3, 4… can also appear as values to similar problem variables.
An OR algorithm tries to solve the above mentioned problems by searching all the possible combinations of resources and by evaluating the objective function with the purpose of finding the optimal solution. The set of all possible combinations is called search space and it may be very large to be handled by ordinary computing resources. Especially the ILP and MIP search spaces may rise exponentially in size, which is equivalent to an exponential number of processors requirement for the problem to be solved. In this case, two methods are usually followed, either the adoption of a heuristic algorithm or of a sub-optimal one. These methods try to find a near optimal solution, which can be achieved by a reasonable number of processors. Obviously, the application of Parallel Processing techniques can considerably speed up the near optimal solution processes.
From another point of view, the use of High Performance Computing makes other solution methods to be worth considering. Global optimization uses numerical analysis to identify global maximums or minimums of objective functions. Semidefinite programming (SDP) can minimize linear objective functions, subject to constraints that are not linear but convex. These are convex optimization problems. Also, Spectral Theory can be employed for resource optimization problems.
Tree processing is a very common procedure in optimization. Utilizing Parallel Processing, this can be performed applying different approaches. For example, many subtrees of the same tree can be processed simultaneously, or the nodes of the tree can be processed at the same time while the tree itself is processed sequentially. Combination of both is possible. Alternatively, parallelization at the node level of the trees can be applied.
An important problem that appears with tree processing parallelization is the load balancing. This refers to the distribution of work equally among the available processors. All the processors must be busy during the processing and no processor is permitted to be idle. However, the trees are generally unpredictable in their shape and size. Due to this, applying static load balancing has been proved not to be so effective. Dynamic load balancing, from the other hand, moves work from increasingly busy processors to processors that became idle due to un-predictiveness of the tree shape and size. However, moving tree data from processor to processor for balancing reasons can raise considerable computing costs. In this case, several factors should be taken into consideration before such a move.
