Summary

Optimization(or combinatorial optimization) aims to find the best solution to a problem out of a very large set of possible solutions(system of linear equations and inequalities). As search them all isn't(yet) optimal, one must narrow down the search set. As examples:

• Constraint programming

• Linear and Mixed-Integer Programming

• Vehicle Routing

• Graph algorithms

Tools & libraries

• OR-Tools

• SciPy

• PuLP

• Gurobi

• Python-MIP

• Pyomo

• CVXOPT

And the list goes on and on...

General Workflow

1. Create models

2. Decision variables(independent variables as continuous, semi or integer values to be maximized or minimized)

3. Objective function(the goal or cost function)

4. Constraints(equality or inequalities equations to be satisfied)

Problem

Let's do a classic combinatorial optimization problem, "Resource Constrained Project Scheduling(RCPS)", a more practical example:  

Find a feasible scheduling for a set of n jobs subject to resource and precedence constraints.

Each job has a processing time, a set of successors jobs and a required amount of different resources. Resources may be scarce but are renewable at each time period. 

Precedence constraints between jobs mean that no jobs may start before all its predecessors are completed. The jobs must be scheduled non-preemptively, i.e., once started, their processing cannot be interrupted.

J jobs set

R renewable resources set

S set of precedences between jobs (i,j)∈J×J

T planning horizon: set of possible processing times for jobs

pj processing time of job j

u(j,r) amount of resource r required for processing job j

cr capacity of renewable resource r