Seminario: "From the input-output model to the linear extension polytope"

E' possibile visionare il seminario anche on-line: link Teams

 

Abstract:

In the input-output model of Leontief, there are a list of economic sectors and numerical values assessing the transfer of production from any sector to any other one.  How to list the sectors in order to maximize the sum of the transfers from any sector to all subsequent ones?  This is the linear ordering problem, which can often be solved by linear programming.  The set of feasible points of the program is the linear ordering polytope,  whose vertices correspond to the linear orderings of the sectors.  The same linear ordering polytope happens to be the prediction range of a probabilistic model of binary choice due to Block and Marschak (1960).  Finding a description of the polytope by affine inequalities is a difficult task.  Many families of facet defining inequalities are known, for instance some capturing the axioms for a linear ordering.  Other inequalities, rather surprisingly, come from nonorientable surfaces or from graphs which are stability critical.

Now assume that not all linear orderings are admissible (Staline might have his preferences), that is, we take into account only the linear orderings extending a partial ordering P on the alternatives.  There results the linear extension polytope of the poset P,  whose vertices correspond to the linear extensions of P.  A natural relaxation of the linear extension polytope, called the axiomatic relaxation, is the set of solutions of the affine inequalities encoding the axioms for linear extensions.  It is natural to ask when the linear extension polytope of P equals its axiomatic relaxation.  We show that this is the case precisely when P does not induce any poset from a list of 78 forbidden induced subposets.  Equivalently, the incomparability graph of P does not include 2 forbidden subgraphs;  also, when the poset P has extension dimension at most 2.

 

 

Referente DEI: Prof. Alfio Giarlotta