13 Mixed Integer Programming

.title[Mixed Integer Programming and Waste Management] <br> .subtitle[BEE 4750/5750] <br> .subtitle[Environmental Systems Analysis, Fall 2022] <hr> .author[Vivek Srikrishnan] <br> .date[October 17, 2022]

---

# Outline

<hr>

1. Mixed Integer Programming for Operational Decisions
2. Waste Management: Netowrk \& Transport Modeling
3. Solving our Waste Management Example

---

# Poll

<hr>

URL: [https://pollev.com/vsrikrish](https://pollev.com/vsrikrish)

Text: **VSRIKRISH** to 22333, then message]

---

***Any questions?***

---

# Last Class

<hr>

* Economic Dispatch Examples

---

# Decision-Making About Operational Status

<hr>

Last class, we discussed economic dispatch, which assumed we had already decided which generating plants are online.

But what if we need to make that decision? Or what if we have a fleet of treatment facilities, some of which might be operated at a given time?

---

# Decision-Making About Operational Status

<hr>

Last class, we discussed economic dispatch, which assumed we had already decided which generating plants are online.

But what if we need to make that decision? Or what if we have a fleet of treatment facilities, some of which might be operated at a given time?

---

# Fixed Costs

<hr>

A key consideration when deciding whether to operate *something* is fixed costs.

Costs can be (roughly) broken down into two categories:

* **Fixed costs**: Labor, etc, required to operate or produce regardless of quantity.
  * **Variable costs**: Costs of inputs (energy, additional labor, materials) required to operate or produce per unit of time/quantity.

---

# Fixed Costs

<hr>

The existence of fixed costs creates a discontinuous cost function.

---

# Discontinuous Objectives: No More LP

<hr>

A discontinuous cost function is one way to violate the principles of linear programming!

This might mean a discontinuous objective, *particularly* if higher average costs mean that it is less cost-effective to operate minimally than to not operate and find another option.

---

# Indicator Variables and Constraints

<hr>

The potential decision to not operate means that we need to introduce new *indicator* variables, which flag on/off status.

These variables are binary, and hence not continuous!

For an example, let's consider **waste allocation** problems.

---

# Waste Load Allocation

<hr>

Some relevant questions:

* Where do we send waste?
  * What types of facilities do we build/operate?

] .right-column[.center[ ![Waste Management Hierarchy](https://www.epa.gov/sites/default/files/styles/medium/public/2015-08/hierarchy_hierarchy_and_options_pages.png)

.cite[Source: [EPA](https://www.epa.gov/homeland-security-waste/waste-management-options-homeland-security-incidents)] ]]

---

# Waste Load Allocation

<hr>

Notice that this type of allocation problem is not specific to garbage: those key questions are applicable to all supply chain problems.

---

# Waste Load Allocation as a Network Problem

<hr>

Think in terms of flows between sources and sinks!

---

# Parameterizing the Network Representation

<hr>

|       Variable       | Definition                                                 |
|:--------------------:|:---------------------------------------------------------- |
| $\color{purple}S_i$  | Waste produced at source $i$ (Mg/day)                      |
|   $\color{red}K_j$   | Capacity of disposal $j$ (Mg/day)                          |
| $\color{blue}W_{ij}$ | Waste transported from source $i$ to disposal $j$ (Mg/day) |

]

---

# Further System-Specific Information Needs

<hr>

This network representation takes into account the graph structure of the system, but nothing else.

To complete a model, need:

* System dynamics (fate, transport)
  * Objectives
  * Costs
  * Management goals and/or regulatory constraints

---

# Waste Management Information

<hr>

Mass-Balance constraints:

* Need to dispose of all waste from each source $i$:

$$
\sum\_{j \in J} W\_{ij} = S_i
$$

* Capacity limit at each disposal site $j$:

$$
\sum\_{i \in I} W\_{ij} \leq K_j
$$

---

# Objective: Minimize Total Costs

<hr>

What are the components of the total system cost?

---

***What are the components of total waste management system cost?***

---

# Objective: Minimize Total Costs

<hr>

* **Transportation** of waste between sources and disposals
  * **Disposal**: fixed costs (labor, maintanance energy), variable costs (fuel, etc)

---

# Objective: Transportation Costs

<hr>

| Variable | Definition                                                           |
|:--------:|:-------------------------------------------------------------------- |
| $a_{ij}$ | Cost of transporting waste from source $i$ to disposal $j$ ($/Mg-km) |
| $l_{ij}$ | Distance between source $i$ and disposal $j$ (km)                    |

$$
\text{Transportation Costs} = \sum\_{i \in I, j \in J} a\_{ij}l\_{ij}W\_{ij}
$$

---

# Objective: Disposal Costs

<hr>

| Variable | Definition                                              |
|:--------:|:------------------------------------------------------- |
|  $c_j$   | Fixed costs of operating disposal $j$ ($/day)           |
| $b_{j}$  | Variable cost of disposing waste at disposal $j$ ($/Mg) |

$$
\text{Disposal Costs} = \sum\_{j \in J} \left[c\_j + b\_j \sum\_{i \in I} W\_{ij}\right]
$$

Is that expression for disposal costs right? What is the underlying assumption?

---

# Objective: Disposal Costs

<hr>

The equation from the previous slide is only right if all disposal facilities are operating.

But the fixed costs of a disposal may make it not cost-effective to operate within the system constraints.

---

# Objective: Disposal Costs

<hr>

The option to not operate a disposal facility $j$ means that we need to introduce a new set of variables:

$$
Y\_j = \begin{cases}0 & \text{if } \sum\_{i \in I} W\_{ij} = 0 \\\\ 1 & \text{if } \sum\_{i \in I} W\_{ij} > 0 \end{cases}
$$

Since $Y_j$ is not a continuous variable, our decision problem is no longer a linear program.

Instead, the inclusion of some integer-constrained variables (which includes binary variables) makes this a ***mixed integer* linear program**.

---

# Waste Management Problem Formulation

<hr>

$$
\begin{alignat}{2}
& \min\_{W\_{i,j}, {Y\_j}} && \sum\_i \sum\_j a\_{ij}l\_{ij}W\_{ij} + \sum\_j \left[c\_jY\_j + \sum\_i b\_jW\_{ij}\right] \notag \\\\
& \text{subject to:} \qquad && Y\_j = \begin{cases}0 & \text{if } \sum\_{i \in I} W\_{ij} = 0 \\\\ 1 & \text{if } \sum\_{i \in I} W\_{ij} > 0 \end{cases} \tag{commitment} \\\\
& && \sum\_i W\_{ij} \leq K\_j \tag{capacity limit} \\\\
& && \sum\_j W\_{ij} = S\_i \tag{mass balance} \\\\
& &&  W_{ij} \geq 0 \tag{nonnegativity}\\\\
\end{alignat}
$$

---

# How Do We Solve a Mixed-Integer Program?

<hr>

What are the implications of the integer-constrained variable $Y_j$ for the solution?

---

# Recall: Linear Programming

<hr>

.left-column[ Since objective function and constraints are all linear and variables are continuous, we know optimal solutions occur at corners of the feasible polytope. ]

---

# Now: Mixed-Integer Linear Program

<hr>

---

# A Simple Mixed-Integer Problem

<hr>

.left-column[ $\begin{alignedat}{2} & \max && 3x_1 + 4x_2 \\\\
& \text{subject to:} && \\\\
& && 2x_1 + 6x_2 \leq 27 \\\\
& && x_2 \geq 2 \\\\
& && 3x_1 + x_2 \leq 19 \\\\
& && x_1, x_2 \geq 0 \\\
& && x_1, x_2 \quad \text{integers} \end{alignedat}$ ]

---

# A Simple Mixed-Integer Problem

<hr>

Integer solution: $f(4, 3) = 24$ ]

---

# Idea of Mixed-Integer Solution Method

<hr>

.left-column[ Solution to linear relaxation (relax integer constraint) is an *upper bound* on the mixed-integer solution (why?).

Starting from this, test new problems "bounding" LP solution with integer constraints.

Continue until integer solution found. ]

---

# Idea of Mixed-Integer Solution Method

<hr>

.left-column[ Solution to linear relaxation (relax integer constraint) is an *upper bound* on the mixed-integer solution (why?).

Starting from this, test new problems "bounding" LP solution with integer constraints.

Continue until integer solution found. ]

---

# Back to Waste Management

<hr>

* Waste-to-Energy (WTE) combusts waste, resulting in residual ash.
  * Materials Recovery Facility (MRF) recycles waste.
  * Landfill (LF) can store all waste types.

]

---

# Back to Waste Management

```julia
using JuMP
using Cbc

waste = Model(Cbc.Optimizer)
I = 1:2 # number of cities
J = 1:3 # number of disposal sites
```

---

# Waste Management Example: Decision Variables

<hr>

| Variable  | Definition                                                            |
|:---------:|:--------------------------------------------------------------------- |
| $W\_{ij}$ | Waste transported from city $i$ to disposal $j$ (Mg/day)              |
| $R\_{kj}$ | Residual waste transported from disposal $k$ to disposal $j$ (Mg/day) |
|  $Y\_j$   | Operational status (on/off) of disposal $j$ (binary)                  |

```julia
@variable(waste, W[i in I, j in J] >= 0)
@variable(waste, R[k in J, j in J] >= 0)
@variable(waste, Y[j in J], Bin)
```

]

---

# Waste Management Example: WTE Costs

<hr>

Transportation: $1.50/Mg-km

Recycling Rate: 40%]

| Facility | Fixed Cost ($/yr) | Tipping Cost ($/Mg) | Recycling Cost ($/Mg recycled) |
|:--------:| -----------------:| -------------------:| ------------------------------:|
|   WTE    |           900,000 |                  60 |                              – |
|   MRF    |           400,000 |                   5 |                             35 |
|    LF    |           700,000 |                  40 |                              – |

]

**WTE Costs**:  $2466 Y\_1 + 60(W\_{11} + W\_{21} + R\_{21})$

---

# Waste Management Example: MRF Costs

<hr>

Transportation: $1.50/Mg-km

Recycling Rate: 40%]

**MRF Costs**:  $1096 Y\_2 + 5(W\_{12} + W\_{22} + 0.4(35)(W\_{12} + W\_{22})$ ]

---

# Waste Management Example: LF Costs

<hr>

Transportation: $1.50/Mg-km

Recycling Rate: 40%]

**LF Costs**:  $1918 Y\_2 + 40(W\_{13} + W\_{23} + R\_{13} + R\_{23})$ ]

---

# Waste Management Example: Transportation Costs

<hr>

Transportation: $1.50/Mg-km

Recycling Rate: 40%]

.right-column[ **Transportation Costs**: $\begin{aligned}  &1.5[15W\_{11} + 5W\_{12} + 30W\_{13} \\\\
& \quad 10W\_{21} + 15W\_{22} + 25W\_{23} \\\\
& \quad 18R\_{13} + 15R\_{21} + 32R\_{23}] \end{aligned}$ ]

---

# Waste Management Example: Objective

<hr>

$$
\begin{aligned}
\min\_{W, R, Y} \qquad & 82.5 W\_{11} + 26.5W\_{12} + 85W\_{13} + 75W\_{21} + \\\\
& \quad 41.5W\_{22} + 77.5W\_{23} + 67R\{13} + 82.5R\_{21} + \\\\
& \quad 88R\_{23} + 2466Y\_1 + 1096Y\_2 + 1918Y\_3
\end{aligned}
$$

```julia
@objective(waste, Min, sum([82.5 26.5 85; 75 41.5 77.5] .* W) +
    sum([0 0 67; 82.5 0 88; 0 0 0] .* R) + sum([2466; 1096; 1916] .* Y))
```

---

# Waste Management Example: Mass-Balance

<hr>

City 2: $W\_{21} + W\_{22} + W\_{23} = 170$

]

---

# Waste Management Example: Mass-Balance

<hr> .left-column[.center[![Waste Management Example Network](figures/waste-example-network.svg)]]

MRF: $W\_{12} + W\_{22} \leq 130$

LF: $W\_{13} + W\_{23} + R\_{23} + R\_{13} \leq 200$ ]

---

# Waste Management Example: Mass-Balance

<hr>

WTE Residual Ash: 20%

$$
R\_{13} = 0.2(W\_{11} + W\_{21} + R\_{21})
$$

$$
R\_{21} + R\_{23} = 0.6(W\_{12} + W\_{22})
$$

]

---

# Waste Management Example: Commitment and Non-Negativity

<hr>

$$
\begin{aligned}
Y\_1 &= \begin{cases}0 &\quad \text{if } W\_{11} + W\_{21} + R\_{21} = 0 \\\\ 1 & \quad \text{else} \end{cases} \\\\
Y\_2 &= \begin{cases}0 &\quad \text{if } W\_{21} + W\_{22} = 0 \\\\ 1 & \quad \text{else} \end{cases} \\\\
Y\_3 &= 1 \\\\
W\_{ij}, R\_{ij} &\geq 0
\end{aligned}
$$

---

# Waste Management Example: All Constraints

<hr>

```julia
city_out = [100; 170]
# mass-balance
@constraint(waste, city[i in I], sum(W[i,:]) == city_out[i])
@constraint(waste, wte, W[1,1] + W[2,1] + R[2,1] <= 150)
@constraint(waste, mrf, W[1,2] + W[2,2]  <= 130)
@constraint(waste, lf, W[1,3] + W[2,3] + R[2,3] + R[1,3] <= 200)
# residuals
@constraint(waste, resid1, R[1,3] == 0.2 .* (W[1,1] + W[2,1] + R[2,1]))
@constraint(waste, resid2, R[2,1] + R[2,3] == 0.6 .* (W[1,2] + W[2,2]))
@constraint(waste, resid3, sum(R[3,:]) == 0)
@constraint(waste, noresiddiag, sum(R[i, i] for i in I) == 0)
@constraint(waste, noresid, R[1,2] == 0)
```

---

# Waste Management Example: All Constraints

<hr>

```julia
# commitment
@constraint(waste, commit1, !Y[1] => {W[1,1] + W[2,1] + R[2,1] == 0})
@constraint(waste, commit2, !Y[2] => {W[1,2] + W[2,2] == 0})
@constraint(waste, commit3, Y[3] == 1)
```

---

# Waste Management Example: Optimize

<hr>

```julia
optimize!(waste)
```

---