Dongjian Shi

A Penalized Quadratic Convex Reformulation Method for Random Quadratic Unconstrained Binary Optimization

  • Karthik Natarajan
  • Kim-Chuan Toh
  • Dongjian Shi
    • Categories 0-1 Programming, Stochastic Approaches Tags , ,

    The Quadratic Convex Reformulation (QCR) method is used to solve quadratic unconstrained binary optimization problems. In this method, the semidefinite relaxation is used to reformulate it to a convex binary quadratic program which is solved using mixed integer quadratic programming solvers. We extend this method to random quadratic unconstrained binary optimization problems. We develop a … Read more

    A Probabilistic Model for Minmax Regret in Combinatorial Optimization

  • Karthik Natarajan
  • Kim-Chuan Toh
  • Dongjian Shi
    • Categories Combinatorial Optimization

    In this paper, we propose a probabilistic model for minimizing the anticipated regret in combinatorial optimization problems with distributional uncertainty in the objective coefficients. The interval uncertainty representation of data is supplemented with information on the marginal distributions. As a decision criterion, we minimize the worst-case conditional value-at-risk of regret. The proposed model includes the … Read more