Danial Davarnia

A graphical framework for global optimization of mixed-integer nonlinear programs

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications, Global Optimization Theory Tags , , , , ,

    While mixed-integer linear programming and convex programming solvers have advanced significantly over the past several decades, solution technologies for general mixed-integer nonlinear programs (MINLPs) have yet to reach the same level of maturity. Various problem structures across different application domains remain challenging to model and solve using modern global solvers, primarily due to the lack … Read more

    Solving Unsplittable Network Flow Problems with Decision Diagrams

  • Hosseinali Salemi
  • Danial Davarnia
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Transportation Tags , , ,

    In unsplittable network flow problems, certain nodes must satisfy a combinatorial requirement that the incoming arc flows cannot be split or merged when routed through outgoing arcs. This so-called “no-split no-merge” requirement arises in unit train scheduling where train consists should remain intact at stations that lack necessary equipment and manpower to attach/detach them. Solving … Read more

    Solving a Class of Cut-Generating Linear Programs via Machine Learning

  • Danial Davarnia
  • Atefeh Rajabalizadeh
    • Categories Branch and Cut Algorithms, Data-Mining, Linear Programming Tags , , , ,

    Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. When incorporated inside branch-and-bound, the cutting planes obtained from CGLPs help to tighten relaxations and improve dual bounds. However, running the CGLPs at the nodes of the branch-and-bound tree is computationally cumbersome … Read more

    On the Structure of Decision Diagram-Representable Mixed Integer Programs with Application to Unit Commitment

  • Hosseinali Salemi
  • Danial Davarnia
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Energy Tags , , ,

    Over the past decade, decision diagrams (DDs) have been used to model and solve integer programming and combinatorial optimization problems. Despite successful performance of DDs in solving various discrete optimization problems, their extension to model mixed integer programs (MIPs) such as those appearing in energy applications has been lacking. More broadly, the question on which … Read more

    Strong Relaxations for Continuous Nonlinear Programs Based on Decision Diagrams

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization

    Over the past decade, Decision Diagrams (DDs) have risen as a powerful modeling tool to solve discrete optimization problems. The extension of this emerging concept to continuous problems, however, has remained a challenge, posing a limitation on its applicability scope. In this paper, we introduce a novel framework that utilizes DDs to model continuous programs. … Read more

    Achieving Consistency with Cutting Planes

  • Danial Davarnia
  • Atefeh Rajabalizadeh
  • John Hooker
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , , , ,

    Cutting planes accelerate branch-and-bound search primarily by cutting off fractional solutions of the linear programming (LP) relaxation, resulting in tighter bounds for pruning the search tree. Yet cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching. A partial assignment is inconsistent with a constraint set when … Read more

    Consistency for 0-1 programming

  • Danial Davarnia
  • John Hooker
    • Categories Cutting Plane Approaches, Integer Programming

    Concepts of consistency have long played a key role in constraint programming but never developed in integer programming (IP). Consistency nonetheless plays a role in IP as well. For example, cutting planes can reduce backtracking by achieving various forms of consistency as well as by tightening the linear programming (LP) relaxation. We introduce a type … Read more

    Outer Approximation for Integer Nonlinear Programs via Decision Diagrams

  • Danial Davarnia
  • Willem-Jan van Hoeve
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Dynamic Programming Tags , , , ,

    As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems based on their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by studying IP techniques that can be … Read more

    Network Models with Unsplittable Node Flows with Application to Unit Train Scheduling

  • Danial Davarnia
  • Jean-Philippe P. Richard
  • Ece Icyuz-Ay
  • Bijan Taslimi
    • Categories Cutting Plane Approaches, Network Optimization, Transportation

    We study network models where flows cannot be split or merged when passing through certain nodes, i.e., for such nodes, each incoming arc flow must be matched to an outgoing arc flow of identical value. This requirement, which we call “no-split no-merge” (NSNM), appears in railroad applications where train compositions can only be modified at … Read more

    Computational Aspects of Bayesian Solution Estimators in Stochastic Optimization

  • Gérard Cornuéjols
  • Danial Davarnia
  • Burak Kocuk
    • Categories Statistics, Stochastic Approaches, Stochastic Programming Tags , , , ,

    We study a class of stochastic programs where some of the elements in the objective function are random, and their probability distribution has unknown parameters. The goal is to find a good estimate for the optimal solution of the stochastic program using data sampled from the distribution of the random elements. We investigate two common … Read more