Integer linear programming (ILP) formulation

Name: Integer linear programming (ILP) formulation
Price: 20 USD
Availability: InStock
Author: Agensi

by Leonid Chindelevitch

Design, assemble, and rigorously audit modular ILP models, with exact proofs of which constraints are truly ideal.

$20

30-day refund guarantee

Secure checkout via Stripe

0 installsSecurity scanned

Works with the AI tools you already use

CCCGGVW+15 more

See it in action

You say

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.

Your agent does

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.

What you get

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.

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.

combinatorial-optimization

ilp

milp

linear-programming