Metadata-Version: 2.4
Name: orkit-edu
Version: 0.1.0
Summary: Educational Operations Research algorithms in plain Python
Author: Meghashyam
License-Expression: MIT
Classifier: Programming Language :: Python :: 3
Classifier: Intended Audience :: Education
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.24.0
Requires-Dist: matplotlib>=3.7.0
Dynamic: license-file

# 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`<br>`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`<br>`north_west_corner`<br>`least_cost_method`<br>`vogels_approximation`<br>`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`<br>`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`<br>`column_maxima`<br>`maximin`<br>`minimax`<br>`find_saddle_points`<br>`solve_pure_strategy`<br>`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`<br>`display_result` | Formats solver result dictionaries into clean, tabular, viva-ready terminal reports. |


---

## 4. Project Structure

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

> [!NOTE]
> PyPI installation will only work after the package is published to PyPI.

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

```bash
pip install orkit-edu
```

Then in Python:
```python
import orkit
```

### Clone and Install in Editable Mode
```bash
# 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:
```bash
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):

```python
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)
```python
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
```python
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)
```python
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)
```python
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
```python
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
```bash
python examples/sample_problems.py
```

### Run Test Suite
```bash
pytest
```

### Execute Notebooks
The five demonstration notebooks can be launched interactively via Jupyter:
```bash
jupyter notebook
```
Or executed headless one notebook per command with outputs saved in-place. The kernel must be installed once per machine with:
```bash
python -m ipykernel install --user --name orkit-venv
```
Then execute each notebook specifying the registered kernel:
```bash
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
