LinearAutarkies.hpp File Reference

Plans for Maxima-components regarding linear autarkies. More...

Go to the source code of this file.

Detailed Description

Plans for Maxima-components regarding linear autarkies.

Finding linear autarkies
  • DONE (predicate laut_paocs_p) Given the clause-variable matrix M, non-trival linear autarkies are given as non-trivial solutions of M x >= 0.
  • DONE (helper functions are provided by us) From what Maxima provides, apparently only maximize_lp (in package "simplex") is of use.
  • DONE (find_linearautarky_ocs) One possibility to achieve complete search for linear autarkies is to consider one after another the additional constraints x_i >= 1 and x_i <= -1.
  • An alternative is to first consider balanced linear autarkies (by linear equations, i.e., M x = 0), and then solving all M x = e_i for the possible e_i.
  • In both cases the objective function would be constant zero.
  • The above methods just search for feasible solutions. How can we use the optimisation facilities? Apparently only heuristical usage is possible?
    1. For example maximising the sum of all x_i.
    2. If this only yields 0, then one can attempt minimising the sum of the x_i.
    3. What can be said in the remaining case? All solutions fulfill sum x_i = 0; is this possible if we also know that no balanced autarkies (non-trivial solutions of M x = 0) exist?
  • Finally we need a dedicated approach.
    1. M has a non-trival linear autarky iff the polyhedron M x >= 0 is unbounded, and a non-trivial linear autarky corresponds to an infinite ray contained in the polyhedron. Can this be better exploited?

Definition in file LinearAutarkies.hpp.