Linear and Mixed Integer Problems for Non Practitioners

As a non practitioner, you may have heard jargons like Mixed Integer programming, Integer programming etc. when interacting with your modeling team. This post intends to describe what these terms mean, in a simplified way using an example.

For our example, we will use the scenario shown in the diagram below. There are two plants P1 and P2, serving three customers, C1, C2 and C3. The maximum capacity for these plants is U1 and U2. The demands at the three customer locations are D1,D2 and D3 respectively. The flow units for each possible flow (lane) and the Transportation cost per Unit for that lane are also indicated in the diagram. To keep this simple, we will not consider any other costs here.lpOur decision points here are:

  • How much will each plant produce?
  • How much will flow from each plant to Each Customer?

Linear Program

Now, we can formulate this simplified example as a Linear program. But I promised I will explain what is Linear program first. Right? So lets do that with a simple definition. A Linear program helps us determine a way to achieve the best outcome (Objective), given some requirements (Constraints). We capture a real world problem in the form of mathematical equations and then the solution to those equations provide us our best outcome.

In our example above, what can be the best outcome? We want to serve our customers in the most cost efficient way so the outcome that minimizes our cost to serve is the best outcome. We can rephrase this as-Our objective is to minimize the total transportation cost (since the only cost we are considering in this problem is the Trans cost). Now, in this example, what is our total cost to serve the three demand regions? For each lane, the Transportation cost if the flow Units multiplied by the Unit cost. So our Total cost (which is only the Transportation cost in this example) is:

TC= F1a+F2b+F3c+F4d+F5e+F6f.        …………………(1)

Our objective is to minimize this cost hence we use the term “Objective Function” for this equation.

Now let us focus on Customer C1. Its total demand requirement is D1. So the sum of all units that arrive at C1 should be greater than or equal to D1. Based on the parameters defined in the above diagram, we can write this as:

F1+F4>= D1………………..(2)

We can formulate similar equations for other customer locations as well:

F2+F5>=D2…………………(3)

F3+F6>=D3…………………(4)

Now, what are these equations/inequalities? These are limits that are being placed. You must fulfill the demand at Customer locations so you can’t ship less than the demand quantities. These Equations are the constraints in our Linear program. Similarly, we have to keep the plant capacities in mind. A plant can’t ship more than its capacity (since it can’t produce more than its capacity). So another set of equations will be:

F1+F2+F3<= U1……………..(5)

F3+F4+F5<=U2………………(6) But wait, we need to add some more constraints here. Can we ship negative quantities to our customers? Nope…but we need to tell this to the model. So our next set of constraints will be F1>=0, F2>=0,F3>=0,F4>=0,F5>=0,F6>=0……………(7)

Great! We just created our first simplified Linear Program. Once you formulate a problem in this form, the next stage is using an algorithm to solve it, but that is out of the scope of our discussion here.

Now that we know a little bit more about the program, we can reformulate the definition of Linear program in a more technical way. A Linear Program is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Why do we call the program a linear program? A simplified version of the answer is: All our functions (objective function as well as the constraints) are linear-which means they have two primary properties- Additivity and Proportionality.

Additivity simply is that the total contribution of all variables in the objective function and their requirements in constraints are the direct sum of individual contribution of each variable.

Proportionality means that the contribution of each decision variable in the objective function and its requirements in the constraints are directly proportional to the value of the variable.

Mixed Integer Programming

Now you have created your Linear problem and you are really excited about it. However, you were just summoned by your COO. He thinks that there is excess manufacturing capacity in our network and we need only one plant to fulfill customer demand. Your problem has changed and you now want the model to chose only one plant and then determine how much to ship from that plant.

This changes our Objective function (equation 1). We modify it to be:

TC= F1aP1+F2bP1+F3cP1+F4dP2+F5eP2+F6fP2.        …………………(1)

Where P1 and P2 can only  assume Binary values i.e 0 or 1. So as you can see in the equation above, if we close plant P1, P1 assumes value of zero and hence there will be no Trans cost element for P1.

You can then add some additional equations like, in this particular scenario, P1+P2 =1, which will ensure that only one of them will have a value of 1 i.e only one of them are open. There are certain other constraints that you need to add, like the Linking constraint*, but for our purposes, we can avoid the details of these constraints. Our purpose here was to show what changes from one problem type to another. Since your problem now has Binary constraints as well (i.e there are decision variables constrained to Integer values), the problem that you have on hand now is a Mixed Integer program.

Though this was a really high level overview, I hope this post will help non-practitioners get a basic understanding of what these different type of programs( problem formulations) are so that next time they are interacting with their modeling team, they can have a more fruitful discussion.

————————————————————————–

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s