Blog
About

21
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Analysis of Sparse Cutting-planes for Sparse MILPs with Applications to Stochastic MILPs

      Preprint

      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          In this paper, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. Given a MILP instance of one of these three types, assume that we decide on the support of cutting-planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. Call the optimal objective function value of the linear programming relaxation together with these cuts as \(z^{cut}\). We present bounds on the ratio of \(z^{cut}\) and the optimal objective function value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of scenario-specific cuts for two stage stochastic MILPs.

          Related collections

          Most cited references 10

          • Record: found
          • Abstract: not found
          • Article: not found

          Solving Large-Scale Zero-One Linear Programming Problems

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Cutting planes in integer and mixed integer programming

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Cutting Planes for Multistage Stochastic Integer Programs

                Bookmark

                Author and article information

                Journal
                2016-01-02
                Article
                1601.00198

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                math.OC

                Numerical methods

                Comments

                Comment on this article