IMI/Publicaţii/CSJM/Ediţii/CSJM v.11, n.1 (31), 2003/

Supermodular Programming on Lattices

Authors: V.R. Khachaturov, Ro.V. Khachaturov, Ru.V. Khachaturov


Questions, concerning the optimization of supermodular functions on finite lattices are considered in the paper. The systematic summary of main authors' and other researchers' results known before, new authors' results are given. There should be marked out the following three results among new results.
The first - elaboration of the basic propositions of the theory of maximization of supermodular functions on Boolean lattices (they were worked out only for the problems of minimization before) and establishing of relation between global minimum and maximum of supermodular function for main types of lattices.
The second - elaboration of original combinatorial algorithms of automatized representation of hyper-cubes (booleans) of large dimension on a plane in the form of various diagrams, on which the properties of boolean as a partially ordered set of its vertexes are kept (This provides us with ample opportunities for construction of various schemes of looking through the elements of atomic lattices and for visualization of the optimization process).
The third - carrying out the basic propositions of the theory of optimization of supermodular functions to the main types of lattices: Boolean lattices, lattices with relative supplements (division lattices, lattices of vector subspaces of finite-dimensional vector space, geometrical spaces), lattices equal to Cartesian product of chains, distributive lattices, atomic lattices.
These theoretical results and availability of the great amount of optimization problems for lattices with concrete forms of supermodular functions allow to consider methods and algorithms for solving the problems of optimization of supermodular functions on lattices as a new field of mathematical programming - supermodular programming [19].

V.R.Khachaturov, R.V.Khachaturov, R.V.Khachaturov


Adobe PDF document0.81 Mb