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 model | Select useful information. Describe problems in words that a non-technical people can understand. Usually not precise enough to write computer programs. |
| Mathematical model | Consist of decision variables, constraints and objective function. Specification for writing programs. The most difficult and important part.- heart of Operations Research. |
| Computer model | Hard 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 |
| wj | Employee number assigned to facility j |
Define parameters
| fjk | Annual office rent of location j with scale k |
| hi | Annual number of services needed by customer i |
| dij | Cost per service between facility j and customer i |
| cj | Cost for hosting one employee in facility j |
| mjk | Max number of employees hosted in facility j with scale level k |
| s | Number 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 wjDefine constraints
| ∑k∈K xjk ≤ 1, ∀ j ∈ J | For any facility j, we choose 1 scale level k |
| yij ≤ ∑k∈K xjk, ∀ i ∈ I, j ∈ J | Only a built facility can serve customers |
| ∑j∈J aij yij = 1, ∀ i ∈ I | For each customer, it must be served by a facility close enough |
| wj ≤ ∑k∈K mjk xjk, ∀ j ∈ J | Number of employee in a facility can not exceeds its capacity |
| ∑i∈I hi yij ≤ s wj, ∀ j ∈ J | Employees 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.
- Open all the facilities with largest scale level.
- In each iteration, we greedily try to improve the current solution by downsizing exactly one facility by one scale level.
- If there are multiple choices of reducing the total costs, we choose the one that brings in the largest reduction.
- 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.
- List all customers.
- If for any customer, there is no open facility that is close enough, we conclude that the current plan is infeasible.
- Otherwise for customer i, we assign it to the closest open facility j, that has enough capacity.
- 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
Related Quick Recap
I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai
Don't forget to sign up newsletter, don't miss any chance to learn.
Or share what you've learned with friends!
Tweet
