infinity: Add failing cut from p0282 to test suite

infinity/library/src/infinity-nd.c

@@ -365,10 +365,6 @@ static int create_tight_rays_lp(int nrows,
     rval = LP_relax(lp);
     abort_if(rval, "LP_relax failed");
 
-    //rval = LP_write(lp, "tight-rays.lp");
-    //abort_if(rval, "LP_write failed");
-
-
 CLEANUP:
     if(rmatind) free(rmatind);
     if(rmatval) free(rmatval);
@@ -602,7 +598,7 @@ static int find_interior_point_enum(const int nrows,
                 }
             }
 
-    if(!DOUBLE_geq(best_value, 1)) *found = 1;
+    if(best_value < 0.999) *found = 1;
 
 CLEANUP:
     if(beta2) free(beta2);
@@ -665,7 +661,7 @@ static int find_interior_point_cplex(const int nrows,
 
     log_debug("    obj = %.8lf\n", objval);
 
-    if(DOUBLE_geq(objval, 1.0))
+    if(objval > 0.999)
     {
         log_debug("  set is lattice-free\n");
         *found = 0;
@@ -1320,9 +1316,7 @@ int INFINITY_ND_generate_lfree(const struct MultiRowModel *model,
                     &epsilon_x, tx);
             abort_if(rval, "bound failed");
 
-            if(isinf(epsilon_x)) break;
-
-//            epsilon_x = (floor(epsilon_x * 128) / 128);
+            abort_if(isinf(epsilon_x), "epsilon_x is infinite");
             log_debug("    epsilon_x = %.8lf\n", epsilon_x);
 
             if(DOUBLE_eq(epsilon_x, epsilon))
@@ -1347,7 +1341,7 @@ int INFINITY_ND_generate_lfree(const struct MultiRowModel *model,
         {
             if(t[i])
             {
-                beta[i] = min(beta[i], epsilon);
+                beta[i] = min(beta[i] * 0.999, epsilon);
             }
             else if(!skip_ahull)
             {
@@ -1364,7 +1358,6 @@ int INFINITY_ND_generate_lfree(const struct MultiRowModel *model,
                     continue;
                 }
 
-//                alpha = (floor(alpha * 128) / 128);
                 beta[i] = min(beta[i], alpha);
             }
 

infinity/library/src/infinity.c

@@ -108,6 +108,7 @@ static int create_cut_from_lfree(const struct Tableau *tableau,
                                 struct Row *cut)
 {
     int rval = 0;
+    double *ray = 0;
 
     struct LP lp;
     int nvars = map->nvars;
@@ -122,40 +123,41 @@ static int create_cut_from_lfree(const struct Tableau *tableau,
     rval = INFINITY_create_psi_lp(lfree, &lp);
     abort_if(rval, "create_psi_lp failed");
 
+    ray = (double*) malloc(nrows * sizeof(double));
+    abort_if(!ray, "could not allocate ray");
+
     cut->nz = nvars;
     for(int i = 0; i < nvars; i++)
     {
-        double value;
-        const double *q = LFREE_get_ray(rays, map->variable_to_ray[i]);
+        double value, norm = 0;
+        double *original_ray = LFREE_get_ray(rays, map->variable_to_ray[i]);
         char type = tableau->column_types[map->indices[i]];
 
+        for (int j = 0; j < nrows; j++)
+        {
+            ray[j] = original_ray[j];
+            norm += fabs(ray[j]);
+        }
+
+        if (norm < 0.001)
+            for (int j = 0; j < nrows; j++)
+                ray[j] *= 0.001 / norm;
 
         if(ENABLE_LIFTING && type == MILP_INTEGER)
         {
-            rval = INFINITY_pi(nrows, q, map->ray_scale[i], &lp, &value);
+            rval = INFINITY_pi(nrows, ray, map->ray_scale[i], &lp, &value);
             abort_if(rval, "INFINITY_pi failed");
         }
         else
         {
-            rval = INFINITY_psi(nrows, q, map->ray_scale[i], &lp, &value);
+            rval = INFINITY_psi(nrows, ray, map->ray_scale[i], &lp, &value);
             abort_if(rval, "INFINITY_psi failed");
         }
 
+        value *= 1.001;
+        value = fmax(value, 0.001);
         log_verbose("   psi[%4d] = %20.12lf %d\n", map->indices[i], value);
 
-        if_debug_level
-        {
-            time_printf("    q=[");
-            for(int j = 0; j < nrows; j++)
-                printf("%25.20lf ", q[j] * map->ray_scale[i]);
-            printf("] value=%25.20lf\n", value);
-        }
-
-        value = fmax(value, 1 / 1024.0);
-
-//        value *= 1.001;
-//        value = DOUBLE_max(value, 0.001);
-
         cut->indices[i] = map->indices[i];
         cut->pi[i] = -value;
     }
@@ -163,6 +165,7 @@ static int create_cut_from_lfree(const struct Tableau *tableau,
     cut->pi_zero = -1.0;
 
 CLEANUP:
+    if(ray) free(ray);
     LP_free(&lp);
     return rval;
 }
@@ -186,12 +189,7 @@ static int filter_model(const struct MultiRowModel *original_model,
     struct RayList *filtered_rays = &filtered_model->rays;
     const struct RayList *original_rays = &original_model->rays;
 
-    memcpy(f, original_model->f, 2 * sizeof(double));
-    for(int i = 0; i < nrows; i++)
-    {
-        f[i] = (ceil(f[i] * 128) / 128);
-        if(f[i] <= 0.01) f[i] = 0;
-    }
+    memcpy(f, original_model->f, nrows * sizeof(double));
 
     r = (double*) malloc(nrows * sizeof(double));
     abort_if(!r, "could not allocate r");
@@ -268,11 +266,18 @@ static int append_extra_rays(struct MultiRowModel *model)
 
     for(int i = 0; i < nrows; i++)
     {
+        int found, index;
+        double scale;
+
         for(int j = 0; j < nrows; j++) r[j] = (i == j ? e : 0);
-        LFREE_push_ray(&model->rays, r);
+        rval = CG_find_ray(&model->rays, r, &found, &scale, &index);
+        abort_if(rval, "CG_find_ray failed");
+        if(!found) LFREE_push_ray(&model->rays, r);
 
         for(int j = 0; j < nrows; j++) r[j] = (i == j ? -e : 0);
-        LFREE_push_ray(&model->rays, r);
+        rval = CG_find_ray(&model->rays, r, &found, &scale, &index);
+        abort_if(rval, "CG_find_ray failed");
+        if(!found) LFREE_push_ray(&model->rays, r);
     }
 
     if(nrows == 2)
@@ -409,6 +414,9 @@ int INFINITY_generate_cut(const struct Tableau *tableau, struct Row *cut)
     rval = CG_init_map(&original_map, max_nrays, tableau->nrows);
     abort_if(rval, "CG_init_map failed");
 
+    rval = LFREE_init_conv(&lfree, tableau->nrows, max_nrays);
+    abort_if(rval, "LFREE_init_conv failed");
+
     rval = extract_models(tableau, &original_model, &filtered_model,
             &original_map);
     abort_if(rval, "extract_models failed");
@@ -419,41 +427,18 @@ int INFINITY_generate_cut(const struct Tableau *tableau, struct Row *cut)
         goto CLEANUP;
     }
 
-    rval = LFREE_init_conv(&lfree, tableau->nrows, max_nrays);
-    abort_if(rval, "LFREE_init_conv failed");
-
-//    if(tableau->nrows == 2)
-//        rval = INFINITY_2D_generate_lfree(&filtered_model, &lfree);
-//    else
-//        rval = INFINITY_ND_generate_lfree(&filtered_model, &lfree);
-//
-//    if(rval)
-//    {
-//        rval = ERR_NO_CUT;
-//        goto CLEANUP;
-//    }
-//
-//    for(int i = 0; i < filtered_model.rays.nrays; i++)
-//    {
-//        double *r = LFREE_get_ray(&filtered_model.rays, i);
-//        for(int j = 0; j < tableau->nrows; j++)
-//            r[j] *= lfree.beta[j];
-//    }
-
     rval = append_extra_rays(&filtered_model);
     abort_if(rval, "append_extra_rays failed");
 
-//    if(tableau->nrows == 2)
-//        rval = INFINITY_2D_generate_lfree(&filtered_model, &lfree);
-//    else
-        rval = INFINITY_ND_generate_lfree(&filtered_model, &lfree);
-
-    if(rval)
+    if_debug_level
     {
-        rval = ERR_NO_CUT;
-        goto CLEANUP;
+        rval = CG_print_model(&filtered_model);
+        abort_if(rval, "CG_print_model failed");
     }
 
+    rval = INFINITY_ND_generate_lfree(&filtered_model, &lfree);
+    abort_if(rval, "INFINITY_ND_generate_lfree failed");
+
     if(SHOULD_DUMP_CUTS)
     {
         rval = dump_cut(&lfree);

infinity/library/tests/infinity-nd-test.cpp

@@ -370,6 +370,53 @@ CLEANUP:
     if(rval) FAIL();
 }
 
+TEST(InfinityNDTest, psi_test_3)
+{
+    int rval = 0;
+
+    double f[] = { 0.671875, 0.671875 };
+    double rays[] = {
+            -0.007812500000,  0.000000000000,
+            -0.039062500000,  0.046875000000,
+             0.000000000000,  0.046875000000,
+             0.046875000000,  0.000000000000,
+             0.000000000000, -0.039062500000
+    };
+
+    double beta[] = {
+            66.909090909091,
+            29.440000000000,
+            14.000000000000,
+            14.000000000000,
+            29.440000000000,
+    };
+
+    double q[] = { 0 - f[0], 1 - f[1]};
+
+    struct ConvLFreeSet lfree;
+    lfree.f = f;
+    lfree.beta = beta;
+    lfree.rays.nrays = 5;
+    lfree.rays.values = rays;
+    lfree.nrows = lfree.rays.dim = 2;
+
+    double value;
+    struct LP lp;
+
+    rval = LP_open(&lp);
+    abort_if(rval, "LP_open failed");
+
+    rval = INFINITY_create_psi_lp(&lfree, &lp);
+    abort_if(rval, "INFINITY_create_psi_lp failed");
+
+    rval = INFINITY_psi(lfree.nrows, q, 1.0, &lp, &value);
+    abort_if(rval, "GREDDY_ND_psi failed");
+    EXPECT_NEAR(value, 1.0, 1e-6);
+
+CLEANUP:
+    if(rval) FAIL();
+}
+
 TEST(InfinityNDTest, generate_cut_test_1)
 {
     int rval = 0;

multirow/include/multirow/cg.h

@@ -116,4 +116,6 @@ int CG_total_nz(const struct Tableau *tableau);
 
 double CG_replace_x(const struct Row *row, const double *x);
 
+int CG_print_model(const struct MultiRowModel *model);
+
 #endif //MULTIROW_CG_H

multirow/include/multirow/lfree2d.h

@@ -40,7 +40,6 @@ struct RayList
     int dim;
 };
 
-
 struct ConvLFreeSet
 {
     double *f;
@@ -82,4 +81,6 @@ int LFREE_init_conv(struct ConvLFreeSet *lfree, int dim, int max_nrays);
 
 void LFREE_free_conv(struct ConvLFreeSet *lfree);
 
+int LFREE_print_set(const struct ConvLFreeSet *lfree);
+
 #endif //LFREE_2D_H

multirow/include/multirow/params.h

@@ -41,7 +41,7 @@
 /*
  * Maximum number of sets that should be considered
  */
-#define MAX_N_SETS 1
+#define MAX_N_SETS 1000
 
 /*
  * Number of rays that should be generated per set.

multirow/src/cg.c

@@ -945,7 +945,10 @@ int CG_add_multirow_cuts(struct CG *cg,
                 LP_free_row(&cut);
                 goto NEXT_COMBINATION;
             }
-            else abort_iff(rval, "generate failed (cut %d)", count);
+            else if(rval) {
+                dump_tableau(&tableau, count);
+                abort_iff(1, "generate failed (cut %d)", count);
+            }
 
             if_verbose_level dump_cut(&cut, count);
 
@@ -1115,4 +1118,32 @@ int CG_total_nz(const struct Tableau *tableau)
     return total_nz;
 }
 
+int CG_print_model(const struct MultiRowModel *model)
+{
+    int rval = 0;
+    int nrows = model->nrows;
+
+    time_printf("       f = [");
+    for (int i = 0; i < nrows; i++)
+        printf("%20.12lf ", model->f[i]);
+    printf("]\n");
+
+    for (int i = 0; i < model->rays.nrays; i++)
+    {
+        double *ray = LFREE_get_ray(&model->rays, i);
+        double norm = 0;
+
+        time_printf("ray[%3d] = [", i);
+        for (int j = 0; j < nrows; j++)
+        {
+            printf("%20.12lf ", ray[j]);
+            norm += fabs(ray[j]);
+        }
+        printf("] norm=%20.12lf \n", norm);
+    }
+
+CLEANUP:
+    return rval;
+}
+
 #endif // TEST_SOURCE

multirow/src/lfree2d.c

@@ -559,6 +559,41 @@ CLEANUP:
     return rval;
 }
 
+int LFREE_print_set(const struct ConvLFreeSet *set)
+{
+    int rval = 0;
+
+    log_debug("f=%12.6lf %12.6lf\n", set->f[0], set->f[1]);
+
+    for (int i = 0; i < set->rays.nrays; i++)
+    {
+        double *ray = LFREE_get_ray(&set->rays, i);
+        log_debug("ray[%-3d] = ", i);
+        for (int j = 0; j < set->nrows; j++)
+            printf("%20.12lf ", ray[j]);
+        printf("\n");
+    }
+
+    for (int i = 0; i < set->rays.nrays; i++)
+    {
+        double beta = set->beta[i];
+        log_debug("beta[%-3d] = %20.12lf\n", i, beta);
+    }
+
+    for (int i = 0; i < set->rays.nrays; i++)
+    {
+        double *ray = LFREE_get_ray(&set->rays, i);
+        double beta = set->beta[i];
+        log_debug("vertex[%-3d] = ", i);
+        for (int j = 0; j < set->nrows; j++)
+            printf("%20.12lf ", ray[j] * beta + set->f[j]);
+        printf("\n");
+    }
+
+CLEANUP:
+    return rval;
+}
+
 void LFREE_free_conv(struct ConvLFreeSet *lfree)
 {
     if(!lfree) return;