Solving Your First Optimization Problem with LINGO

In this post, we will start diving into solving your first optimization problem. We will be using LINGO as our solver as it is easy to use for beginners, even when you are not coming from a computer sciences background.

“Practice makes perfect”

The way I’m always taught myself about learning software-based approach is to keep trying, face a problem, solve that problem, and repeat. Just like a designer, you learn to make art by doing a ton of designs.

You don’t need to have experience in LINGO as we will start from the very beginning, just make sure you installed it on your machine. I would recommend you to read Intro to Operation Research (OR) before you read this for better understanding. But it is not mandatory if you have a basic understanding of OR.

Okay cool, let’s start our journey.

Case Study

We need to introduce our simple yet real-life problem, called the assignment problem. An assignment problem is when we want to assign a person, machine, or any resource given several conditions. The common objective is to maximize the overall score, profit, or anything relatable. We will start with a problem description (always start with a text description to test your interpretation skills and convert it to a mathematical model.)

Okay here is our case study for this occasion. Try to read it, interpret it, and convert these text descriptions to math models for the next 10 minutes.

Hyuman Resources Consulting is a company that has 10 years of experience in human resources consultation. Now they have a client in which they need to assign high-tier talent to a few job posts. There are five employees that are available to perform four jobs. To perform such a job, each high-tier talent has their own time given in the table below. The client wants to find the optimal assignment that minimizes the total time required to perform the four jobs. (modified from Winston. 2003. Operation Research.)

*** additional notes ***

All value was in hours and dashes mean that the person can’t do the job.

Math Model

So first, let’s match our model (i hope you do before).

Let’s define the objective function first before the variable. What we want is to minimize the total time taken for all the jobs. So how do we math this logic?

We can do so by summing up if worker 1 is selected for job 1, then worker 2 is selected for job 2, and for worker 3, and so on. (let’s just say it for now, but it’s not the ground truth)

So by doing so, we can introduce what we call decision variables. Which is,

x[i,j] = 1 if worker i selected for job j, 0 otherwise.

So now, we have 20 variables right because this will create i*j matrix which is 5 (worker) * 4 (jobs) = 20.

So let’s group our decision variable with the constant of the time taken to get the job done. Now we have the complete version of our objective function,

Min z = 22x11 + 28x12 + 30x13 + 18x14 + 18x21 + 27x23 + 22x24 + … + 28x54

For the constraint, we want to add that there will be no overlap between workers. We take into account too for the jobs must be filled. The constraint will as follows:

1. All jobs are assigned to only one worker, (note that from the problem, we have 5 workers and 4 jobs meaning that one worker will not selected)
2. All the job is filled.
3. The worker who can’t do specific jobs. (one that have dashes from the table)

Let’s start with our first constraint with this

x11 + x12 + x13 + x14 ≤ 1 → Mean that for all jobs only assigned to 1 worker (see index i in x[i,j] is not changed) is and only 1.

x21 + x22 + x23 + x24 ≤ 1

x31 + x32 + x33 + x34 ≤ 1

x41 + x42 + x43 + x44 ≤ 1

x51 + x52 + x53 + x54 ≤ 1

The question is why less than and equal sign (≤)? Because we let the worker not get selected (The LHS can be zero). Remember that there will be one of the five workers who will not get assigned to any jobs because we only have 4 job posts.

For the second constraint, we want to ensure that all job is filled. We can do so by doing this,

x11 + x21 + x31 + x41 = 1 → Making all job posts is always filled by only one of the workers.

x12 + x22 + x32 + x42 = 1

x13 + x23 + x33 + x43 = 1

x14 + x24 + x34 + x44 = 1

x15 + x25 + x35 + x45 = 1

Then our third constraint,

x22 = 0 → From the dashes (table), meaning that worker 2 cannot get assigned to job 2.

x43 = 0

x52 = 0

Then the last touch, we want to bound our x to be binary.

x = [0.1]

LINGO TIME

First let’s open LINGO and we will got like the picture below,

For simplicity, in LINGO all the code will get executed and end with a semicolon (;). Then when writing the objective function we need to call MIN. And for the binary, we need to call @GIN. Okay, all sets.

Let’s write our objective function. We write it like this,

Min = 22x11 + 28x12 + 30x13 + 18x14 + 18x21 + 27x23 + 22x24 + 26x31 + 20x32 + 28x33 + 28x34 + 16x41 + 22x42 + 14x44 + 21x51 + 25x53 + 28x54;

To run the code, just press the red target with the arrow icon or simply click the solver menu → then solve. Now run the code and you will get an error. LINGO doesn't understand the 22x11. What LINGO can digest is like this, 22*x11. So you need to add an asterisk after the constant to represent the multiplication sign.

Our revised objective function will be like this,

MIN = 22*x11 + 28*x12 + 30*x13 + 18*x14 + 18*x21 + 0*x22 + 27*x23 + 22*x24 + 26*x31 + 20*x32 + 28*x33 + 28*x34 + 16*x41 + 22*x42 + 0*x43+ 14*x44 + 21*x51 + 0*x52 + 25*x53 + 28*x54;

For the constraint, (we will move fast as this point).

(Constraint for the worker will only got one jobs)

x11 + x12 + x13 + x14 <= 1;

x21 + x23 + x24 <= 1;

x31 + x32 + x33 + x34 <= 1;

x41 + x42 + x44 <= 1;

x51 + x53 + x54 <= 1;

(Constraint for all jobs must be filled by one worker)

x11 + x21 + x31 + x41 + x51 = 1;

x12 + x32 + x42 = 1;

x13 + x23 + x33 + x53 = 1;

x14 + x24 + x34 + x44 + x54 = 1;

(Add binary bound to the x)

@BIN(x11);

@BIN(x12);

@BIN(x13);

@BIN(x14);

@BIN(x21);

@BIN(x23);

@BIN(x24);

@BIN(x31);

@BIN(x32);

@BIN(x33);

@BIN(x34);

@BIN(x41);

@BIN(x42);

@BIN(x44);

@BIN(x51);

@BIN(x53);

@BIN(x54);

Our full complete model :

Then we solved the problem.

The Solution

We will get these windows when we run the model. Our objective value is 77 meaning that if we assign as in LINGO solution, we will get the optimal value of 77 hours. Close this window, and you will be redirected to a more detailed report. You will see these result, and this is the most important part is to interpret the result. Just focus on the one with a value of one.

So, our solution will go like this,

1. Assign worker 2 to job 1.
2. Assign worker 3 to job 2.
3. Assign worker 4 to job 4.
4. Assign worker 5 to job 3.
5. Do not assign worker 1 to any job.

Conclusion

So, Hyuman Resources Consulting will assign workers 2,3,4, and 5 respectively to their post, and leave worker 1. If you have something in mind, or maybe a correction, be sure to contact me (on profile). I will be happy to discuss it. Thanks for reading.