Search

This paper presents the properties of the minimum mean cycle-canceling algorithm for solving linear programming models. Originally designed for solving network flow problems for which it runs in strongly polynomial time, most of its properties are preserved. This is at the price of adapting the fundamental decomposition theorem of a network flow solution together with various definitions: that of a cycle and the way to calculate its cost, the residual problem, and the improvement factor at the end of a phase. We also use the primal and dual necessary and sufficient optimality conditions stated on the residual problem for establishing the pricing step giving its name to the algorithm. It turns out that the successive solutions need not be basic, there are no degenerate pivots, and the improving directions are potentially interior in addition to those on edges. For solving an m × n linear program, it requires a pseudo-polynomial number O ( n Δ ) of so-called phases, where Δ depends on the number of rows and the coefficient matrix.

In the context of large-scale linear programs solved by a column generation algorithm, we present a primal algorithm for handling the master problem. Successive approximations of the latter are created to converge to optimality. The main properties are that, for every approximation except the last one, the cost of the solution decreases whereas the sum of the variable values increases. Moreover, the minimum reduced cost of the variables also increases and converges to zero with a super-geometric growth rate.

This paper addresses the solution of the capacitated minimum cost flow problem on a network containingn nodes and m arcs. Satisfying necessary and sufficient optimality conditions can be done on the residual network although it can be quite time consuming as testified by the minimum mean cycle-canceling algorithm (MMCC). We introduce a contracted network which exploits these conditions on a much smaller network. Since the construction of this contracted network is very flexible, we study its properties depending on the construction choice. A generic contraction algorithm is then produced around the contracted network. Interestingly enough, it turns out it encapsulates both the MMCC and primal network simplex algorithms as extreme cases. By guiding the solution using a particular expansion scheme, we are able to recuperate theoretical results from MMCC. As such, we obtain a strongly polynomial Contraction-Expansion algorithm which runs in O(m3n2) time. There is thus no improvement of the runtime complexity, yet the expansion scheme sticks to very practical observations of MMCCs behavior, namely that of phases and jumps on the optimality parameter. The solution time is ultimately significantly reduced, even more so as the size of the instance increases.

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

Given a linear program? ( L P ) with m constraints and n lower and upper bounded variables, any solution x 0 to L P can be represented as a nonnegative combination of at most m + n so-called weighted paths and weighted cycles, among which at most n weighted cycles. This fundamental decomposition theorem leads us to derive, on the residual problem L P ( x 0 ) , two alternative optimality conditions for linear programming, and eventually, a class of primal algorithms that rely on an Augmenting Weighted Cycle Theorem.

Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to often suffer from degeneracy in the master problem. Inspired by recent advances in coping with degeneracy in the primal simplex method, we propose a row-reduced column generation method that may take advantage of degenerate solutions. The idea is to reduce the number of constraints to the number of strictly positive basic variables in the current master problem solution. The advantage of this row-reduction is a smaller working basis, and thus a faster re-optimization of the master problem. This comes at the expense of a more involved pricing subproblem, itself eventually solved by column generation, that needs to generate weighted subsets of variables that are said compatible with the row-reduction, if possible. Such a subset of variables gives rise to a strict improvement in the objective function value if the weighted combination of the reduced costs is negative. We thus state, as a by-product, a necessary and sufficient optimality condition for linear programming. This methodological paper generalizes the improved primal simplex and dynamic constraints aggregation methods. On highly degenerate linear programs, recent computational experiments with these two algorithms show that the row-reduction of a problem might have a large impact on the solution time. We conclude with a few algorithmic and implementation issues.