<a rel="license" href="http://creativecommons.org/licenses/by/4.0/"></a><br /><span xmlns:dct="http://purl.org/dc/terms/" property="dct:title"><b>Solving the Lego Planning Problem with Pyomo and Glpk</b></span> by <a xmlns:cc="http://creativecommons.org/ns#" href="http://mate.unipv.it/gualandi" property="cc:attributionName" rel="cc:attributionURL">Stefano Gualandi</a> is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>. Based on a project at <a xmlns:dct="http://purl.org/dc/terms/" href="https://github.com/mathcoding/opt4ds" rel="dct:source">https://github.com/mathcoding/opt4ds</a>.

# 2. Solving the Lego Planning Problem

In this notebook, we explain how to solve **Linear Programming** problem that we have written to model the Lego Planning problem (see the slides on KIRO):

$$
\begin{align}
\max \quad & 8 c + 11 t  \\
\mbox{s.t. } \quad & 2c + 2t \leq 24 \\
& c + 2 t \leq 18\\
& c \geq 0\\
& t \geq 0
\end{align}
$$

We show below how to use Pyomo to define the **variables**, the **objective function**, and the **constraints**.

First, we need to install the [Pyomo](http://www.pyomo.org/) modeling language and the [GLPK](https://www.gnu.org/software/glpk/) open source solver, as explained in the following section.

## 2.1 Software Installation
If you are running this notebook in a Colab, you don't need to install anything else on your computer.

Otherwise, if you have installed the recommended Anaconda Python distribution, you have to run the following two commands:

1. To install the [Pyomo](http://www.pyomo.org/) optimization modeling language:

```
conda install -c conda-forge pyomo
```

2. To install the open source [GLPK](https://www.gnu.org/software/glpk/) solver:

```
conda install -c conda-forge glpk
```

3. (Optional) You can install some extra packages of Pyomo using the following command:

```
conda install -c conda-forge pyomo.extras
```

For details about the Pyomo installation, we refer to the official [Pyomo Documentation](https://pyomo.readthedocs.io/en/stable/).

The following lines are for running this notebook in a Google Colab:


```python
import shutil
import sys
import os.path

if not shutil.which("pyomo"):
    !pip install -q pyomo
    assert(shutil.which("pyomo"))

if not (shutil.which("glpk") or os.path.isfile("glpk")):
    if "google.colab" in sys.modules:
        !apt-get install -y -qq glpk-utils
    else:
        try:
            !conda install -c conda-forge glpk 
        except:
            pass
```

## 2.2 Define the model entities
To build the Linear Programming model with Pyomo, we need first to import the Pyomo library:


```python
from pyomo.environ import *
```

At this point, we first declare a global object that refer to our model:


```python
model = ConcreteModel()
```

Notice the `ConcreteModel` is a python class, and we are initializing an object called `model` of type `ConcreteModel`.

Then we star by declaring the two non/negative variables:


```python
# declare decision variables
model.c = Var(domain=NonNegativeReals)
model.t = Var(domain=NonNegativeReals)
```

Here, we add variable `c` and `t` to the model. The two variables are of type `Var`, and we are passing as input to the constructor the parameter `NonNegativeReals`. That is, we are declaring the two variables $c \geq 0, t \geq 0$.

Next, we declare the objective function.


```python
# Declare objective
model.cost = Objective(
    expr =  8*model.c + 11*model.t,
    sense = maximize)
```

In this case, we are adding the variable `cost`  to our model, that is an instance of an object of type `Objective`. The constructor is called with a linear expression `8*model.c + 11*model.t`, and we denote the sense of the objective function as `maximize`.

Next step is to introduce the two linear constraints:


```python
# Declare constraints
model.cnstr1 = Constraint(expr = 2*model.c + 2*model.t <= 24)
model.cnstr2 = Constraint(expr = 1*model.c + 2*model.t <= 18)
```

We have used here a third type of objects, namely the `Constraint` class, giving in input the two linear relation.

Notice that we are **declaring** the model, without programming any algorithm to actually solve this model. To find the optimal solution of this LP, we are going to use the Integer Linear Programming solver GLPK.

## 2.3 Solve the model
We have use the type of objects of the Pyomo library to *declare* our Linear Programming model. Next, we have to use a solver to find the optima value for the decision variables.

With Pyomo, we are not constrained to use a specific solver. In this notebook, for the sake of simplicity, we use the GLPK solver as follows, where we set the parameter `tee=True`, in order to see the logs produced by the solver.


```python
# Solve the LP model
sol = SolverFactory('glpk').solve(model, tee=True)
```

Every time we invoke a solver, it is very good practice to check the status of the solver, since it may have stop its execution for several different reasons:


```python
# Basic info about the solution process
for info in sol['Solver']:
    print(info)
```

Whenever the status of the solver is OK, we can query the solver to get the optimal value of the objective function and of the decision variables.


```python
# Report solution value
print("Optimal solution value: z =", model.cost())
print("Decision variables:")
print("\tProduction of chairs:", model.c())
print("\tProduction of tables:", model.t())
```

As we found manually during the *Active Learning* session, the optimal production plan is to build 6 chairs and 6 tables, to get a profit of 114 kroner.

It is also possible to check the file temporary file produced by Pyomo and passed as input to the Glpk solver, with the following command:


```python
model.write('lego1.lp')
```

## 2.4 Complete Script
We report below the complete script.


```python
# Main model object
model = ConcreteModel()

# Declare decision variables
model.c = Var(domain=NonNegativeReals)
model.t = Var(domain=NonNegativeReals)

# Declare objective
model.cost = Objective(
    expr =  8*model.c + 11*model.t,
    sense = maximize)

# Declare constraints
model.cnstr1 = Constraint(expr = 2*model.c + 2*model.t <= 24)
model.cnstr2 = Constraint(expr = 1*model.c + 2*model.t <= 18)

# Solve the LP model
sol = SolverFactory('glpk').solve(model, tee=True)

# Basic info about the solution process
for info in sol['Solver']:
    print(info)
    
# Report solution value
print("Optimal solution value: z =", model.cost())
print("Decision variables:")
print("\tProduction of chairs:", model.c())
print("\tProduction of tables:", model.t())
```

## 2.5 Exercise: three variables
As an exercise, you can try to modify the previous script to solve the second version of the Lego Planning problem:

$$
\begin{align}
\max \quad & 8 c + 11 t + 15 s \\
\mbox{s.t. } \quad & 2c + 2t +2s \leq 24 \\
& c + 2 t +3s \leq 18\\
& c \geq 0\\
& t \geq 0\\
& s \geq 0
\end{align}
$$

Basically, you have to add a third variable to the model, to modify the objective function, and the two constraints. Later, you call the solver again.


```python
# TO BE COMPLETED ...
```

04959d6ca849a6bab8c1385bca801b6ab5949aa4
ipynb
Jupyter Notebook
aa2021/notebooks/Lego Problems.ipynb
gianlucacovini/opt4ds
c8927ad36cace51c501527b2f8e8e93857c80d95
MIT
2020-03-04T18:02:47.000Z
2022-02-27T17:40:09.000Z
aa2021/notebooks/Lego Problems.ipynb
gianlucacovini/opt4ds
c8927ad36cace51c501527b2f8e8e93857c80d95
MIT
2021-03-23T11:47:24.000Z
2021-03-28T12:23:21.000Z
notebooks/Lego Problems.ipynb
mathcoding/opt4ds
42904fd56c18a83fd5ff6f068bbd20b055a40734
MIT
2020-03-12T23:41:21.000Z
2022-03-03T13:41:29.000Z
Qwen/Qwen-72B
1. YES
2. YES