Linear programming and modeling

Linear programming is a technique to find the optimal solution in a mathematical model with a linear objective function and linear constraints. A linear programming model has the following form

$$\begin{aligned} \text{min} \quad & c^Tx && \\ \text{s.t} \quad & Ax & \leq & \quad b \\ & x & \geq & \quad 0 \\ \end{aligned}$$

Where $b$ and $c$ are constant column vectors, $A$ is a constant matrix, and $x$ is a column vector representing the variables.

There are many efficient LP solvers available today, such as Gurobi, SCIP, and COIN-OR. Therefore, if we can model a problem as an LP, it can be considered solved. However, modeling a problem is not always easy due to the following reasons.

• It is not straightforward to model all the conditions of a problem in a linear form.
• There are multiple ways to model a problem, but not all models are equally efficient. A model, even if it accurately represents the problem, can be too large or have loose constraints, leading to significant computational time.
• Sometimes, multiple models need to be constructed to solve a single problem. Building each model and ensuring effective interactions between them is also a challenge.

In my work, linear programming is used extensively, and I have often witnessed breakthroughs stemming from innovative modeling techniques. Therefore, I believe that modeling skills are crucial and not easily mastered.

Discover other modeling techniques by visiting MOSEK Modeling Cookbook. Happy learning!