Mixed Integer Linear Programming (MILP) Solver

\begin{matrix} \underset{x \in ℝ^{n}}{minimize} & c^{T} x \\ subject to & l_{A} \leq Ax \leq u_{A}, \\ l_{x} \leq x \leq u_{x}, \end{matrix}

(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

c_{fix} x + c_{var} y,

Where we add constraints

\begin{matrix} 0 \leq y \leq Mx, \\ x \in {0, 1}, \end{matrix}

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.

\begin{matrix} t_{j} \geq t_{i} + p_{i}, \\ t_{i} \geq t_{j} + p_{j}, \end{matrix}

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

\begin{matrix} x_{1} + x_{2} \geq 1, \\ x_{1}, x_{2} \in {0, 1}, \\ t_{j} \geq t_{i} + p_{i} - M (1 - x_{1}), \\ t_{i} \geq t_{j} + p_{j} - M (1 - x_{2}), \end{matrix}

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$ $\in {- 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.

References

[1] Vielma JP. Mixed integer linear programming formulation techniques. Siam Review. 2015;57(1):3-57.

[2] Floudas CA, Lin X. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research. 2005 Oct;139:131-62.

[3] Conforti M, Cornuéjols G, Zambelli G, Conforti M, Cornuéjols G, Zambelli G. Integer programming models. Springer International Publishing; 2014.

Mixed Integer Linear Programming (MILP)

MILP Modelling and Solving

References

Default title

Please provide your work email to access the free trial