Tools for primal degenerate linear programs: IPS, DCA, and PE

摘要: This paper describes three recent tools for dealing with primal degeneracy in linear programming. The first one is the improved simplex (IPS) algorithm which turns into a possible advantage. constraints of original problem are dynamically partitioned based on numerical values current basic variables. idea to work only those that correspond nondegenerate leads row-reduced decreases size working basis. main feature IPS it provides pivot at every iteration solution process until optimality reached. To achieve such result, negative reduced cost convex combination variables their bounds selected, if any. pricing step necessary and sufficient condition second tool dynamic constraint aggregation (DCA), constructive strategy specifically designed set partitioning constraints. It heuristically aims properties provided by methodology. We bridge similarities differences DCA models. final positive edge (PE) rule. capitalizes compatibility definition determine status column vector associated variable during computation. Within IPS, selection compatible enter basis ensures pivot, hence PE permits trade-off between strict improvement high, degenerate pivots. added value obtained without explicitly computing updated components tableau. Ultimately, we establish tight bonds these going back algebra framework from emanates so-called concept subspace