Titlebook: Integer Programming and Combinatorial Optimization; 12th International I Matteo Fischetti,David P. Williamson Conference proceedings 2007 S

Ballad

Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)/2-approximation [9] for this problem. It is also known, via a reduction from the max-.-cover problem, that there is no (1 − 1/. + .)-approximation for any constant .> 0, unless . = . [6]. In this paper, we improve the 1/2-approximation to a (1 − 1/.)-approximation, when . is a sum of weighted rank

Crohns-disease

On a Generalization of the Master Cyclic Group Polyhedronxplicit characterization of the nontrivial facet-defining inequalities for MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory [9] and for the Master Knapsack Polyhedron by Araoz [1]. Furthermore, this characterization also gives a polynomial time algorithm

分离

半圆凿

On the Exact Separation of Mixed Integer Knapsack Cuts However, no such class has had as much practical success as the MIR inequality when used in cutting plane algorithms for general mixed integer programming problems. In this work we analyze this empirical observation by developing an algorithm which takes as input a point and a single-row mixed inte

游行

掺和

Matching Problems in Polymatroids Without Double Circuitsl, then a partition-type min-max formula characterizes the size of a maximum matching. We provide applications of this result to parity constrained orientations and to a rigidity problem..A polynomial time algorithm is constructed by generalizing the principle of shrinking blossoms used in Edmonds’ matching algorithm [2].

acrobat

A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applicationsroblem can be expressed or approximated through the single-dimensional lifting function of some of its components. We then apply our approach to two variants of classical models and show that it yields an efficient procedure to derive strong valid inequalities.

euphoria

Orbital Branchingt suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as . and significantly better than a state-of-the-art commercial solver on symmetric integer programs.

中世纪

消瘦

On the Exact Separation of Mixed Integer Knapsack Cutsntire closure of single-row systems allows us to establish natural benchmarks by which to evaluate specific classes of knapsack cuts. Using these benchmarks on Miplib 3.0 instances we analyze the performance of MIR inequalities. Computations are performed in exact arithmetic.