Gomory cutting-plane method for integer linear programs

R arm of morie.fn.cuttip: maximise \(c'x\) subject to \(Ax \le b\), \(x \ge 0\), the variables in integer_indices (0-based, all by default) integer. The relaxation is solved by the primal simplex method from the slack basis (\(b \ge 0\) required); while an integer variable is fractional, the Gomory mixed-integer cut of the most fractional row is appended and the dual simplex method re-optimises. Slacks count as integer when every variable is integer and the data are integer. Decisions use a 1e-9 tolerance, as the Python arm.

Usage

Cuttip(c, A, b, integer_indices = NULL, max_cuts = 200, max_iter = 5000)

Arguments

c

Objective coefficients (maximised).

A

Constraint matrix.

b

Right-hand sides, non-negative.

integer_indices

0-based integer variables (default all).

max_cuts

Cut limit.

max_iter

Pivot limit per simplex call.

Value

List with x, objective, lp_bound, n_cuts, status.

References

Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society 64, 275-278.

Gomory, R. E. (1960). An algorithm for the mixed integer problem. RAND report RM-2597.

Nemhauser, G. L. and Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley.

Examples

Cuttip(c(1, 1), rbind(c(-2, 2), c(8, 10)), c(1, 13))$x
#> [1] 1 0