The objectives for any research is that we want to build a mathematical model to formulate the given problem. The heart of operations research is a mathematical model. That model is going to precisely describe the problem, but the model may be too complicated to get an optimal solution.

We need heuristic algorithms, and the model could be the foundation. With heuristic algorithms, we don’t want to find optimal solutions. Instead, near-optimal solutions are fine. We want to spend short time to get feasible solutions efficiently.



We always try to solve a problem by creating three levels of models:

Conceptual modelSelect useful information.
Describe problems in words that a non-technical people can understand.
Usually not precise enough to write computer programs.
Mathematical modelConsist of decision variables, constraints and objective function.
Specification for writing programs.
The most difficult and important part.- heart of Operations Research.
Computer modelHard to build if without specification from mathematical model.
Programs in C++, python, Excel, etc to generate solutions.

Conceptual models

In operations research, before we build a mathematical model, we first build conceptual models to help us do the preparation, and it will help us do the communication between business persons.

An example of conceptual model describing the problem. These are all real concerns. When we write down one-by-one, it would not be so hard to generate a mathematical model from these descriptions.

What decision to make?
  1. Whether to build a facility in a city.
  2. Its scale: large, middle or small.
  3. Its number of employees offering services.
  4. To which customers the services are offered.
What is the objective?
  Minimize the cost
  1. Office rent
  2. Traveling expenditure
  3. Utility costs
What are the constraints?
  1. At most 1 facility in 1 candidate location
  2. Only 1 scale level is selected for a facility
  3. Each of employees and each of customers are assigned to 1 facility only.
  4. For each facility, its employees shall be enough to serve its costumers.
  5. Number of employees is limited by scale of the facility.  

Mathematical models

Almost always we start by defining sets, indexes, and the variables. For example: set of customers I, set of facilities J, and set of scale levels K. Use the corresponding small letter i, j, k to represent each element in the corresponding set.

Define decision variables

xjk= 1 if a facility is built at location j with scale level k
= 0 otherwise
yij= 1 if a customer i is assigned to be served at facility j
= 0 otherwise
wjEmployee number assigned to facility j

Define parameters

fjkAnnual office rent of location j with scale k
hiAnnual number of services needed by customer i
dijCost per service between facility j and customer i
cjCost for hosting one employee in facility j
mjkMax number of employees hosted in facility j with scale level k
sNumber of services that an employee can complete in a year
aij= 1 if customer i and facility j is close enough
=0 otherwise

Define objective function

The goal of this problem is to minimize the total cost:

min office rent + traveling cost + utility cost
= min โˆ‘jโˆˆJ โˆ‘kโˆˆK fjk xjk + โˆ‘iโˆˆI โˆ‘jโˆˆJ hj dij yij + โˆ‘jโˆˆJ cj wj


Define constraints

โˆ‘kโˆˆK xjk โ‰ค 1, โˆ€ j โˆˆ JFor any facility j, we choose 1 scale level k
yij โ‰ค โˆ‘kโˆˆK xjk, โˆ€ i โˆˆ I, j โˆˆ JOnly a built facility can serve customers
โˆ‘jโˆˆJ aij yij = 1, โˆ€ i โˆˆ IFor each customer, it must be served by a facility close enough
wj โ‰ค โˆ‘kโˆˆK mjk xjk, โˆ€ j โˆˆ JNumber of employee in a facility can not exceeds its capacity
โˆ‘iโˆˆI hi yij โ‰ค s wj, โˆ€ j โˆˆ JEmployees of a facility should be able to complete all service requests
xjk โˆˆ {0, 1} โˆ€ j โˆˆ J, k โˆˆ K
yij โˆˆ {0, 1} โˆ€ i โˆˆ I, j โˆˆ J
Decision variables must be binary

Computer models

Once you have a mathematical model, then you may give that for someone to build a computer model. Python with Gurobi optimizer is a good example. Microsoft Excel solver is typically not enough for large-scale real problems.

Heuristic algorithms

When your problem is having large number of facilities, customers or more decisions, you need heuristic algorithms to find a near-optimal solution in a reasonable short time. An example of heuristic algorithm is naรฏve greedy algorithm.

  1. Open all the facilities with largest scale level.
  2. In each iteration, we greedily try to improve the current solution by downsizing exactly one facility by one scale level.
  3. If there are multiple choices of reducing the total costs, we choose the one that brings in the largest reduction.
  4. We keep iterating until no further feasible downsizing may reduce the total cost.

Given a plan that determines the scale level of each facility, we also use heuristic way to evaluate its feasibility and cost.

  1. List all customers.
  2. If for any customer, there is no open facility that is close enough, we conclude that the current plan is infeasible.
  3. Otherwise for customer i, we assign it to the closest open facility j, that has enough capacity.
  4. Whenever one more engineer is needed for a facility, add one there.

But you may correctly evaluate how good your heuristic algorithm is, only if you have an optimal solution or a lower bound of your optimal solution. Designing an algorithm is easy, but evaluating it is hard.

Also remember there are always something can not be quantified. The decision-maker is still the key, who should know what is inside the model.



My Certificate

For more on Heuristic Algorithms: A Case Study, please refer to the wonderful course here https://www.coursera.org/learn/operations-research-algorithms



I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai

All of your support will be used for maintenance of this site and more great content. I am humbled and grateful for your generosity. Thank you!




Don't forget to sign up newsletter, don't miss any chance to learn.

Or share what you've learned with friends!