ORKit: A Python Library for Operations Research Optimization

ORKit is a modular, educational Python library implementing classical Operations Research (OR) optimization algorithms from first principles. Built specifically as an undergraduate mini-project, ORKit prioritizes clarity, transparency, and explainability over industrial scale. Every algorithm is implemented with plain Python loops, conditions, and standard data structures so that every step can be traced and understood in an academic viva.

---

1. Project Overview & Problem Statement

Operations Research algorithms often form the backbone of decision sciences, logistics, and resource allocation. While industrial solvers (such as CPLEX, Gurobi, or PuLP) treat algorithms as black-box solvers, students and educators require clear, inspectable code that mirrors standard textbook steps.

ORKit provides clean, dependency-minimal implementations of core OR techniques without third-party mathematical programming solvers. Every calculation step—from simplex pivots to Hungarian line coverings—is recorded and accessible in plain Python dictionaries.

---

2. Objectives

1. Pedagogical Clarity: Code directly reflects formulations from standard undergraduate OR textbooks.
2. First-Principles Implementation: No solver dependencies (SciPy optimize, PuLP, OR-Tools, CVXPY are strictly excluded).
3. Reproducibility: Hand-verified examples with complete automated test coverage.
4. Interactive Learning: Standalone Jupyter notebooks with step-by-step calculations and visual representations.

---

3. Features & Implemented Algorithms

Module	Algorithms / Functions	Description
LPP (lpp.py)	solve_graphical solve_simplex	Corner-point intersection method for 2-variable linear programs; Tableau-based Simplex method for canonical $\le$ constraints.
Visualization (visualization.py)	plot_feasible_region	Feasible region grid shading, boundary lines, corner point markers, and optimal solution callout (2 variables).
Transportation (transportation.py)	balance_problem north_west_corner least_cost_method vogels_approximation modi_method	Initial feasible solutions via North-West Corner, Least Cost (Matrix Minimum), and Vogel's Approximation Method (VAM); optimal solution via Modified Distribution (MODI / $u$-$v$) method with closed-loop stepping stone pivots.
Assignment (assignment.py)	hungarian_method	Classical Hungarian algorithm (Kuhn-Munkres) with row/column reductions, textbook line covering, and zero-assignment matching. Supports negative costs.
Network (network.py)	cpm pert	Critical Path Method (topological sort, forward/backward passes, slacks, critical path); PERT analysis using 3-point time estimates ($a, m, b$) and critical variance.
Game Theory (game_theory.py)	row_minima column_maxima maximin minimax find_saddle_points solve_pure_strategy solve_mixed_2x2	Zero-sum two-player matrix games; minimax-maximin pure strategy saddle point determination; analytical odds formulas for $2 \times 2$ mixed strategy games.
Display (display.py)	format_result display_result	Formats solver result dictionaries into clean, tabular, viva-ready terminal reports.

---

4. Project Structure

ORKit/
├── orkit/
│   ├── __init__.py          # Exports public API functions
│   ├── core.py              # Shared validation helpers, clean_number & build_result
│   ├── display.py           # Presentation formatters (display_result, format_result)
│   ├── lpp.py               # Graphical and Simplex LPP solvers
│   ├── transportation.py    # NW Corner, Least Cost, VAM, and MODI methods
│   ├── assignment.py        # Hungarian assignment algorithm (supports negative costs)
│   ├── network.py           # CPM schedule and PERT calculations
│   ├── game_theory.py       # Zero-sum pure and 2x2 mixed strategy solvers
│   └── visualization.py     # LPP feasible-region grid plot
├── notebooks/
│   ├── 01_lpp.ipynb
│   ├── 02_transportation.ipynb
│   ├── 03_assignment.ipynb
│   ├── 04_cpm_pert.ipynb
│   └── 05_game_theory.ipynb
├── tests/
│   ├── test_assignment.py
│   ├── test_display.py
│   ├── test_game_theory.py
│   ├── test_lpp.py
│   ├── test_network.py
│   └── test_transportation.py
├── examples/
│   └── sample_problems.py   # Complete runnable demonstration script
├── LICENSE                  # MIT License
├── requirements.txt         # Core dependencies and notebook tooling
├── pyproject.toml           # Packaging configuration for editable install
├── .gitignore               # Git ignore rules for environments and caches
└── README.md                # Project documentation

---

5. Requirements & Installation

ORKit requires Python 3.10+.

Installation from PyPI

The package is published as orkit-edu on PyPI; import it as orkit.

pip install orkit-edu

Then in Python:

import orkit

Clone and Install in Editable Mode

# Optional: create and activate a virtual environment
python -m venv .venv
# Windows:
.venv\Scripts\activate
# Linux/macOS:
source .venv/bin/activate

# Install dependencies and ORKit in editable development mode
pip install -r requirements.txt
pip install -e .

Verify installation:

python -c "import orkit; print('ORKit imported successfully!')"

---

6. Input & Output Formats

All ORKit optimization solvers return plain Python dictionaries containing standard keys:

• "status": "optimal", "infeasible", or "unbounded" (or "no_saddle_point").
• "solution": Dictionary or list containing decision variable values or allocations.
• "objective_value": Numeric optimal value ($Z$, cost, duration, game value).
• "steps": List of human-readable strings explaining each calculation step.

Displaying Results

ORKit includes presentation helpers in orkit.display to render clean, aligned, viva-ready terminal reports. Use display_result(result, show_steps=True) to print the formatted report (or format_result to retrieve the formatted string):

from orkit import solve_graphical, display_result

c = [3, 5]
A = [[1, 0], [0, 2], [3, 2]]
b = [4, 12, 18]
signs = ["<=", "<=", "<="]

result = solve_graphical(c, A, b, signs, maximize=True)

# Display result with step-by-step calculations
display_result(result, show_steps=True)

These helpers are strictly for output formatting; the underlying solver return dictionary remains untouched and directly accessible.

Quick Usage Examples

1. Linear Programming (Graphical & Simplex)

from orkit import solve_graphical, solve_simplex, plot_feasible_region

c = [3, 5]
A = [[1, 0], [0, 2], [3, 2]]
b = [4, 12, 18]
signs = ["<=", "<=", "<="]

# Graphical solver (2 variables)
res_graph = solve_graphical(c, A, b, signs, maximize=True)
print(res_graph["solution"])         # {'x1': 2, 'x2': 6}
print(res_graph["objective_value"])  # 36

# Simplex solver
res_simp = solve_simplex(c, A, b, maximize=True)
print(res_simp["solution"])          # {'x1': 2, 'x2': 6}
print(res_simp["objective_value"])   # 36

# Plot feasible region
fig = plot_feasible_region(c, A, b, signs, maximize=True)
# fig.savefig("feasible_region.png")

2. Transportation Problem

from orkit import vogels_approximation, modi_method

cost_matrix = [
    [19, 30, 50, 10],
    [70, 30, 40, 60],
    [40,  8, 70, 20]
]
supply = [7, 9, 18]
demand = [5, 8, 7, 14]

# Initial solution via VAM
vam_res = vogels_approximation(cost_matrix, supply, demand)
print("VAM Cost:", vam_res["objective_value"])  # 779

# Optimal solution via MODI (u-v method)
modi_res = modi_method(cost_matrix, supply, demand, initial_method="vam")
print("Optimal Cost:", modi_res["objective_value"])  # 743
print("Allocations:", modi_res["allocation"])
# [[5, 0, 0, 2], [0, 2, 7, 0], [0, 6, 0, 12]]

3. Assignment Problem (Hungarian Method)

from orkit import hungarian_method

cost_matrix = [
    [9, 2, 7, 8],
    [6, 4, 3, 7],
    [5, 8, 1, 8],
    [7, 6, 9, 4]
]
res = hungarian_method(cost_matrix)
print("Optimal Cost:", res["objective_value"])  # 13
print("Assignments:", res["assignments"])       # [(0, 1), (1, 0), (2, 2), (3, 3)]

4. Project Network Analysis (CPM & PERT)

from orkit import cpm, pert

# Activity dictionary format: name -> {"duration": num, "predecessors": list}
cpm_activities = {
    "A": {"duration": 3, "predecessors": []},
    "B": {"duration": 4, "predecessors": ["A"]},
    "C": {"duration": 2, "predecessors": ["A"]},
    "D": {"duration": 5, "predecessors": ["B", "C"]},
}
cpm_res = cpm(cpm_activities)
print("Duration:", cpm_res["project_duration"])  # 12
print("Critical Path:", cpm_res["critical_path"]) # ['A', 'B', 'D']
print("Slack:", cpm_res["slack"])                # {'A': 0, 'B': 0, 'C': 2, 'D': 0}

# PERT 3-point estimates: name -> {"a": opt, "m": likely, "b": pess, "predecessors": list}
pert_activities = {
    "A": {"a": 1, "m": 3, "b": 5, "predecessors": []},
    "B": {"a": 2, "m": 4, "b": 6, "predecessors": ["A"]},
    "C": {"a": 1, "m": 2, "b": 3, "predecessors": ["A"]},
    "D": {"a": 3, "m": 5, "b": 7, "predecessors": ["B", "C"]},
}
pert_res = pert(pert_activities)
print("Expected Duration:", pert_res["project_expected_duration"]) # 12
print("Critical Variance:", pert_res["project_variance"])          # 1.33333333

5. Game Theory

from orkit import solve_pure_strategy, solve_mixed_2x2

# Pure strategy saddle point game
saddle_payoff = [[3, 5], [2, 4]]
print(solve_pure_strategy(saddle_payoff))
# status: 'optimal', saddle_points: [(0, 0)], objective_value: 3

# Mixed strategy 2x2 game
mixed_payoff = [[2, 4], [3, 1]]
res = solve_mixed_2x2(mixed_payoff)
print("p:", res["p"])                  # [0.5, 0.5]
print("q:", res["q"])                  # [0.75, 0.25]
print("Value:", res["objective_value"]) # 2.5

---

7. Running Demonstrations, Tests, and Notebooks

Run Sample Problems Script

python examples/sample_problems.py

Run Test Suite

pytest

Execute Notebooks

The five demonstration notebooks can be launched interactively via Jupyter:

jupyter notebook

Or executed headless one notebook per command with outputs saved in-place. The kernel must be installed once per machine with:

python -m ipykernel install --user --name orkit-venv

Then execute each notebook specifying the registered kernel:

python -m jupyter nbconvert --to notebook --execute --inplace --ExecutePreprocessor.kernel_name=orkit-venv notebooks/01_lpp.ipynb
python -m jupyter nbconvert --to notebook --execute --inplace --ExecutePreprocessor.kernel_name=orkit-venv notebooks/02_transportation.ipynb
python -m jupyter nbconvert --to notebook --execute --inplace --ExecutePreprocessor.kernel_name=orkit-venv notebooks/03_assignment.ipynb
python -m jupyter nbconvert --to notebook --execute --inplace --ExecutePreprocessor.kernel_name=orkit-venv notebooks/04_cpm_pert.ipynb
python -m jupyter nbconvert --to notebook --execute --inplace --ExecutePreprocessor.kernel_name=orkit-venv notebooks/05_game_theory.ipynb

---

8. Honest Limitations & Design Assumptions

In accordance with ORKit's educational purpose, scope is deliberately focused on foundational methods:

1. Linear Programming:
   • solve_simplex strictly supports canonical problems with $\le$ constraints and $b \ge 0$ (variables $\ge 0$). Big-M, Two-Phase simplex, and anti-cycling Bland's rule are not implemented.
   • solve_graphical supports exactly 2 decision variables. Unboundedness is detected via an artificial bounding box ($10^6$).
   • plot_feasible_region shades the feasible region using a numerical grid across the bounding view window.
2. Transportation:
   • modi_method supports cost minimization only. Degeneracy is resolved by selecting non-loop-forming cells in row-major order with zero allocation.
3. Assignment:
   • hungarian_method supports square and rectangular matrices (padded with zero-cost dummy rows or columns) and accepts negative costs by shifting the matrix via minimum reduction. The $O(n^3)$ dual potential implementation is omitted in favor of the explainable textbook line-covering method.
4. Project Network:
   • cpm returns one deterministic primary critical path (all critical activities with slack 0 are listed in critical_activities).
   • pert calculates expected critical path duration and variance; normal distribution $Z$-lookup probabilities of completion are not computed. Network diagrams are not generated.
5. Game Theory:
   • Mixed strategy analytical formulas are implemented strictly for $2 \times 2$ zero-sum games without dominance reduction. LP-based solving for $m \times n$ mixed games is out of scope.
6. Display Helpers:
   • Formatters in orkit.display (display_result, format_result) are designed strictly for terminal presentation and student demonstration; they do not alter solver data structures.

---

9. Future Scope (Not Implemented)

The following advanced operations research techniques are NOT implemented in this undergraduate release and represent prospective future work:

• Integer Linear Programming (ILP) and Branch-and-Bound
• Sensitivity and Post-Optimality Analysis
• Job Sequencing and Johnson's Algorithm
• Inventory Control Models (EOQ, EPQ, safety stock)
• Queuing Theory ($M/M/1$, $M/M/c$)
• Monte Carlo Simulation
• $m \times n$ Game Theory via Linear Programming / Subgame Dominance
• Automated PERT/CPM Network Graph rendering