The Unit Re-Balancing Problem

The unit re-balancing problem is about a number of defensive military units distributed over a geographic area. Each unit consists of a number of components (e.g., people, armor, or equipment). A value between 0 and 1 describes the current rating of each component. By a nonlinear function this value is converted into a nominal status assessment. This allows a comparison of different components of all units. The lowest of the statuses determines the efficiency of a unit, and the highest status its cost. An unbalanced unit has a gap between these two. When too many units are unbalanced, the entire system is costly and inefficient. To re-balance the units, people and material can be transferred. The goal is to have all units equally well equipped at the lowest possible cost. On a secondary level, the cost for the re-balancing should also be minimal. We present a mixed-integer nonlinear programming formulation for this problem, which describes the potential movement of components as a multi-commodity flow. Nonlinear constraints are needed to obtain the lowest and the highest status. Since we assume that these functions are piecewise linear, we reformulate them using inequalities and binary variables. This results in a mixed-integer linear program, and numerical standard solvers are able to compute proven optimal solutions for instances with up to 100 units. The dataset consists of the models and test instances that were presented at the (virtual) 6th IMA Conference on Mathematics in Defence and Security, March 30-31, 2021.