Skip to content

Coursera Discrete Optimization course programming assignments source code

Notifications You must be signed in to change notification settings

balta2ar/discrete-optimization-001

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

76 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

discrete-optimization-001

Coursera Discrete Optimization course programming assignments source code

Below is a list of optimization techniques/topics and languages used for each assignment. Note that all assignments come with default trivial solution in python -- I don't count python unless I implemented something non-trivial in this assignment. Also, I started almost every assignment with implementing greedy or random solver, I don't count them either.

Knapsack

  • Go (DP, BnB solver)
  • Dynamic Programming (DP)
  • Branch and Bound (BnB)

Graph Coloring (GC)

  • Bash (wrapper)
  • Go (CP solver)
  • Constraint Programming (CP)
    • Minimum Remaining Variable (MRV)
    • Least Constraining Value (LCV)
    • Arc Consistency (AC3)

Traveling Salesman Problem (TSP)

  • Bash (wrapper)
  • Go (LS solver)
  • R (visualization)
  • Python
    • visualization (igraph)
    • MIP problem generator, parser
    • scipy.kmeans
  • Local Search (LS)
  • Mixed Integer Programming (MIP)
    • external solver: SCIP
    • problem format: PIP
    • problem formulations: Miller-Tucker-Zemlin, subtour elimination

Warehouse Location Problem (WLP)

  • Bash (wrapper)
  • Python (MIP problem generator, parser)
  • Mixed Integer Programming (MIP)
    • external solver: SCIP
    • problem format: PIP
    • problem formulations: SimpleModel, LectureModel

Vehicle Routing Problem (VRP)

  • Bash (wrapper)
  • Go (LS solver, unit test)
  • R (visualization)
  • Python (MIP problem generator, parser)
  • Local Search (LS)
    • Simulated Annealing (SA)
    • Metropolis
    • neighbour generation moves: 1. move customer from one route to another 2. swap two customers
  • Mixed Integer Programming (MIP)
    • external solver: SCIP
    • problem format: PIP
    • problem formulations: AssignCustomersModel (similar to WLP), OrderCustomersModel (similar to TSP)

Puzzle Challenge (PC)

  • Python (nqueens CP solver back from university times)
  • Octave (magic square)
  • Constraint Programming (CP)
    • Minimum Remaining Variable (MRV)
    • Least Constraining Value (LCV)

About

Coursera Discrete Optimization course programming assignments source code

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published