Oscar Meza

Solving the Prize-collecting Rural Postman Problem

  • Julian Araoz
  • Oscar Meza
  • Elena Fernandez
    • Categories Cutting Plane Approaches, Integer Programming Tags ,

    In this work we present an algorithm for solving the Prize-collecting Rural Postman Problem. This problem was recently defined and is a generalization of other arc routing problems like, for instance, the Rural Postman Problem. The main difference is that there are no required edges. Instead, there is a profit function on the edges that … Read more

    A simple exact separation algorithm for 2-matching inequalities.

  • Julian Araoz
  • Oscar Meza
  • Elena Fernandez
    • Categories Combinatorial Optimization Tags ,

    In this work we present an exact separation algorithm for the so called co-circuit inequalities, otherwise known as parity or 2-matching inequalities. The algorithm is quite simple since it operates on the tree of min-cuts of the support graph of the solution to separate, relative to an ad hoc capacity vector. The order of our … Read more