set-covering-problem

What it does

The skill presents a structured framework for solving coverage-based optimization problems. It defines several problem variants (Basic SCP, LSCP, MCLP, Partial Set Covering, Redundant Coverage) and provides the mathematical formulations, decision variables, and objective functions that an agent should implement when solving these problems. It also includes example code blocks showing how to set up and solve SCP and related variants using optimization tooling (e.g., PuLP). The focus is on determining minimum-cost coverage sets, minimizing the number of facilities for full coverage, maximizing covered demand under constraints, accommodating partial or redundant coverage, and applying these models to facility location and service coverage contexts.

Concretely, the agent is instructed to:

• Identify problem type variants (SCP, LSCP, MCLP, Partial, Redundant) and their goals.
• Use the given parameters and coverage matrices to formulate the optimization problem.
• Define decision variables (binary x_j for sets/facilities; y_i for coverage in MCLP as appropriate).
• Implement objective functions (minimize cost or number of facilities, maximize covered demand).
• Apply the same coverage constraints across variants (each element must be covered, or constrained by redundancy).
• For SCP/LSCP, construct the coverage matrix a_{ij} and enforce Σ a_{ij} x_j ≥ 1 for all elements i, or minimize Σ x_j subject to full coverage.
• Provide example setups, including code sketches for PuLP-based solutions and a downstream example outlining redundant coverage.
• Outline exact formulations for SCP, LSCP, MCLP, and Redundant Coverage, including definitions of I, J, c_j, a_{ij}, x_j, and y_i, and the corresponding constraints.
• Outline how to compute additional metrics (e.g., distances to nearest facility) in LSCP/MCLP contexts when coordinates are provided.
• Remain within the stated scope of solving coverage problems and do not overpromise outcomes.

The skill folds these elements into a cohesive guide for implementing coverage optimization solvers and applying them to facility location and service coverage problems.

How it works

The skill lays out a framework for solving multiple variants of the set covering family. It enumerates problem variants and their goals, followed by a shared mathematical formulation:

• Basic SCP: choose sets to cover all elements with minimum total cost. Variables: x_j ∈ {0,1}; Objective: Minimize Σ c_j × x_j; Constraints: Σ_{j:a_{ij}=1} x_j ≥ 1 for all i.
• LSCP: minimize the number of facilities while ensuring every demand point is within a service radius. Coverage matrix a_{ij} = 1 if d_{ij} ≤ S; Objective: Minimize Σ x_j; Constraints: same as SCP.
• MCLP: maximize weighted covered demand with a cap on facilities. Variables: x_j, y_i ∈ {0,1}; Objective: Maximize Σ w_i × y_i; Constraints: y_i ≤ Σ a_{ij} x_j; Σ x_j ≤ p; binaries.
• Redundant Coverage (k-Coverage): ensure each element is covered by at least k facilities: Σ a_{ij} x_j ≥ k for all i. Additionally, it provides exact PuLP-based code blocks for solving SCP with and without redundancy, and LSCP/MCLP problem templates, along with example workflows and outputs. The steps include constructing coverage matrices, defining costs, solving with a MILP solver, and extracting selected facilities and coverage details.

When to use it

Use when the user mentions solving set covering problems or coverage-based optimization, and related terms: set cover, minimum set cover, coverage optimization, facility coverage, service coverage, location set covering, maximal covering location problem, or covering design. It also directs when to reference related facility location problems like warehouse-location-optimization or hub-location-problem for general facility location context.

What it can touch

The skill references and uses the following tools and components in its examples:

• PuLP (Python library) for solving the optimization problems, via PuLP’s LpProblem, LpVariable, and solver invocation (PULP_CBC_CMD).
• It defines data structures for coverage matrices (binary I x J matrices) and optional coordinate arrays for distance-based coverage (numpy and linear algebra for distance calculations).
• It includes example code blocks showing how to construct and solve the problems and how to extract results (selected sets, total cost, coverage per element).

Caveats

• The skill documents complexity notes (e.g., NP-complete for SCP) and provides formulations and example implementations, but actual performance depends on input size and solver efficiency.
• It relies on exact binary coverage assumptions (a_{ij} ∈ {0,1}) and may not cover probabilistic or fuzzy coverage models.
• The provided examples assume availability of a MILP solver (e.g., CBC) via PuLP.