Skip to content

ManifoldSubset: Propagate emptiness/nonemptiness using LP #31744

@mkoeppe

Description

@mkoeppe

Introduce a binary variable z_S for each subset S, z_S = 1 if nonempty, z_S = 0 if empty. Fix a variable z_S to this value if emptiness/nonemptiness of the set S is known.

If A is a subset of B, write a constraint z_A <= z_B.

If [A, B] is an open cover of C, write a constraint z_C <= z_A + z_B or z_C <= z_A + z_B - z_A_inter_B.

Then solving a linear or integer linear optimization problem maximizing/minimizing variables z_S can prove that S has to be empty or nonempty.

CC: @egourgoulhon @mjungmath @tscrim @yuan-zhou

Component: manifolds

Issue created by migration from https://trac.sagemath.org/ticket/31744

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions