Yongjia Song

Markov Chain-based Policies for Multi-stage Stochastic Integer Linear Programming with an Application to Disaster Relief Logistics

  • Margarita P Castro
  • Merve Bodur
  • Yongjia Song
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We introduce an aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We demonstrate that the aggregated MSILP can be … Read more

    An Adaptive Sequential Sample Average Approximation Framework for Solving Two-stage Stochastic Programs

  • Raghu Pasupathy
  • Yongjia Song
    • Categories Stochastic Programming Tags , ,

    We present adaptive sequential SAA (sample average approximation) algorithms to solve large-scale two-stage stochastic linear programs. The iterative algorithm framework we propose is organized into \emph{outer} and \emph{inner} iterations as follows: during each outer iteration, a sample-path problem is implicitly generated using a sample of observations or “scenarios,” and solved only \emph{imprecisely}, to within a … Read more

    Branch-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs

  • Qie He
  • Yongjia Song
  • Stefan Irnich
    • Categories Transportation Tags , , , ,

    Two critical yet frequently conflicting objectives for logistics and transportation service companies are improving customer satisfaction and reducing transportation cost. In particular, given a net- work of customer requests with preferred service times, it is very challenging to find vehicle routes and service schedules simultaneously that respect all operating constraints and minimize the total transportation … Read more

    On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems

  • Welington de Oliveira
  • Yongjia Song
  • Wim van Ackooij
    • Categories Nonsmooth Optimization, Stochastic Programming Tags , , ,

    We consider well-known decomposition techniques for multistage stochastic programming and a new scheme based on normal solutions for stabilizing iterates during the solution process. The given algorithms combine ideas from finite perturbation of convex programs and level bundle methods to regularize the so-called forward step of these decomposition methods. Numerical experiments on a hydrothermal scheduling … Read more

    Vehicle Routing Problems with Time Windows and Convex Node Costs

  • Qie He
  • Yongjia Song
    • Categories Integer Programming, Transportation Tags , , ,

    We consider a variant of the vehicle routing problems with time windows, where the objective includes the inconvenience cost modeled by a convex function on each node. We formulate this mixed integer convex program using a novel set partitioning formulation, by considering all combinations of routes and block structures over the routes. We apply a … Read more

    An Adaptive Partition-based Level Decomposition for Solving Two-stage Stochastic Programs with Fixed Recourse

  • Welington de Oliveira
  • Yongjia Song
  • Wim van Ackooij
    • Categories Stochastic Programming

    We present a computational study of several strategies to solve two-stage stochastic linear programs by integrating the adaptive partition-based approach with level decomposition. A partition-based formulation is a relaxation of the original stochastic program, obtained by aggregating variables and constraints according to a scenario partition. Partition refinements are guided by the optimal second-stage dual vectors … Read more

    A joint routing and speed optimization problem

  • Ricardo Fukasawa
  • Qie He
  • Fernando Santos
  • Yongjia Song
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Transportation

    Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and … Read more

    Risk Averse Shortest Path Interdiction

  • Siqian Shen
  • Yongjia Song
    • Categories 0-1 Programming, Network Optimization, Stochastic Programming

    We consider a Stackelberg game in a network, where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer … Read more

    A disjunctive convex programming approach to the pollution routing problem

  • Ricardo Fukasawa
  • Qie He
  • Yongjia Song
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Transportation Tags , , ,

    The pollution routing problem (PRP) aims to determine a set of routes and speed over each leg of the routes simultaneously to minimize the total operational and environmental costs. A common approach to solve the PRP exactly is through speed discretization, i.e., assuming that speed over each arc is chosen from a prescribed set of … Read more

    An Adaptive Partition-based Approach for Solving Two-stage Stochastic Programs with Fixed Recourse

  • James R. Luedtke
  • Yongjia Song
    • Categories Stochastic Programming Tags , ,

    We study an adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse. A partition-based formulation is a relaxation of the original stochastic program, and we study a finitely converging algorithm in which the partition is adaptively adjusted until it yields an optimal solution. A solution guided refinement strategy is developed to refine the … Read more