We start this section with an introductory example: the Knapsack Problem.
The goal is to put as many of \(n\) items as possible with value \(v_i\) and weight \(w_i\) in a bag of capacity \(W\). Imagine you are a shipping company and you need to decide what items you would like to put into a shipment container such that the overall profit is maximized.
\[ \begin{equation*} \begin{array}{ll@{}ll} \text{max} & \displaystyle\sum\limits_{i=1}^{n} v_{i}x_{i} & &\\ \text{subject to}& \displaystyle\sum\limits_{i=1}^{n} w_{i}x_{i} \leq W, & &\\ & x_{i} \in \{0,1\}, &i=1 ,\ldots, n& \end{array} \end{equation*} \]
As alluded to in the beginning, this integer program consists of 3 parts:
Having derived such a model that describes a relevant optimization problem, we need to solve it. The first step is to encode the problem in a way that an algorithm can understand it (the most basic form is a set of vectors and a constraint matrix). Having such a standard interface, many specialized solvers have been developed over the years (both commercial and open-source) to solve these kind of problems at a scale required for real world problems.
R has many packages that help you model and solve mixed-integer linear programs. The section about modelling packages shows how to model this problem in R.