Integer linear programming (ILP) formulation
Design, assemble, and rigorously audit modular ILP models, with exact proofs of which constraints are truly ideal.
- Turn a word-problem into a correct ILP: scheduling, assignment, covering, routing, coloring → a clean MathProg model with variables and constraints properly classified.
- "Is this constraint actually doing anything?": audit an existing model to prove which valid inequalities are ideal vs. which a modern solver already recovers, so you stop adding useless cuts
- "My MILP is too slow": diagnose whether to shrink the model or tighten the relaxation, using the size-over-tightness heuristic plus a real audit.
$20
· or 100 creditsSecure checkout via Stripe
Included in download
- Turn a word-problem into a correct ILP: scheduling, assignment, covering, routing, coloring → a clean MathProg model with variables and constraints properly classified.
- "Is this constraint actually doing anything?": audit an existing model to prove which valid inequalities are ideal vs. which a modern solver already recovers, so you stop adding useless cuts
- terminal automation included
- Ready for Primarily designed to work with GLPK
Sample input
Formulate minimum graph colouring as an ILP in MathProg, and colour this graph: vertices 1–4, edges 1–2, 2–3, 3–4, 4–1, 1–3.
Sample output
1 — structured problem summary (the skill's Phase 1): SETS: V (vertices), E ⊆ V×V (edges), C = 1..|V| (colour slots) ESSENTIAL VARS: x[v,c] ∈ {0,1} — vertex v takes colour c AUXILIARY VARS: w[c] ∈ {0,1} — colour c is used CONSTRAINTS (essential): each vertex exactly one colour; edge endpoints can't share a colour (and that colour then counts as used) CONSTRAINTS (symmetry): use colours in index order — kills colour-permutation symmetry OBJECTIVE: minimize Σ_c w[c] (number of colours used) 2 — the MathProg model (min_colouring.mod): set V; # vertices set E within V cross V; # edges param K := card(V); # upper bound on colours set C := 1..K; # colour slots var x{V, C} binary; # x[v,c] = 1 iff vertex v gets colour c var w{C} binary; # w[c] = 1 iff colour c is used minimize Colours: sum{c in C} w[c]; s.t. OneColour{v in V}: sum{c in C} x[v,c] = 1; s.t. Proper{(u,v) in E, c in C}: x[u,c] + x[v,c] <= w[c]; s.t. SymBreak{c in C: c < K}: w[c] >= w[c+1]; # use colours in order solve; printf "colours used = %d\n", sum{c in C} w[c]; for {v in V} printf "vertex %d -> colour %d\n", v, sum{c in C} c * x[v,c]; data; set V := 1 2 3 4; set E := (1,2) (2,3) (3,4) (4,1) (1,3); end; 3 — solve it (glpsol --math min_colouring.mod): colours used = 3 vertex 1 -> colour 1 vertex 2 -> colour 2 vertex 3 -> colour 3 vertex 4 -> colour 2 (The triangle 1–2–3 forces 3 colours; vertex 4 reuses colour 2. χ = 3. ✓) 4 — the value-add the skill flags: colouring is the textbook symmetry trap — any colour relabelling is an equivalent solution, which balloons the search. The SymBreak line (w[c] ≥ w[c+1]) is the skill earning its keep: it spots the symmetry and breaks it, rather than just transcribing the obvious model.
Integer linear programming (ILP) formulation
Design, assemble, and rigorously audit modular ILP models, with exact proofs of which constraints are truly ideal.
$20
· or 100 creditsSecure checkout via Stripe
Included in download
- Turn a word-problem into a correct ILP: scheduling, assignment, covering, routing, coloring → a clean MathProg model with variables and constraints properly classified.
- "Is this constraint actually doing anything?": audit an existing model to prove which valid inequalities are ideal vs. which a modern solver already recovers, so you stop adding useless cuts
- terminal automation included
- Ready for Primarily designed to work with GLPK
- Instant install
Sample input
Formulate minimum graph colouring as an ILP in MathProg, and colour this graph: vertices 1–4, edges 1–2, 2–3, 3–4, 4–1, 1–3.
Sample output
1 — structured problem summary (the skill's Phase 1): SETS: V (vertices), E ⊆ V×V (edges), C = 1..|V| (colour slots) ESSENTIAL VARS: x[v,c] ∈ {0,1} — vertex v takes colour c AUXILIARY VARS: w[c] ∈ {0,1} — colour c is used CONSTRAINTS (essential): each vertex exactly one colour; edge endpoints can't share a colour (and that colour then counts as used) CONSTRAINTS (symmetry): use colours in index order — kills colour-permutation symmetry OBJECTIVE: minimize Σ_c w[c] (number of colours used) 2 — the MathProg model (min_colouring.mod): set V; # vertices set E within V cross V; # edges param K := card(V); # upper bound on colours set C := 1..K; # colour slots var x{V, C} binary; # x[v,c] = 1 iff vertex v gets colour c var w{C} binary; # w[c] = 1 iff colour c is used minimize Colours: sum{c in C} w[c]; s.t. OneColour{v in V}: sum{c in C} x[v,c] = 1; s.t. Proper{(u,v) in E, c in C}: x[u,c] + x[v,c] <= w[c]; s.t. SymBreak{c in C: c < K}: w[c] >= w[c+1]; # use colours in order solve; printf "colours used = %d\n", sum{c in C} w[c]; for {v in V} printf "vertex %d -> colour %d\n", v, sum{c in C} c * x[v,c]; data; set V := 1 2 3 4; set E := (1,2) (2,3) (3,4) (4,1) (1,3); end; 3 — solve it (glpsol --math min_colouring.mod): colours used = 3 vertex 1 -> colour 1 vertex 2 -> colour 2 vertex 3 -> colour 3 vertex 4 -> colour 2 (The triangle 1–2–3 forces 3 colours; vertex 4 reuses colour 2. χ = 3. ✓) 4 — the value-add the skill flags: colouring is the textbook symmetry trap — any colour relabelling is an equivalent solution, which balloons the search. The SymBreak line (w[c] ≥ w[c+1]) is the skill earning its keep: it spots the symmetry and breaks it, rather than just transcribing the obvious model.
About This Skill
Most ILP/MILP modeling goes wrong in one of two ways: the model grows into one unmaintainable file, and people claim their constraints are tight or "ideal" without ever proving it. This skill fixes both. Developed by a MILP practitioner with over 20 years of experience in industry and academia, this skill guides you through a disciplined five-phase workflow: problem definition → modular formulation → assembly → tightness audit → refinement. Your modular optimization model in GLPK/MathProg is then compiled into the universal LP format. Jump in at any phase: start from scratch, add a constraint module, assemble modules into one runnable file, or audit an existing formulation. What sets it apart: a real tightness audit. Phase 4 doesn't eyeball your constraints; it proves whether a constraint family is ideal using exact-rational convex-hull / vertex enumeration (the cddlib engine, which ports to Python via pycddlib or to R via rcdd). A seven-check method covers total unimodularity, McCormick envelopes, big-M vs disaggregation, and modern-solver cut recovery, so you stop shipping "valid inequalities" that do nothing and learn which ones actually matter. Modular by construction. Bundled helpers (assembleModel, parseModule, checkDependencies, findDuplicateNames) merge ordered .mod modules into one runnable model, catch duplicate declarations, and verify dependencies, so large models stay readable across sessions. Battle-tested, not theoretical. Stress-tested on classic Erwin Kalvelagen's examples and used to audit ILPs from multiple published papers (validated against Gurobi, CPLEX, and CBC). Encodes hard-won heuristics, such as: for modern solvers prioritize model-size reductions over LP-relaxation tightening, since a good cut engine recovers bound tightenings for free but can't shrink a bloated model. Who it is for: operations researchers, MILP practitioners, and anyone formulating combinatorial problems (job or staff scheduling, vehicle routing, network design) who wants provably correct, tight, maintainable models.
Use Cases
- Turn a word-problem into a correct ILP: scheduling, assignment, covering, routing, coloring → a clean MathProg model with variables and constraints properly classified.
- "Is this constraint actually doing anything?": audit an existing model to prove which valid inequalities are ideal vs. which a modern solver already recovers, so you stop adding useless cuts
- "My MILP is too slow": diagnose whether to shrink the model or tighten the relaxation, using the size-over-tightness heuristic plus a real audit.
- Tame a sprawling model: split a monolithic .mod into dependency-checked modules and assemble them without duplicate-name bugs.
- Reproduce / validate a paper's ILP formulation: check a published formulation against its tightness and correctness claims with exact-rational proofs.
- Research-grade combinatorial models: scheduling, routing, network design, matching, where correctness and tractability both matter.
- Feasibility / CSP problems: Sudoku- or passcode-style "find any feasible X" via the same ILP machinery.
Known Limitations
Does not currently work directly with GAMS Does not include solver-specific tuning, by design - only sharpens the ILP formulation
How to Install
mkdir -p ~/.claude/skills && curl -sL https://www.agensi.io/api/install/integer-linear-programming-ilp-formulation -o /tmp/integer-linear-programming-ilp-formulation.zip && unzip -o /tmp/integer-linear-programming-ilp-formulation.zip -d ~/.claude/skills && rm /tmp/integer-linear-programming-ilp-formulation.zipFree skills install directly. Paid skills require purchase - use the download button above after buying.
Reviews
No reviews yet - be the first to share your experience.
Only users who have downloaded or purchased this skill can leave a review.
Early access skill
Be the first to review this skill.
Only users who have downloaded or purchased this skill can leave a review.
Security Scanned
Passed automated security review
Permissions
File Scopes
Tags
Primarily designed to work with GLPK/MathProg, but creates universal LP files that can be read into Gurobi, CPLEX and open-source solvers (COIN OR, Google OR-tools, etc). Compatible with both Python-based and R-based workflows. GLPK (glpsol) required; R + rcdd strongly recommended for the audit (Python pycddlib also works); CPLEX/Gurobi optional for scale.