mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
hanzoskills.com/llms.txt now opens with the install line, the API reference index and the company index, so an agent that lands on any one of the three can find the rest. robots.txt claimed 537 documents while llms.txt counts 920. The number is gone from robots.txt; llms.txt derives it. public/ is regenerated from scripts/site.py, which it had fallen behind: the copy-prompt menu and agent bar were in the generator and not in the committed pages. tests/site.mjs passes against the result. Co-authored-by: Hanzo Dev <[email protected]>
512 lines
26 KiB
HTML
512 lines
26 KiB
HTML
<!doctype html>
|
||
<html lang="en"><head>
|
||
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
||
<title>formal-csp-modeling</title>
|
||
<meta name="color-scheme" content="dark">
|
||
<style>
|
||
/* Committed to one visual world: a dark instrument panel. No light variant —
|
||
the dot field and the hairline rules only read on black, and a naive
|
||
inversion would wash both out. Every colour is painted explicitly so the page
|
||
never borrows a host background. */
|
||
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
||
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
||
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
||
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
||
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
|
||
|
||
:root{
|
||
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
|
||
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
|
||
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
|
||
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
|
||
--font-zen-pixel-square:'Zen Pixel Square',monospace;
|
||
--mono:var(--font-zen-mono);
|
||
--sans:var(--font-zen-sans);
|
||
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
|
||
--r:999px; --r-soft:14px;
|
||
}
|
||
*{box-sizing:border-box}
|
||
html{-webkit-text-size-adjust:100%}
|
||
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
|
||
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
|
||
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
|
||
|
||
/* The dot field. A halftone made of one repeating radial-gradient, faded out
|
||
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
|
||
/* No overflow clip here: the dot field is inset to the box already, and a clip
|
||
would cut off the copy-prompt menu. */
|
||
.hero{position:relative;border-bottom:1px solid var(--line)}
|
||
.hero::before{content:"";position:absolute;inset:0;
|
||
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
|
||
background-size:7px 7px;
|
||
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
||
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
||
pointer-events:none}
|
||
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
|
||
|
||
nav{border-bottom:1px solid var(--line)}
|
||
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
|
||
justify-content:space-between;align-items:center;gap:1rem}
|
||
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
|
||
text-transform:uppercase;color:var(--ink);text-decoration:none;
|
||
display:inline-flex;align-items:center;gap:.6rem}
|
||
.brand i{font-style:normal;color:var(--faint)}
|
||
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
|
||
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
|
||
text-transform:uppercase;color:var(--soft);text-decoration:none}
|
||
nav a.up:hover{color:var(--ink)}
|
||
|
||
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
|
||
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
|
||
h1 em{font-style:normal;color:var(--faint)}
|
||
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
|
||
|
||
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
|
||
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
|
||
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
|
||
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
|
||
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
|
||
line-height:1.2;font-weight:400}
|
||
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
|
||
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
|
||
.btn.solid:hover{background:#d8d8d4}
|
||
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
|
||
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
|
||
|
||
/* Copy-prompt selector. Each row copies the prompt for its own target. */
|
||
.copy{position:relative;display:inline-flex}
|
||
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
|
||
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
|
||
padding:.4rem;display:flex;flex-direction:column;
|
||
box-shadow:0 12px 32px rgba(0,0,0,.75)}
|
||
.menu[hidden]{display:none}
|
||
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
|
||
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
|
||
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
|
||
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
|
||
white-space:nowrap}
|
||
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
|
||
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
|
||
.mi:hover .mark{color:var(--ink)}
|
||
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
|
||
letter-spacing:.1em;text-transform:uppercase}
|
||
|
||
/* Works-with bar: one scrolling row, name and mark per agent. */
|
||
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
|
||
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
|
||
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
|
||
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
|
||
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
|
||
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
|
||
display:flex;align-items:center}
|
||
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
|
||
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
|
||
-webkit-overflow-scrolling:touch;
|
||
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
|
||
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
|
||
.bar::-webkit-scrollbar{display:none}
|
||
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
|
||
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
|
||
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
|
||
text-decoration:none;background:var(--ground)}
|
||
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
|
||
.agent .mark{width:.95rem;height:.95rem}
|
||
|
||
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
|
||
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
|
||
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
|
||
p{margin:0 0 1rem;max-width:70ch}
|
||
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
|
||
li{margin:.22rem 0}
|
||
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
|
||
text-decoration-color:var(--line-hi)}
|
||
a:hover{text-decoration-color:var(--ink)}
|
||
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
|
||
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
|
||
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
|
||
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
|
||
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
|
||
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
|
||
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
|
||
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
|
||
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
|
||
display:block;overflow-x:auto}
|
||
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
|
||
|
||
.curl{display:block;background:var(--panel);border:1px solid var(--line);
|
||
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
|
||
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
|
||
white-space:pre;line-height:1.9}
|
||
.curl b{color:var(--ink);font-weight:400}
|
||
.curl i{font-style:normal;color:var(--faint)}
|
||
|
||
/* index */
|
||
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
|
||
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
|
||
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
|
||
#q:focus{outline:none;border-color:var(--soft)}
|
||
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
|
||
text-transform:uppercase;margin:0 0 2rem}
|
||
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
|
||
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
|
||
padding-bottom:.45rem}
|
||
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
|
||
border-radius:var(--r-soft);text-decoration:none}
|
||
.row:hover{background:#0a0a0a}
|
||
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
|
||
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
|
||
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
|
||
color:var(--faint);font-size:.85rem}
|
||
footer a{color:var(--soft)}
|
||
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
|
||
margin:0 0 2rem;font-size:.85rem}
|
||
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
|
||
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
|
||
border-bottom:1px solid var(--line);padding-bottom:.4rem}
|
||
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
|
||
.fmap a:hover{text-decoration:underline}
|
||
.fmap div{color:var(--faint);line-height:1.5}
|
||
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
|
||
|
||
@media (max-width:640px){
|
||
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
|
||
.btns{gap:.5rem}
|
||
.btn{padding:.75rem 1.15rem;font-size:.68rem}
|
||
.copy,.copy .btn{width:100%;justify-content:center}
|
||
.menu{left:0;right:0;min-width:0}
|
||
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
|
||
.strip b{border-right:0;padding-right:0}
|
||
.bar{width:100%}
|
||
}
|
||
</style>
|
||
<link rel="alternate" type="text/markdown" href="/formal-csp-modeling.md">
|
||
|
||
<link rel="icon" href="/favicon.svg">
|
||
<link rel="canonical" href="https://hanzoskills.com/formal-csp-modeling">
|
||
</head>
|
||
<!-- Reading this with a machine? Every page here is also plain markdown.
|
||
This one: https://hanzoskills.com/formal-csp-modeling.md
|
||
Index: https://hanzoskills.com/llms.txt
|
||
Corpus: https://hanzoskills.com/all.md
|
||
Append .md to any path for the markdown twin. -->
|
||
<body>
|
||
<nav><div class="in">
|
||
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
|
||
<a class="up" href="/">All skills</a>
|
||
</div></nav>
|
||
|
||
<div class="wrap">
|
||
<h1>formal-csp-modeling</h1><p class="lede">Modeling scheduling problems (meetings, courses, jobs)</p><h1>CSP Modeling</h1>
|
||
<p><strong>Scope</strong>: Constraint satisfaction problem modeling, variables, domains, constraints, problem formulation <strong>Lines</strong>: ~330 <strong>Last Updated</strong>: 2025-10-18</p>
|
||
<h2>When to Use This Skill</h2>
|
||
<p>Activate this skill when:</p>
|
||
<ul><li>Modeling scheduling problems (meetings, courses, jobs)</li><li>Solving allocation problems (resources, tasks, assignments)</li><li>Implementing puzzle solvers (Sudoku, N-Queens, graph coloring)</li><li>Formulating planning problems with constraints</li><li>Converting real-world problems to CSP representation</li><li>Designing constraint-based optimization systems</li><li>Building configuration or layout generation systems</li></ul>
|
||
<h2>Core Concepts</h2>
|
||
<h3>CSP Components</h3>
|
||
<p><strong>Variables</strong>: Decision points in the problem</p>
|
||
<ul><li>Represent unknowns to be assigned values</li><li>Example: Square positions in Sudoku, class time slots</li><li>Choose granularity carefully (too fine = slow, too coarse = inflexible)</li><li>Notation: X = {X₁, X₂, ..., Xₙ}</li></ul>
|
||
<p><strong>Domains</strong>: Possible values for each variable</p>
|
||
<ul><li>Finite set of values each variable can take</li><li>Example: {1-9} for Sudoku, {Mon-Fri} for scheduling</li><li>Can be discrete (integers, colors) or continuous (ranges)</li><li>Notation: D = {D₁, D₂, ..., Dₙ} where Dᵢ is domain for Xᵢ</li></ul>
|
||
<p><strong>Constraints</strong>: Rules limiting variable assignments</p>
|
||
<ul><li><strong>Unary</strong>: Single variable (X₁ ≠ 5)</li><li><strong>Binary</strong>: Two variables (X₁ ≠ X₂)</li><li><strong>N-ary</strong>: Multiple variables (X₁ + X₂ + X₃ = 10)</li><li><strong>Global</strong>: Complex patterns (AllDifferent, Cardinality)</li><li>Notation: C = {C₁, C₂, ..., Cₘ}</li></ul>
|
||
<h3>Constraint Types</h3>
|
||
<p><strong>Explicit constraints</strong>: Enumerate allowed/forbidden tuples</p>
|
||
<pre><code class="lang-python"># Binary constraint: allowed pairs
|
||
constraint = {(1, 2), (1, 3), (2, 3), (2, 4)}</code></pre>
|
||
<p><strong>Implicit constraints</strong>: Expressed as functions/predicates</p>
|
||
<pre><code class="lang-python"># Mathematical constraint
|
||
def constraint(x1, x2):
|
||
return x1 + x2 <= 10</code></pre>
|
||
<p><strong>Global constraints</strong>: High-level patterns</p>
|
||
<ul><li><code>AllDifferent(X)</code>: All variables have different values</li><li><code>Cardinality(X, v, min, max)</code>: Value v appears min-max times</li><li><code>Cumulative(tasks, resources)</code>: Resource usage constraints</li><li>More efficient than decomposing into binary constraints</li></ul>
|
||
<h3>Constraint Graph</h3>
|
||
<p><strong>Structure</strong>: Graph representation of CSP</p>
|
||
<ul><li>Nodes: Variables</li><li>Edges: Binary constraints between variables</li><li>Hyperedges: N-ary constraints (multiple variables)</li><li>Used for algorithm selection and analysis</li></ul>
|
||
<p><strong>Properties</strong>:</p>
|
||
<ul><li>Tree-structured: O(n·d²) solvable</li><li>Width k: Complexity depends on tree decomposition</li><li>Sparse vs dense affects algorithm choice</li></ul>
|
||
<hr>
|
||
<h2>Patterns</h2>
|
||
<h3>Pattern 1: N-Queens Problem</h3>
|
||
<pre><code class="lang-python">from constraint import Problem, AllDifferentConstraint
|
||
|
||
def solve_n_queens(n):
|
||
"""Place n queens on n×n board with no attacks."""
|
||
problem = Problem()
|
||
|
||
# Variables: One per queen (row), domain: column positions
|
||
cols = range(n)
|
||
for row in range(n):
|
||
problem.addVariable(row, cols)
|
||
|
||
# Constraint: No two queens in same column
|
||
problem.addConstraint(AllDifferentConstraint(), cols)
|
||
|
||
# Constraint: No diagonal attacks
|
||
for row1 in range(n):
|
||
for row2 in range(row1 + 1, n):
|
||
# |row1 - row2| != |col1 - col2|
|
||
problem.addConstraint(
|
||
lambda c1, c2, r1=row1, r2=row2:
|
||
abs(r1 - r2) != abs(c1 - c2),
|
||
(row1, row2)
|
||
)
|
||
|
||
return problem.getSolutions()</code></pre>
|
||
<p><strong>When to use</strong>:</p>
|
||
<ul><li>Placement problems with non-overlapping constraints</li><li>Board game configuration</li><li>Layout generation with separation rules</li></ul>
|
||
<h3>Pattern 2: Sudoku Solver</h3>
|
||
<pre><code class="lang-python">from constraint import Problem, AllDifferentConstraint
|
||
|
||
def solve_sudoku(grid):
|
||
"""Solve 9×9 Sudoku puzzle."""
|
||
problem = Problem()
|
||
|
||
# Variables: Each cell (row, col)
|
||
cells = [(r, c) for r in range(9) for c in range(9)]
|
||
|
||
for r, c in cells:
|
||
if grid[r][c] == 0:
|
||
# Empty cell: domain 1-9
|
||
problem.addVariable((r, c), range(1, 10))
|
||
else:
|
||
# Pre-filled cell: fixed value
|
||
problem.addVariable((r, c), [grid[r][c]])
|
||
|
||
# Row constraints
|
||
for r in range(9):
|
||
problem.addConstraint(
|
||
AllDifferentConstraint(),
|
||
[(r, c) for c in range(9)]
|
||
)
|
||
|
||
# Column constraints
|
||
for c in range(9):
|
||
problem.addConstraint(
|
||
AllDifferentConstraint(),
|
||
[(r, c) for r in range(9)]
|
||
)
|
||
|
||
# 3×3 box constraints
|
||
for box_r in range(3):
|
||
for box_c in range(3):
|
||
cells_in_box = [
|
||
(r, c)
|
||
for r in range(box_r * 3, box_r * 3 + 3)
|
||
for c in range(box_c * 3, box_c * 3 + 3)
|
||
]
|
||
problem.addConstraint(
|
||
AllDifferentConstraint(),
|
||
cells_in_box
|
||
)
|
||
|
||
solutions = problem.getSolutions()
|
||
return solutions[0] if solutions else None</code></pre>
|
||
<p><strong>Benefits</strong>:</p>
|
||
<ul><li>Declarative problem specification</li><li>Automatic constraint propagation</li><li>Easy to add new constraint types</li></ul>
|
||
<h3>Pattern 3: Graph Coloring</h3>
|
||
<pre><code class="lang-python">from constraint import Problem, AllDifferentConstraint
|
||
|
||
def color_graph(graph, num_colors):
|
||
"""Assign colors to graph nodes (no adjacent same color)."""
|
||
problem = Problem()
|
||
|
||
# Variables: Graph nodes
|
||
nodes = list(graph.keys())
|
||
colors = range(num_colors)
|
||
|
||
for node in nodes:
|
||
problem.addVariable(node, colors)
|
||
|
||
# Constraints: Adjacent nodes different colors
|
||
for node, neighbors in graph.items():
|
||
for neighbor in neighbors:
|
||
if node < neighbor: # Avoid duplicate constraints
|
||
problem.addConstraint(
|
||
lambda c1, c2: c1 != c2,
|
||
(node, neighbor)
|
||
)
|
||
|
||
return problem.getSolutions()
|
||
|
||
# Example: Map coloring
|
||
us_map = {
|
||
'WA': ['OR', 'ID'],
|
||
'OR': ['WA', 'ID', 'NV', 'CA'],
|
||
'CA': ['OR', 'NV', 'AZ'],
|
||
# ... more states
|
||
}
|
||
|
||
solutions = color_graph(us_map, num_colors=4)</code></pre>
|
||
<p><strong>When to use</strong>:</p>
|
||
<ul><li>Register allocation in compilers</li><li>Frequency assignment in wireless networks</li><li>Time slot assignment avoiding conflicts</li></ul>
|
||
<h3>Pattern 4: Scheduling with OR-Tools</h3>
|
||
<pre><code class="lang-python">from ortools.sat.python import cp_model
|
||
|
||
def schedule_jobs(jobs, machines):
|
||
"""Schedule jobs on machines minimizing makespan."""
|
||
model = cp_model.CpModel()
|
||
|
||
# Variables: start_time and machine for each job
|
||
starts = {}
|
||
machines_assigned = {}
|
||
|
||
for job_id, duration in jobs.items():
|
||
starts[job_id] = model.NewIntVar(0, 1000, f'start_{job_id}')
|
||
machines_assigned[job_id] = model.NewIntVar(
|
||
0, len(machines) - 1, f'machine_{job_id}'
|
||
)
|
||
|
||
# Constraint: Jobs on same machine don't overlap
|
||
intervals_per_machine = [[] for _ in machines]
|
||
|
||
for job_id, duration in jobs.items():
|
||
for machine_id in range(len(machines)):
|
||
# Create interval for job on this machine
|
||
interval = model.NewOptionalIntervalVar(
|
||
starts[job_id],
|
||
duration,
|
||
starts[job_id] + duration,
|
||
machines_assigned[job_id] == machine_id,
|
||
f'interval_{job_id}_{machine_id}'
|
||
)
|
||
intervals_per_machine[machine_id].append(interval)
|
||
|
||
# NoOverlap constraint per machine
|
||
for machine_id in range(len(machines)):
|
||
model.AddNoOverlap(intervals_per_machine[machine_id])
|
||
|
||
# Objective: Minimize makespan
|
||
makespan = model.NewIntVar(0, 1000, 'makespan')
|
||
for job_id, duration in jobs.items():
|
||
model.Add(makespan >= starts[job_id] + duration)
|
||
|
||
model.Minimize(makespan)
|
||
|
||
# Solve
|
||
solver = cp_model.CpSolver()
|
||
status = solver.Solve(model)
|
||
|
||
if status == cp_model.OPTIMAL:
|
||
schedule = {
|
||
job_id: {
|
||
'start': solver.Value(starts[job_id]),
|
||
'machine': solver.Value(machines_assigned[job_id])
|
||
}
|
||
for job_id in jobs
|
||
}
|
||
return schedule, solver.Value(makespan)
|
||
|
||
return None, None</code></pre>
|
||
<p><strong>Benefits</strong>:</p>
|
||
<ul><li>Optimization objectives (minimize/maximize)</li><li>Optional intervals for flexible scheduling</li><li>Built-in NoOverlap global constraint</li></ul>
|
||
<h3>Pattern 5: Resource Allocation</h3>
|
||
<pre><code class="lang-python">from constraint import Problem, ExactSumConstraint
|
||
|
||
def allocate_resources(tasks, resources, capacity):
|
||
"""Assign tasks to resources respecting capacity limits."""
|
||
problem = Problem()
|
||
|
||
# Variables: Resource assignment per task
|
||
for task in tasks:
|
||
problem.addVariable(task, resources)
|
||
|
||
# Constraint: Each resource has capacity limit
|
||
for resource in resources:
|
||
# Count tasks assigned to this resource
|
||
tasks_on_resource = [
|
||
task for task in tasks
|
||
]
|
||
|
||
# Custom constraint checking capacity
|
||
def capacity_constraint(*assignments):
|
||
count = sum(1 for a in assignments if a == resource)
|
||
return count <= capacity[resource]
|
||
|
||
problem.addConstraint(
|
||
capacity_constraint,
|
||
tasks_on_resource
|
||
)
|
||
|
||
return problem.getSolutions()
|
||
|
||
# Example usage
|
||
tasks = ['T1', 'T2', 'T3', 'T4', 'T5']
|
||
resources = ['R1', 'R2', 'R3']
|
||
capacity = {'R1': 2, 'R2': 2, 'R3': 1}
|
||
|
||
solutions = allocate_resources(tasks, resources, capacity)</code></pre>
|
||
<p><strong>When to use</strong>:</p>
|
||
<ul><li>Server assignment with load limits</li><li>Classroom allocation for courses</li><li>Worker assignment to shifts</li></ul>
|
||
<hr>
|
||
<h2>Quick Reference</h2>
|
||
<h3>CSP Formulation Checklist</h3>
|
||
<pre><code>1. Identify variables: What are you deciding?
|
||
2. Define domains: What values can each variable take?
|
||
3. Specify constraints:
|
||
- Unary: Variable must/cannot be X
|
||
- Binary: Relationships between pairs
|
||
- N-ary: Relationships among groups
|
||
- Global: High-level patterns
|
||
4. Choose optimization objective (if needed)
|
||
5. Select appropriate solver library</code></pre>
|
||
<h3>Common Global Constraints</h3>
|
||
<p>| Constraint | Meaning | Use Case | |------------|---------|----------| | <code>AllDifferent(X)</code> | All variables different | Sudoku, N-Queens | | <code>AllEqual(X)</code> | All variables equal | Consistent labeling | | <code>Cardinality(X, v, min, max)</code> | Value v appears min-max times | Workforce limits | | <code>Sum(X) = k</code> | Variables sum to k | Budget constraints | | <code>NoOverlap(intervals)</code> | Intervals don't overlap | Scheduling | | <code>Cumulative(tasks, limit)</code> | Resource usage ≤ limit | Machine capacity | | <code>Element(index, array, value)</code> | array[index] = value | Lookup constraints |</p>
|
||
<h3>Modeling Guidelines</h3>
|
||
<pre><code>✅ DO: Use global constraints when possible (more efficient)
|
||
✅ DO: Minimize domain sizes (smaller = faster)
|
||
✅ DO: Add redundant constraints if they prune search space
|
||
✅ DO: Choose variable granularity carefully
|
||
❌ DON'T: Model everything as binary constraints
|
||
❌ DON'T: Use variables when constants suffice
|
||
❌ DON'T: Ignore problem structure (tree, bipartite, etc.)
|
||
❌ DON'T: Over-constrain (making problem unsatisfiable)</code></pre>
|
||
<hr>
|
||
<h2>Anti-Patterns</h2>
|
||
<p>❌ <strong>Over-constraining</strong>: Adding contradictory constraints</p>
|
||
<pre><code class="lang-python"># Problem has no solution
|
||
problem.addConstraint(lambda x: x > 10)
|
||
problem.addConstraint(lambda x: x < 5)</code></pre>
|
||
<p>✅ Check constraint consistency before solving</p>
|
||
<p>❌ <strong>Decomposing global constraints unnecessarily</strong></p>
|
||
<pre><code class="lang-python"># Inefficient: AllDifferent as pairwise inequality
|
||
for i in range(n):
|
||
for j in range(i + 1, n):
|
||
problem.addConstraint(lambda xi, xj: xi != xj, (i, j))</code></pre>
|
||
<p>✅ Use <code>AllDifferentConstraint()</code> directly</p>
|
||
<p>❌ <strong>Wrong variable choice</strong></p>
|
||
<pre><code class="lang-python"># Bad: Boolean variables for multi-valued decisions
|
||
# is_blue, is_red, is_green (3 variables per item)</code></pre>
|
||
<p>✅ Use single variable with domain {blue, red, green}</p>
|
||
<p>❌ <strong>Ignoring problem symmetry</strong></p>
|
||
<pre><code class="lang-python"># N-Queens: All solutions are rotations/reflections
|
||
# Returns 92 solutions for 8-Queens (only 12 unique)</code></pre>
|
||
<p>✅ Add symmetry-breaking constraints or post-process</p>
|
||
<p>❌ <strong>Missing implied constraints</strong></p>
|
||
<pre><code class="lang-python"># Scheduling: Only NoOverlap constraint
|
||
# Missing: Task precedence, resource limits</code></pre>
|
||
<p>✅ Add all relevant constraints for complete model</p>
|
||
<hr>
|
||
<h2>Related Skills</h2>
|
||
<ul><li><code>constraint-propagation.md</code> - Reducing domains using constraints</li><li><code>backtracking-search.md</code> - Searching for CSP solutions</li><li><code>sat-solving-strategies.md</code> - Boolean satisfiability (special case of CSP)</li><li><code>optimization-modeling.md</code> - Adding objective functions to CSPs</li><li><code>graph-algorithms.md</code> - Graph coloring and CSP structure</li></ul>
|
||
<hr>
|
||
<p><strong>Last Updated</strong>: 2025-10-18 <strong>Format Version</strong>: 1.0 (Atomic)</p>
|
||
<footer>
|
||
<div class="fmap">
|
||
<div><b>Build</b>
|
||
<a href="https://hanzo.app">hanzo.app</a> app builder
|
||
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
|
||
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
|
||
<div><b>Run</b>
|
||
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
|
||
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
|
||
<div><b>Account</b>
|
||
<a href="https://hanzo.id">hanzo.id</a> sign in
|
||
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
|
||
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
|
||
<div><b>Company</b>
|
||
<a href="https://hanzo.ai">hanzo.ai</a> canonical
|
||
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
|
||
</div>
|
||
<div class="fend"><a href="/formal-csp-modeling.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
||
</footer>
|
||
</div></body></html> |