OSCLIB 1.0

E. Balas and A. Saxena, "Optimizing over the Split Closure", Math. Prog. Ser. A (to appear).

This was accomplished by repeatedly solving the following separation problem: given a fractional point, say x, find a rank-1 split cut violated by x or show that none exists. We showed that this separation problem can be formulated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective function and the right hand side. We developed an algorithmic framework to deal with the resulting PMILP by creating and maintaining a dynamically updated grid of parameter values, and used the corresponding mixed integer programs to generate rank 1 split cuts. Our approach was implemented in the COIN-OR framework using CPLEX 9.0 as a general purpose MIP solver. We ran our code on more than 500 Mixed Integer Programming instances and a summary of the computational results can be obtained from the above paper

OSCLIB is a database of split disjunctions and rank 1 split cuts generated during the course of this experiment which extended over a period of more than eight months. We conducted our experiment on a wide variety of problem instances derived from the literature. For each instance, we ran our code with a time-limit of 2-4 days (see paper for details) and stored the following information.

• Osc (Split Cuts Information)
  1. Osc Formulation: The master program at the last iteration containing only the binding cuts.
  2. Unstrengthened Disjunctions: A list of split disjunctions which give rise to the cuts saved in the Osc Formulation. A precise correspondence between the disjunctions and cuts is maintained by storing the disjunctions in the same order as the cuts they give rise to.
  3. Strengthened Disjunctions: Similar to unstrengthened disjunctions except that the strengthened split disjunctions obtained by the Balas-Jeroslow procedure are stored instead.
• Experimental Data
  1. LP Relaxation Value (Round): The value of the LP relaxation at the beginning of each round of the master program.
  2. LP Relaxation Value (Time): Same as LP Relaxation Value (Round) except that the evolution of LP relaxation w.r.t time is recorded.
  3. Number of Cuts (Round): The number of cuts which were added to the master program in each round of the algorithm.
  4. Fractional Space Information (Round): For each round, we recorded the number of rows, number of columns and non-zeroes in the coefficient matrix of the fractional subspace. This information is useful since the PMILP (and subsequent CGLPs) are generated in the fractional subspace.

At the end of the experiment, we collected the following information for each problem instance.

• Relaxations & Duality Gap: The LP optimum, the IP optimum and the optimum over the split closure (estimated by the LP relaxation value of the final master program). Percentage Duality Gap was calculated from these optimum values, and its average over all instances in each problem class was computed.
• Advanced Analysis:
  1. Cuts' Information The number of cuts which were binding at the final master problem. Note that the binding cuts provide a compact certificate of the gap closed. We also calculated the average number of distinct cut coefficients in the final set of binding cuts. Most combinatorial cuts (such as comb inequalities, clique inequalities, odd cycle inequalities etc) have very few distinct coefficients, a feature which is typically not shared by general purpose cutting planes such as Mixed Integer Gomory Cuts or Lift-and-Project cuts. Consequently, the number of distinct cut coefficients gives a metric to gauge the combinatorial nature of these cuts.
  2. Disjunctions' Information We calculated the average number of distinct coefficients in the support vector of the split disjunctions which gave rise to cuts binding at the final master problem. The average magnitude of the support coefficient, the average ratio of the maximum and minimum (non-zero) coefficient magnitude and the average support size of the disjunction was also recorded. Surprisingly, problem instances across several classes of problems have very small values (typically less than 10) of these parameters. In order to gain a better understanding of the split closure, we also computed a classification of these disjunctions into the following nested categories.
     1. Single Support disjunctions with unit coefficients. These are disjunctions of the form x_j<=t or x_j>=t+1 for integral t.
     2. Split Disjunctions whose support coefficients are all equal to 1.
     3. Split Disjunctions whose support coefficients are derived from {-1,1}.
• Advanced Analysis of LP Values For each instance, we studied the impact of keeping only those cuts in the final master program which were derived from disjunctions belonging to a specific class of split disjunctions, described above. The objective of this experiment was to assess the extent to which split closure can be approximated by split cuts derived from split disjunctions with coefficients in {0,1,-1}. To our surprise, we found that restricting the use of cuts to unstrengthened cuts from disjunctions with coefficients equal to 0, 1 or -1 for many problem classes (especially structured ones) does not affect substantially the gap closed (see Table 16 of the paper).

A. Saxena (anureet "at" cmu.edu)

Last Updated on November 18th, 2006