Natashia Boland

Scenario Set Partition Dual Bounds for Multistage Stochastic Programming: A Hierarchy of Bounds and a Partition Sampling Approach

  • Ilke Bakir
  • Natashia Boland
  • Brian Dandurand
  • Alan L. Erera
    • Categories Stochastic Programming Tags

    We consider multistage stochastic programming problems in which the random parameters have finite support, leading to optimization over a finite scenario set. We propose a hierarchy of bounds based on partitions of the scenario set into subsets of (nearly) equal cardinality. These expected partition (EP) bounds coincide with EGSO bounds provided by Sandikci et al. … Read more

    A polynomially solvable case of the pooling problem

  • Natashia Boland
  • Thomas Kalinowski
  • Fabian Rigterink
    • Categories Constrained Nonlinear Optimization

    Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border … Read more

    Dominance in Pricing Problems with Stochasticity

  • Natashia Boland
  • Martin Savelsbergh
  • Karen Smilowitz
  • Sophie Dickson
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    Sequencing activities over time is a fundamental optimization problem. The problem can be modeled using a directed network in which activities are represented by nodes and pairs of activities that can be performed consecutively are represented by arcs. A sequence of activities then corresponds to a path in the directed network, and an optimal sequence … Read more

    Discrete flow pooling problems in coal supply chains

  • Natashia Boland
  • Thomas Kalinowski
  • Fabian Rigterink
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Global Optimization Applications

    The pooling problem is a nonconvex nonlinear programming problem (NLP) with applications in the refining and petrochemical industries, but also the coal mining industry. The problem can be stated as follows: given a set of raw material suppliers (inputs) and qualities of the supplies, find a cost-minimising way of blending these raw materials in intermediate … Read more

    A special case of the generalized pooling problem arising in the mining industry

  • Natashia Boland
  • Thomas Kalinowski
  • Fabian Rigterink
  • Martin Savelsbergh
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications

    Iron ore and coal are substantial contributors to Australia’s export economy. Both are blended products that are made-to-order according to customers’ desired product qualities. Mining companies have a great interest in meeting these target qualities since deviations generally result in contractually agreed penalties. This paper studies a variation of the generalized pooling problem (GPP) arising … Read more

    New multi-commodity flow formulations for the pooling problem

  • Natashia Boland
  • Thomas Kalinowski
  • Fabian Rigterink
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications

    The pooling problem is a nonconvex nonlinear programming problem with numerous applications. The nonlinearities of the problem arise from bilinear constraints that capture the blending of raw materials. Bilinear constraints are well-studied and significant progress has been made in solving large instances of the pooling problem to global optimality. This is due in no small … Read more

    A New Method for Optimizing a Linear Function over the Efficient Set of a Multiobjective Integer Program

  • Natashia Boland
  • Hadi Charkhgard
  • Martin Savelsbergh
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , , ,

    We present a new algorithm for optimizing a linear function over the set of efficient solutions of a multiobjective integer program MOIP. The algorithm’s success relies on the efficiency of a new algorithm for enumerating the nondominated points of a MOIP, which is the result of employing a novel criterion space decomposition scheme which (1) … Read more

    The Continuous Time Service Network Design Problem

  • Natashia Boland
  • Mike Hewitt
  • Luke Marshall
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , ,

    Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost-effective, the carrier must consolidate shipments, which requires coordinating their paths in both space and time, i.e., the carrier must solve a Service Network Design problem. Most service network design models rely on discretization of time, i.e., instead of determining the exact … Read more

    A Trust Region Method for the Solution of the Surrogate Dual in Integer Programming

  • Natashia Boland
  • Andrew C. Eberhard
  • Angelos Tsoukalas
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Nonsmooth Optimization Tags , ,

    We propose an algorithm for solving the surrogate dual of a mixed integer program. The algorithm uses a trust region method based on a piecewise affine model of the dual surrogate value function. A new and much more flexible way of updating bounds on the surrogate dual’s value is proposed, which numerical experiments prove to … Read more

    A big bucket time indexed formulation for nonpreemptive single machine scheduling problems

  • Natashia Boland
  • Hamish Waterer
  • Riley Clement
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , ,

    A big bucket time indexed mixed integer linear programming formulation for nonpreemptive single machine scheduling problems is presented in which the length of each period can be as large as the processing time of the shortest job. The model generalises the classical time indexed model to one in which at most two jobs can be … Read more