solvers

func CalcScLb ¶

func CalcScLb(aC cCSMatrix, costs []float64) (float64, error)

Calculate a lower bound for the (non-exact) set covering problem instance specified by the binary matrix aC where element aC_{ij} = 1 iff element i is in subset j.

This is done using a subgradient algorithm on the Lagrangian Dual of the ILP (Integer Linear Programming) formulation of the set covering problem.

func MakeInstance ¶

func MakeInstance(m int, subsets [][]int, costs []float64) (instance, error)

Make an Instance and check the constraints that an Instance should satisfy.

func SolveByBranchAndBound ¶

func SolveByBranchAndBound(ins cover.Instance) (cover.SubsetsEval, error)

SolveByBranchAndBound exposes an internal method without the suffix `Internal“ and takes and returns exported types.

func SolveByBranchAndBoundInternal ¶

func SolveByBranchAndBoundInternal(ins instance) (subsetsEval, error)

WIP

func SolveByBruteForce ¶

func SolveByBruteForce(ins cover.Instance) (cover.SubsetsEval, error)

SolveByBruteForce exposes an internal method without the suffix `Internal“ and takes and returns exported types.

func SolveByBruteForceInternal ¶

func SolveByBruteForceInternal(ins instance) (subsetsEval, error)

SolveByBruteForceInternal attempts finds a minimum cost exact cover for an instance by evaluating all possible selections of the subsets.

If a minimum cost exact cover exists, the returned subsetsEval will contain indices to this cover and its exactlyCovered flag will be true. Otherwise, the zero value of subsetEval will be returned.