# Heuristic Algorithms: A Case Study

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 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 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``````

## 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