Opened 19 months ago

Last modified 3 months ago

#31744 new enhancement

ManifoldSubset: Propagate emptiness/nonemptiness using LP

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-9.8
Component: manifolds Keywords:
Cc: Eric Gourgoulhon, Michael Jung, Travis Scrimshaw, Yuan Zhou Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges


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.

Change History (4)

comment:1 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:2 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:3 Changed 9 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:4 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.