scip-opt
Solve optimization tasks with PySCIPOpt by building a correct model, proving (near-)optimality when graded, and extracting a validated deliverable.
- License 许可
- Apache-2.0
- 最近更新
- 2026-11-14
- Stars
- ★ 0
- Forks
- 1
01 前言 Front Matter
- name
- scip-opt
- description
- Solve optimization tasks with PySCIPOpt by building a correct model, proving (near-)optimality when graded, and extracting a validated deliverable.
03 SKILL.md 正文
SCIP Optimization
Use SCIP through pyscipopt when a task asks you to minimize or maximize an objective subject to constraints.
SCIP is a strong open-source optimization solver with a Python API. It is well suited for mixed-integer optimization, routing-style models, assignment models, capacity planning, inventory movement, scheduling, and problems with soft penalties. For benchmark tasks, a SCIP-backed model plus an independent validator is usually safer than a greedy construction.
Execution Workflow (don’t stop early)
- Locate and read the input in a way your environment permits (tool sandbox vs terminal).
- Parse input → build sets/mappings → decide modeling approach.
- Build the model (variables, hard constraints, soft penalties, objective).
- Solve, then extract a concrete solution (routes/assignments/amounts) from variable values.
- Write the required deliverable file(s) to the expected path(s).
- Re-open what you wrote and validate completeness (schema keys present, expected counts/IDs covered, and basic invariants). If any check fails, continue working and re-validate.
Read references/deliverable-artifact-check.md when the task is graded on a required JSON/CSV artifact (e.g., report.json) or when a prior attempt ended without writing outputs. Skip when the evaluator reads only stdout and no output file is required.
When To Use
Consider PySCIPOpt when the request includes:
- an objective such as minimizing cost, distance, time, unmet demand, or penalty;
- yes/no choices, route arcs, assignments, selected items, or ordering decisions;
- integer or continuous quantities such as load, inventory, flow, served units, or slack;
- hard rules that every valid answer must satisfy;
- soft rules that can be violated with an explicit penalty.
Do not start by installing another optimization package. First check whether PySCIPOpt is already available:
try:
from pyscipopt import Model, quicksum
except ImportError as exc:
raise RuntimeError("PySCIPOpt is required for this optimization approach") from exc
Modeling Workflow
-
Identify sets and indices.
- Examples: vehicles
K, stationsN, jobsJ, periodsT, arcsA. - Build explicit mappings when input IDs are not contiguous.
- Examples: vehicles
-
Define decision variables.
- Binary variables for choices, visits, assignments, route arcs, or modes.
- Integer variables for counts, loads, inventory moves, or unmet units.
- Continuous variables for flows, costs, times, slacks, or resource levels.
-
Add hard constraints.
- Conservation, capacity, bounds, linking, continuity, inventory limits, and mutual exclusion.
-
Add soft constraints with explicit slack variables.
- Never use Python
abs()on solver expressions. - Linearize absolute deviation with two inequalities.
- Never use Python
-
Set a single objective.
- Keep named objective components such as travel cost and penalty cost.
-
Solve with time and gap limits.
- Require at least one incumbent before extracting a solution.
-
Optimality gate (benchmark objective alignment).
- If the task is graded on objective quality, treat “feasible + self-consistent” as insufficient.
- Before finalizing, inspect solver status, best bound, and the implied optimality gap; if not optimal/tight enough, re-solve with more time or a tighter formulation.
- Also sanity-check semantics that change the feasible set. In particular, decide whether the system is closed (unit conservation) and how initial/end loads are anchored.
- Closed system (no source/sink): enforce system-wide conservation and fix starting loads to the stated value (often 0), with end loads consistent with conservation.
- Depot is a source/sink: constrain depot inventory/supply and link any nonzero start loads or depot transfers to that supply.
- Post-solve quality probe: if any unmet/deviation remains, test whether it can be reduced with a small objective increase (e.g., lexicographic “minimize unmet then distance”, or temporarily raise penalty weights). If it can, treat that as evidence of semantics mismatch or insufficient optimality/tightness.
model.optimize()
status = str(model.getStatus()).lower()
if model.getNSols() == 0:
raise RuntimeError(f"SCIP found no feasible solution; status={status}")
obj = float(model.getObjVal())
try:
bound = float(model.getBestbound())
except Exception:
bound = None
if "optimal" not in status and bound is not None and obj != 0.0:
gap = abs(obj - bound) / abs(obj)
if gap > 1e-4:
raise RuntimeError(f"solution not tight enough: status={status} obj={obj} bound={bound} gap={gap}")
Read references/scip-optimality-gate.md when the benchmark expects (near-)optimal objective value, you used a time limit/nonzero gap, or resource/conservation semantics (optional vehicles, depot source/sink, start loads) are ambiguous. Skip when feasibility alone is graded or when the evaluator explicitly accepts any feasible solution.
Minimal PySCIPOpt Template
from pyscipopt import Model, quicksum
model = Model("optimization_model")
model.hideOutput()
I = range(n_items)
x = {i: model.addVar(vtype="B", name=f"x_{i}") for i in I}
amount = {
i: model.addVar(vtype="I", lb=0, ub=capacity[i], name=f"amount_{i}")
for i in I
}
dev = {i: model.addVar(lb=0, name=f"dev_{i}") for i in I}
for i in I:
model.addCons(amount[i] <= capacity[i] * x[i])
model.addCons(amount[i] - target[i] <= dev[i])
model.addCons(target[i] - amount[i] <= dev[i])
cost = quicksum(fixed_cost[i] * x[i] for i in I)
penalty = penalty_weight * quicksum(dev[i] for i in I)
model.setObjective(cost + penalty, "minimize")
model.setParam("limits/time", 300.0)
model.setParam("limits/gap", 0.01)
model.optimize()
status = str(model.getStatus()).lower()
if model.getNSols() == 0:
raise RuntimeError(f"SCIP found no feasible solution; status={status}")
objective = float(model.getObjVal())
selected = [i for i in I if model.getVal(x[i]) > 0.5]
Common Patterns
Binary Activation
Use a binary variable to allow a quantity only when an option is active.
use = {i: model.addVar(vtype="B", name=f"use_{i}") for i in I}
q = {i: model.addVar(lb=0, ub=upper[i], name=f"q_{i}") for i in I}
for i in I:
model.addCons(q[i] <= upper[i] * use[i])
Assignment
assign = {
(i, j): model.addVar(vtype="B", name=f"assign_{i}_{j}")
for i in items
for j in options
}
for i in items:
model.addCons(quicksum(assign[i, j] for j in options) == 1)
for j in options:
model.addCons(quicksum(weight[i] * assign[i, j] for i in items) <= capacity[j])
Absolute Deviation Penalty
dev = {i: model.addVar(lb=0, name=f"dev_{i}") for i in I}
for i in I:
model.addCons(actual[i] - target[i] <= dev[i])
model.addCons(target[i] - actual[i] <= dev[i])
penalty_cost = penalty_weight * quicksum(dev[i] for i in I)
Route Arcs
START = "depot_start"
END = "depot_end"
nodes_from = [START, *locations]
nodes_to = [*locations, END]
arcs = [
(i, j)
for i in nodes_from
for j in nodes_to
if i != j and not (i == START and j == END)
]
x = {
(k, i, j): model.addVar(vtype="B", name=f"x_{k}_{i}_{j}")
for k in vehicles
for i, j in arcs
}
for k in vehicles:
model.addCons(quicksum(x[k, START, j] for j in locations) == 1)
model.addCons(quicksum(x[k, i, END] for i in locations) == 1)
for i in locations:
incoming = quicksum(x[k, j, i] for j in nodes_from if (j, i) in arcs)
outgoing = quicksum(x[k, i, j] for j in nodes_to if (i, j) in arcs)
model.addCons(incoming == outgoing)
model.addCons(outgoing <= 1)
Degree and continuity constraints alone can permit disconnected cycles. Add subtour elimination for routing models.
MTZ Subtour Elimination
order = {
(k, i): model.addVar(lb=1, ub=max(1, len(locations)), name=f"order_{k}_{i}")
for k in vehicles
for i in locations
}
n = len(locations)
for k in vehicles:
for i in locations:
for j in locations:
if i != j:
model.addCons(order[k, i] - order[k, j] + n * x[k, i, j] <= n - 1)
Reproducibility
Fix SCIP randomization and thread settings when repeatability matters.
def set_if_available(model, name, value):
try:
model.setParam(name, value)
except Exception:
pass
for name in [
"randomization/randomseedshift",
"randomization/permutationseed",
"randomization/lpseed",
]:
set_if_available(model, name, 0)
for name in ["randomization/permutevars", "randomization/permuteconss"]:
set_if_available(model, name, False)
set_if_available(model, "parallel/maxnthreads", 1)
Extraction And Validation
After solving, reconstruct the answer from variable values and validate it outside SCIP.
def is_selected(var):
return model.getVal(var) > 0.5
selected_arcs = [(i, j) for i, j in arcs if is_selected(x[vehicle, i, j])]
reported_cost = sum(distance[i, j] for i, j in selected_arcs)
if abs(reported_cost - expected_cost) > 1e-6:
raise AssertionError("reported objective component does not match reconstruction")
Treat SCIP feasibility as necessary but not sufficient. The final reported file still needs independent checks for schema, route reconstruction, capacity, inventory, penalties, and objective arithmetic.
Common Pitfalls
- Accepting a time-limited incumbent without checking
getStatus(), best bound, and the implied optimality gap when the evaluator expects an optimal (or near-optimal) objective. - Missing or ambiguous semantics that change the feasible set (e.g., optional vs required resources, or unanchored initial/end loads in a conservation model).
- Using loose Big‑M bounds, which can slow SCIP and lead to weak incumbents.
04 同仓库更多 Skills
video-frame-extraction
Extract frames from video files and save them as images using OpenCV
openai-vision
Analyze images and multi-frame sequences using OpenAI GPT vision models
image-ocr
Extract text content from images using Tesseract OCR via Python, including structured field extraction from receipts and forms
video-frame-extraction
Extract frames from video files and save them as images using OpenCV
openai-vision
Analyze images and multi-frame sequences using OpenAI GPT vision models
image-ocr
Extract text content from images using Tesseract OCR via Python, including structured field extraction from receipts and forms