Natashia Boland

Simultaneous Solution of Lagrangean Dual Problems Interleaved with Preprocessing for the Weight Constrained Shortest Path Problem

  • Natashia Boland
  • Ranga Muhandiramge
    • Categories Combinatorial Optimization, Dynamic Programming, Network Optimization

    Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and … Read more

    A strengthened formulation for the open pit mine production scheduling problem

  • Natashia Boland
  • Gary Froyland
  • Christopher Fricke
    • Categories Applications - Science and Engineering Tags , ,

    We present a strengthened integer programming formulation for the open pit mine production scheduling problem, where the precedence and production constraints are combined to form 0-1 knapsack inequalities. Addition of corresponding knapsack cover inequalities decreases the computational requirements to obtain the optimal integer solution, in many cases by a significant margin. CitationThe University of Melbourne, … Read more

    Clique-based facets for the precedence constrained knapsack problem

  • Andreas Bley
  • Natashia Boland
  • Gary Froyland
  • Renata Sotirov
  • Christopher Fricke
    • Categories 0-1 Programming, Polyhedra

    We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in management and machine scheduling, and also appears as a subproblem in decomposition techniques for network design and other related problems. We present a new approach for determining facets of … Read more