discrete

package

v0.0.0-...-d54ec2c Latest Latest Go to latest Published: Jan 14, 2026 License: MIT Imports: 10 Imported by: 0

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

github.com/roidaradal/opt

Links

Open Source Insights

Documentation ¶

Overview ¶

Package discrete contains the common parts to discrete optimization problems

Index ¶

type BaseConstraint
- func (c BaseConstraint) ComputePenalty(solution *Solution) Penalty
- func (c BaseConstraint) IsSatisfied(solution *Solution) bool
type Constraint
type ConstraintFn
type GlobalConstraint
type Goal
type ObjectiveFn
type Penalty
type Problem
- func NewProblem(name string) *Problem
- func (p *Problem) AddConstraint(constraint Constraint)
- func (p *Problem) AddGlobalConstraint(test ConstraintFn, penalty Penalty, variables ...Variable)
- func (p *Problem) AddUniversalConstraint(test ConstraintFn)
- func (p Problem) ComputeScore(solution *Solution)
- func (p Problem) IsOptimization() bool
- func (p Problem) IsSatisfaction() bool
- func (p Problem) IsSatisfied(solution *Solution) bool
- func (p Problem) SolutionSpace() int
- func (p Problem) SolutionSpaceEquation() string
type ProblemType
type Score
type Solution
- func NewSolution() *Solution
- func ZipSolution(variables []Variable, values []Value) *Solution
- func (s *Solution) Assign(variable Variable, value Value)
- func (s Solution) Length() int
- func (s Solution) Tuple(p *Problem) []Value
- func (s Solution) Values() []Value
type SolutionCoreFn
type SolutionStringFn
type Value
- func BooleanDomain() []Value
- func IndexDomain(numItems int) []Value
- func MapDomain[T any](items []T) []Value
- func PathDomain(numItems int) []Value
- func RangeDomain(first, last int) []Value
type Variable
- func IndexVariables(numItems int) []Variable
- func RangeVariables(first, last int) []Variable
- func Variables[T any](items []T) []Variable

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

Types ¶

type BaseConstraint ¶

type BaseConstraint struct {
	Penalty
	Variables []Variable
	Test      ConstraintFn
}

The base Constraint type

func (BaseConstraint) ComputePenalty ¶

func (c BaseConstraint) ComputePenalty(solution *Solution) Penalty

Computes the penalty for the given solution

func (BaseConstraint) IsSatisfied ¶

func (c BaseConstraint) IsSatisfied(solution *Solution) bool

Checks if solution satisfies the constraint test

type Constraint ¶

type Constraint interface {
	IsSatisfied(*Solution) bool
	ComputePenalty(*Solution) Penalty
}

type ConstraintFn ¶

type ConstraintFn func(*Solution) bool

type GlobalConstraint ¶

type GlobalConstraint struct {
	BaseConstraint
}

Constraint with more than 2 variables

type Goal ¶

type Goal string

const (
	Maximize Goal = "max"
	Minimize Goal = "min"
	Satisfy  Goal = "sat"
)

type ObjectiveFn ¶

type ObjectiveFn func(*Solution) Score

type Penalty ¶

type Penalty = float64

var HardPenalty Penalty = math.Inf(1)

type Problem ¶

type Problem struct {
	Name        string
	Type        ProblemType
	Variables   []Variable
	Domain      map[Variable][]Value
	Constraints []Constraint
	Goal
	ObjectiveFn
	SolutionCoreFn
	SolutionStringFn
}

func NewProblem ¶

func NewProblem(name string) *Problem

Create new Problem

func (*Problem) AddConstraint ¶

func (p *Problem) AddConstraint(constraint Constraint)

Add new constraint to problem

func (*Problem) AddGlobalConstraint ¶

func (p *Problem) AddGlobalConstraint(test ConstraintFn, penalty Penalty, variables ...Variable)

Add Global constraint to problem, with given penalty and variables

func (*Problem) AddUniversalConstraint ¶

func (p *Problem) AddUniversalConstraint(test ConstraintFn)

Add Universal constraint to problem (all problem variables are involved)

func (Problem) ComputeScore ¶

func (p Problem) ComputeScore(solution *Solution)

Computes and attaches solution score by calling the ObjectiveFn

func (Problem) IsOptimization ¶

func (p Problem) IsOptimization() bool

Check if optimization problem

func (Problem) IsSatisfaction ¶

func (p Problem) IsSatisfaction() bool

Check if satisfaction problem

func (Problem) IsSatisfied ¶

func (p Problem) IsSatisfied(solution *Solution) bool

Check if solution satisfies the problem constraints

func (Problem) SolutionSpace ¶

func (p Problem) SolutionSpace() int

Compute the total solution space of the problem

func (Problem) SolutionSpaceEquation ¶

func (p Problem) SolutionSpaceEquation() string

Create the solution space equation of the problem

type ProblemType ¶

type ProblemType string

const (
	Assignment ProblemType = "assignment"
	Partition  ProblemType = "partition"
	Sequence   ProblemType = "sequence"
	Subset     ProblemType = "subset"
	Path       ProblemType = "path"
)

type Score ¶

type Score = float64

type Solution ¶

type Solution struct {
	Score
	Map           map[Variable]Value
	VariableOrder []Variable
	IsPartial     bool
}

func NewSolution ¶

func NewSolution() *Solution

Create new blank solution

func ZipSolution ¶

func ZipSolution(variables []Variable, values []Value) *Solution

Create new solution by zipping variables, values

func (*Solution) Assign ¶

func (s *Solution) Assign(variable Variable, value Value)

Assign variable=value in solution

func (Solution) Length ¶

func (s Solution) Length() int

Get solution length

func (Solution) Tuple ¶

func (s Solution) Tuple(p *Problem) []Value

Get values of solution, ordered by problem variable order

func (Solution) Values ¶

func (s Solution) Values() []Value

Get values of solution in arbitrary order

type SolutionCoreFn ¶

type SolutionCoreFn func(*Solution) string

type SolutionStringFn ¶

type SolutionStringFn func(*Solution) string

type Value ¶

type Value = int

func BooleanDomain ¶

func BooleanDomain() []Value

Creates a Boolean domain {1, 0}

func IndexDomain ¶

func IndexDomain(numItems int) []Value

Creates a list of values from [0, numItems)

func MapDomain ¶

func MapDomain[T any](items []T) []Value

Creates a list of values, mirroring the list of items

func PathDomain ¶

func PathDomain(numItems int) []Value

Creates a list of values from [-1, 0, numItems)

func RangeDomain ¶

func RangeDomain(first, last int) []Value

Creates a list of values from [first, last]

type Variable ¶

type Variable = int

func IndexVariables ¶

func IndexVariables(numItems int) []Variable

Create list of variables from [0, numItems)

func RangeVariables ¶

func RangeVariables(first, last int) []Variable

Create list of variables from [first, last]

func Variables ¶

func Variables[T any](items []T) []Variable

Create list of variables, mirroring the list of items

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL