Opened 6 months ago

Last modified 3 months ago

#31744 new enhancement

ManifoldSubset: Propagate emptiness/nonemptiness using LP

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.5
Component: manifolds Keywords:
Cc: egourgoulhon, gh-mjungmath, tscrim, yzh Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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 (1)

comment:1 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.