Understanding linear optimization better?

Question

I'm taking a linear optimization class, and I'm having a difficult time formulating an 'integer program' from a problem. My main problem is taking given information (often tables), how do I declare variables that correspond with the data and create constraints with the variables based on the data given.

When I look at the answers, I understand why it is, but that doesn't help me all that much.

A chemical company manufactures two products from four raw materials. The company can use three different batch processes in any combination to meet consumer demand. The table below shows, for each process, the required raw materials, the amount of output products and the manufacturing cost. The table also includes the consumer demand for each product. Formulate an integer program that can be used to find the processes to employ that minimizes cost to the company while meeting consumer demand. The available raw material quantities are $125$, $175$, $225$, and $150$, respectively. \begin{array}{c|c|c|c|c|} & \text{Process 1}& \text{Process 2}&\text{Process 3}&\text{Consumer Demand}\\\hline \text{Raw Material 1}&1&2&0&\\ \text{Raw Material 2}&2&2&1&\\ \text{Raw Material 3}&4&1&2&\\ \text{Raw Material 4}&0&3&4&\\\hline \text{Product 1}&3&2&1&217\\\hline \text{Product 2}&1&3&1&167\\\hline \text{Cost}&\$44&\$32&\$29&\\\hline \end{array}

Given the problem, can someone give me the thought process of how to solve it? What I'm thinking is:

We declare $X_n$ to our process where $n$ is the material used. But then, how do we differentiate the material used in each process? Also, how can we link the variable with product (if we decide to use another variable to represent it) to make a constraint to meet the demands?

Answer 1

I ended up solving the example problem and the key takeaway I noticed that helps is that we use one variable for all the items, like x. this was tricky because I often use different variables to represent different items from my previous math classes.

Answer 2

For each positive integer $n$, denote the set of positive integers less than or equal to $n$ by $[n]$. Let

• $x_i = $ number of times using process $i$, $i\in[3]$
• $C_i = $ cost of using process $i$, $i\in[3]$
• $Q_j$ = available quantity of raw material $j$, $j\in[4]$
• $R_{ij} = $ amount of raw material $j$ used by process $i$, $(i,j)\in[3]\times[4]$
• $D_k = $ consumer demand for product $k$, $k\in[2]$
• $P_{ik} = $ amount of product $k$ produced by process $i$, $(i,k)\in[3]\times[2]$.

Then we can model this problem by the integer program \begin{align} \min&\quad \sum_{i\in[3]} C_ix_i\\ \mathrm{s.t.}&\quad \sum_{i\in[3]} P_{ik}x_i\geqslant D_k,\quad k\in[2]\\ &\quad \sum_{i\in[3]} R_{ij}x_i\leqslant Q_j,\quad j\in[4]\\ &\quad x_i\in\mathbb Z,\quad i\in[3]\\ &\quad x_i\geqslant 0,\quad i\in[3]. \end{align}

For the given numbers, this comes out to \begin{align} \min&\quad 44x_1 + 32x_2 + 29x_3\\ \mathrm{s.t.}&\quad 3x_1 + 2x_2 + x_3 \geqslant 217\\ &\quad x_1+3x_2+x_3\geqslant 167\\ &\quad x_1+2x_2\leqslant 125\\ &\quad 2x_1+2x_2+x_3\leqslant 175\\ \quad& 4x_1+x_2+2x_3\leqslant 225\\ \quad& 3x_2+4x_3\leqslant 150\\ \quad& x_1,x_2,x_3\in\mathbb Z\\ \quad& x_1,x_2,x_3\geqslant 0. \end{align}