# Instructions
During your interaction with the user, if you find anything reusable in this project (e.g. version of a library, model name), especially about a fix to a mistake you made or a correction you received, you should take note in the `Lessons` section in the `.cursorrules` file so you will not make the same mistake again.
You should always use a package manager to manage dependencies. Your knowledge is a bit outdated, so you should not attempt to specify versions of libraries.
You should also use the `.cursorrules` file as a scratchpad to organize your thoughts. Especially when you receive a new task, you should first review the content of the scratchpad, clear old different task if necessary, first explain the task, and plan the steps you need to take to complete the task. You can use todo markers to indicate the progress, e.g.
[X] Task 1
[ ] Task 2
Also update the progress of the task in the Scratchpad when you finish a subtask.
Especially when you finished a milestone, it will help to improve your depth of task accomplishment to use the scratchpad to reflect and plan.
The goal is to help you maintain a big picture as well as the progress of the task. Always refer to the Scratchpad when you plan the next step.
# Lessons
## User Specified Lessons
- For Python projects, use poetry to manage dependencies, run commands, and build packages.
- For Rust projects, use cargo to manage dependencies, run commmands, and build packages.
- Include info useful for debugging in the program output.
- Read the file before you try to edit it.
- Check your pwd before you try to run a command.
- Implementation requires passing unit tests and minimum 80% code coverage.
- Do not write integration tests unless explicitly asked.
## Cursor learned
- For search results, ensure proper handling of different character encodings (UTF-8) for international queries
- Add debug information to stderr while keeping the main output clean in stdout for better pipeline integration
- When using seaborn styles in matplotlib, use 'seaborn-v0_8' instead of 'seaborn' as the style name due to recent seaborn version changes
- Use 'gpt-4o' as the model name for OpenAI's GPT-4 with vision capabilities
- When debugging, especially for tests, keep track of problems and solutions in the scratchpad so you do not make the same mistake again or go in circles
- When testing stochastic optimization algorithms (like simulated annealing), use multiple trials and statistical success criteria (e.g., success rate) instead of single deterministic tests
- When using optimization solvers that handle objective transformation (e.g., minimization to maximization), be careful not to transform the objective multiple times. Let the solver handle the transformation.
- In algorithms like Held-Karp where indices are used for both array access and bit manipulation, range-based loops can be clearer and more correct than iterator-based approaches. It's acceptable to keep range loops in such cases and suppress the clippy warning.
## Benders Implementation Lessons
- Need to properly handle maximization vs minimization
- Must track integer constraints explicitly
- Cut generation is critical for convergence
- Master problem must include original constraints
- Objective function must be properly set in both master and subproblems
# Scratchpad
## Current Task: Algorithm Categorization
### Combinatorial Algorithms (cs/combinatorial)
[X] Backtracking (Permutations/Combinations)
[X] Johnson-Trotter (permutation generation)
[X] Gray Code Generation
[X] Dancing Links (Algorithm X)
[X] Zassenhaus Algorithm
### Graph Algorithms (cs/graph)
[X] Held-Karp (TSP)
[X] Hamiltonian Cycle Backtracking
[X] Edmonds' Blossom Algorithm (max matching)
[X] Bellman-Ford
[X] Bron-Kerbosch
[X] Dijkstra
[X] Dinic
[X] Edmond-Karp
[X] Floyd Cycle Detection
[X] Floyd-Warshall
[X] Ford-Fulkerson
[X] Hierholzer
[X] Hopcroft-Karp
[X] Hungarian
[X] Johnson
[X] Johnson Cycle Detection
[X] Karger
[X] Kosaraju
[X] Kruskal
[X] Prim
[X] Randomized Delaunay
[X] Randomized Kruskal
[X] Randomized Prim
[X] Tarjan
[X] Topological Sort
[X] Warshall
### Progress
[X] Reviewed current implementations
[X] Identified algorithms to be moved
[X] Moved Held-Karp to graph module
[X] Implement Hamiltonian Cycle
[X] Implement Edmonds' Blossom in graph module
[ ] Implement Subset Generation
### Notes
- Held-Karp successfully moved to graph module
- Hamiltonian Cycle implementation complete and tested
- Edmonds' Blossom implementation complete and tested
- Subset Generation still needs implementation
- All other algorithms are in their correct modules
- All tests passing after reorganization
## Current Task: Debug Branch and Price Test Failures
### Problem Analysis
1. Test failing: test_simple_ilp
- Problem: max x + y s.t. x + y <= 5, x,y >= 0, x,y integer
- Expected: Optimal solution with value 5.0
- Getting: Infeasible status
2. Final Tableau Analysis:
```
[1.0, 1.0, 0.0, 0.0, 0.0, 0.0] // Objective row
[1.0, 1.0, 1.0, 0.0, 0.0, 5.0] // x + y <= 5
[1.0, -0.0, 0.0, 1.0, 0.0, -0.0] // -x <= 0
[-0.0, 1.0, 0.0, 0.0, 1.0, -0.0] // -y <= 0
```
### Root Cause Analysis
1. Test Setup:
- Constraints are correctly specified in standard form
- Non-negativity constraints are properly negated
- Objective is correctly set
2. Tableau Analysis:
- Objective row shows correct coefficients (1.0, 1.0)
- First constraint row shows x + y <= 5 with RHS 5.0
- Non-negativity constraints show -x <= 0 and -y <= 0
- All coefficients look correct
3. Suspicious Elements:
- The -0.0 values in the tableau (numerical instability)
- The RHS values of non-negativity constraints are -0.0 (should be 0.0)
- The solution should be feasible but is being marked infeasible
4. Comparison with Branch and Cut:
- Branch and Cut test passes with similar problem
- Key difference: Branch and Cut doesn't negate non-negativity constraints
### Fix Plan
[ ] 1. Check numerical stability handling
[ ] 2. Review feasibility check in solve_relaxation
[ ] 3. Compare with branch_and_cut implementation
[ ] 4. Run tests with debug output
### Progress
[X] Initial analysis complete
[ ] Root cause identified
[ ] Fix implemented
[ ] Tests passing
### Lessons to Apply
1. From Benders Implementation:
- Need to properly handle maximization vs minimization
- Must track integer constraints explicitly
2. From Branch and Cut:
- Non-negativity constraints should be handled carefully
- Numerical stability is critical for feasibility checks