Effective computational methods are important for practitioners and researchers working in strategic underground mine planning. We consider a class of problems that can be modeled as a resource-constrained project scheduling problem with optional activities; the objective maximizes net present value. We provide a computational review of math programming and constraint programming techniques for this problem, describe and implement novel problem-size reductions, and introduce an aggregated linear program that guides a list scheduling algorithm running over unaggregated instances. Practical, large-scale planning problems cannot be processed using standard optimization approaches. However, our strategies allow us to solve them to within about 5% of optimality in several hours, even for the most difficult instances. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms—Discrete. Funding: This work was supported by Alford Mining Systems, the Centro de Modelamiento Matemático [Grants ACE210010 and FB21005], ANID-Chile [BASAL funds for center of excellence and FONDEF Grant ID19-10164], and the supercomputing infrastructure of the NLHPC [Grant ECM-02].

Two-step mixed integer rounding (MIR) inequalities are valid inequalities derived from a facet of a simple mixed integer set with three variables and one constraint. In this paper we investigate how to effectively use these inequalities as cutting planes for general mixed integer problems. We study the separation problem for single-constraint sets and show that it can be solved in polynomial time when the resulting inequality is required to be sufficiently different from the associated MIR inequalities. We discuss computational issues and present numerical results based on a number of data sets.

We describe a simple process for generating numerically safe cutting planes using floating-point arithmetic and the mixed-integer rounding procedure. Applying this method to the rows of the simplex tableau permits the generation of Gomory mixed-integer cuts that are guaranteed to be satisfied by all feasible solutions to a mixed-integer programming problem (MIP). We report on tests with the MIPLIB 3.0 and MIPLIB 2003 test collections as well as with MIP instances derived from the TSPLIB traveling salesman library.

We describe methods for implementing separation algorithms for domino-parity inequalities for the symmetric traveling salesman problem. These inequalities were introduced by Letchford (2000), who showed that the separation problem can be solved in polynomial time when the support graph of the LP solution is planar. In our study we deal with the problem of how to use this algorithm in the general (nonplanar) case, continuing the work of Boyd et al. (2001). Our implementation includes pruning methods to restrict the search for dominoes, a parallelization of the main domino-building step, heuristics to obtain planar-support graphs, a safe-shrinking routine, a random-walk heuristic to extract additional violated constraints, and a tightening procedure to modify existing inequalities as the LP solution changes. We report computational results showing the strength of the new routines, including the optimal solution of a 33,810-city instance from the TSPLIB.