At Mark 29.3, NAG introduces a cutting-edge solver (nag_mip_handle_solve_milp) designed specifically for addressing large-scale mixed-integer linear programming (MILP) problems. This marks a significant stride in NAG’s commitment to enhancing and broadening its offerings in the field of mathematical optimization.

MILP finds widespread application across diverse industries, including but not limited to finance, manufacturing, logistics, transportation, and telecommunications. By accommodating both continuous and discrete decision variables, the solver empowers organizations to model practical and challenging problems, including resource allocation, scheduling, and network flow.

Large-scale MILP problems of the form 

minimizex ∈ ℝncTx subject to lA ≤ Ax ≤ uA, lx ≤ x ≤ ux, 		(1)

\( x \) ∈ \(P \),

where \( A \in \mathbb{R}^{m\times n} \), \(l_{A}, u_{A} \) ∈ ℝ\(^m\), \( c \), \( l_{x} \), \(u_{x}\) ∈ ℝ\(^n\)  are the problem data, and \( P = \) ℤ\(^{n_{int}}\) ×  ℝ \(^{n_{l}}\) are quite ubiquitous in real-life applications. It’s important to highlight that solving MILP problems poses a considerable challenge owing to their combinatorial nature, and in many practical scenarios, finding an exact solution within reasonable time may be very difficult. We are happy to present the latest addition to the NAG Library and aim to help users to make decisions efficiently and accurately.

MILP Modelling and Solving

Model (1) covers many practical use cases. One of the distinctive features of MILP is its capability to model logical conditions such as implications or dichotomies.

Take fixed charge modelling as an example. Economic activities frequently involve both fixed and variable costs. In these cases, a fixed cost \(c_{fix} \) only occurs when variable \( y \) is positive. Given a variable cost \(c_{var}\), the total cost when \( y \) >0 is \(c_{fix} \) + \(c_{var}y\) and 0 otherwise. It’s easy to observe that the cost function is nonlinear. By introducing binary variable \(x\) we can model it as the linear expression

 

cfixx + cvary,

Where we add constraints

0 ≤ y ≤ Mx, x ∈{0,1},

Where \(M \) is an upper bound of \(y\) and should be chosen as the tightest known bound, instead of an arbitrarily large \(M \). This modelling technique appears in applications such as facility location and network design.

Another great usage of MILP is to model disjunctions. For example, when scheduling jobs on a machine, we might want to allow job \(i\) to be scheduled before job \(j\) or vice versa. Let \(p_{i} \) and \(p_{j} \) denote the processing time of job \(i\) and \(j\), while \(t_{i}\) and \(t_{j}\) represent their starting times. Then we will require at least one of the following constraints is satisfied.

 

tj ≥ ti + pi, ti ≥ tj + pj,

By introducing binary variables \(x_{1} \) and \(x_{2} \), the problem can be modelled as

x1 + x2 ≥ 1, x1, x2 ∈{0,1}, tj ≥ ti + pi − M(1 − x1), ti ≥ tj + pj − M(1 − x2),

where \( M \) again is positive and serves as a known bound.

There are many other types of constraints that are very useful in the field of operations research, including but not limited to

  • Semi-continuous variables where a variable \(x\) is either 0 or in an interval [\( a, b\)],
  • variables only taking values from a set, e.g., \(x\)
    ∈{−2,−1,1,2}    ,
  • continuous piece-wise linear functions, which can be seen as a combination of linear functions.

See [1, 2] for more formulation techniques and its usage in scheduling.

Figure 1: Illustration of a branch-and-bound tree

 

In order to solve (1) efficiently, the branch-and-bound algorithm serves as a fundamental framework, which is equipped with modern MILP techniques such as preprocessing, cut generation and various heuristics. A portion of a branch-and-bound tree is depicted in Figure 1. Starting from the original problem, noted as root node, the algorithm generates various child nodes by shaping the feasible region via adding more constraints, such as Gomory fractional cut. Each node is solved as a continuous linear programming by an efficient dual simplex method. Various heuristics are adopted to get a better lower bound. By successfully pruning the search tree and selecting the search nodes, it greatly increases the chance for a branch-and-bound algorithm to find the optimal solution in a reasonable time. See [3] for more details on algorithms to solve MILP.

The MILP solver nag_mip_handle_solve_milp is fully integrated into the NAG Optimization Modelling Suite, which allows users to better express the real-world problems into the mathematical model, enhancing the understanding of the inner working of the model. During the modelling process, the users can

  • see the effect of a particular constraint or variable by temporarily removing them and then bringing them back;
  • modify individual coefficients of the linear objective or the linear constraints;
  • fix a variable to a given constant which results in the elimination of the variable across the formulation and decreasing the problem dimension.

The solver is available for multiple languages and environments including C and C++, Python, Java, .NET and Fortran, on Windows, Linux and MacOS. See the Getting Started page for how to download and install.