<commit_before>/*===========================================================================*/
/*                                                                           */
/* This file is part of the SYMPHONY MILP Solver Framework.                  */
/*                                                                           */
/* SYMPHONY was jointly developed by <NAME> (<EMAIL>) and    */
/* <NAME> (<EMAIL>).                                        */
/*                                                                           */
/* (c) Copyright 2000-2008 <NAME>. All Rights Reserved.                  */
/*                                                                           */
/* This software is licensed under the Common Public License. Please see     */
/* accompanying file for terms.                                              */
/*                                                                           */
/*===========================================================================*/

#include <stdlib.h>
#include <math.h>
#include <string.h>

#include "sym_qsort.h"
#include "sym_lp.h"
#include "sym_constants.h"
#include "sym_lp_solver.h"
#include "sym_primal_heuristics.h"
#include "sym_macros.h"
#include "sym_return_values.h"

/*===========================================================================*/
/*===========================================================================*\
 * This file contains heuristics to find an integral solution after an LP
 * is solved.
 \*===========================================================================*/
/*===========================================================================*/
/*
 * TODO: 
 * make independent of solver
 */

int feasibility_pump (lp_prob *p, char *found_better_solution,
      double &solution_value, double *betterSolution)
{
   int                      termcode    = FUNCTION_TERMINATED_NORMALLY;
   FPdata                  *fp_data     = (FPdata*) malloc(sizeof(FPdata));
   LPdata                  *lp_data     = p->lp_data;
   LPdata                  *new_lp_data = (LPdata *)calloc(1,sizeof(LPdata));	
   /* no. of max pumping cycles */
   int                      max_iter    = p->par.fp_max_cycles;
   int                      n           = lp_data->n;
   /* use OSI to get lp data */
   OsiSolverInterface      *model       = p->lp_data->si;
   const CoinPackedMatrix  *matrix      = model->getMatrixByRow();
   const double            *lp_r_low    = model->getRowLower();
   const double            *lp_r_up     = model->getRowUpper();
   int                      i, r, iter, cnt, verbosity;
   int                     *indices;
   double                  *values;
   double                   fp_time, last_fp_time, real_obj_value, target_ub;
   FPvars                 **vars;
   double                   gap           = model->getInfinity();
   double                   obj_lb        = lp_data->objval;
   double                   total_time    = 0;
   const double            *mip_obj       = model->getObjCoefficients();
   char                     is_feasible   = FALSE;
   double                  *x_ip, *x_lp, new_solution_value;
   const double             fp_display_interval = p->par.fp_display_interval;

   fp_time                                = used_time(&total_time);
   if (p->lp_stat.fp_calls < 1) {
      CoinSeedRandom(17000);
   }

   /* total_time and fp_time both now have total time used by symphony's lp
    * process */
   fp_time                                = used_time(&total_time);
   last_fp_time                           = fp_time;
   /* fp_time should now be zero and total_time be still the same */

   verbosity = fp_data->verbosity     = p->par.verbosity;
   if (p->bc_index<1) {
      PRINT(verbosity, 0, ("starting feasibility pump\n"));
   }

   *found_better_solution = FALSE;
   fp_data->mip_obj       = (double *)malloc(n*DSIZE);
   fp_data->flip_fraction = p->par.fp_flip_fraction;
   memcpy(fp_data->mip_obj,mip_obj,n*DSIZE);

   /* initialize the lp solver. load the current basis */
   fp_initialize_lp_solver(p, new_lp_data, fp_data);
   x_ip = fp_data->x_ip;
   x_lp = fp_data->x_lp;
   if (p->has_ub && p->mip->mip_inf && 
         (p->mip->mip_inf->obj_size <= p->mip->mip_inf->max_row_size || 
          p->mip->mip_inf->obj_size < n/10)) {
      solution_value = p->ub-p->mip->obj_offset;
      fp_add_obj_row(new_lp_data, n, mip_obj, p->ub-p->par.granularity);
   } else {
      solution_value = model->getInfinity();
   }

   /* round the x_lp and store as x_ip, it will usually become infeasible */
   vars = fp_data->fp_vars;

   /* do the following max_iter times */
   fp_time += used_time(&total_time);
   for (iter=0; iter<max_iter && fp_time<p->par.fp_time_limit; iter++) {
      if (fp_time - last_fp_time > fp_display_interval || verbosity > 5) {
         PRINT(verbosity, 0, 
               ("feasibility pump: starting iteration %d, time used = %.2f\n",
                iter, fp_time));
         last_fp_time = fp_time;
      }
      is_feasible = FALSE;
      /* solve an lp */
      fp_round(fp_data, new_lp_data);
      if (fp_data->x_bar_len[fp_data->iter] == -1) {
         /*
          * the cost and reference point are same as some other iteration. we
          * should stop here because we are cycling
          */
         PRINT(verbosity,5,("fp: leaving because of cycling\n"));
         fp_data->iter++;
         break;
      }
      fp_is_feasible (lp_data,matrix,lp_r_low,lp_r_up,fp_data,&is_feasible);

      if (is_feasible == TRUE) {
         /* we found what we wanted */
         memcpy(betterSolution, x_ip, n*DSIZE);

         new_solution_value = 0;
         for (i=0;i<n;i++) {
            new_solution_value += betterSolution[i]*mip_obj[i];
         }
         if (new_solution_value<solution_value-p->par.granularity) {
            solution_value = new_solution_value;
            indices = p->lp_data->tmp.i1;          /* n */
            values  = p->lp_data->tmp.d;           /* n */
            cnt     = collect_nonzeros(p, betterSolution, indices, values);
            gap     = (solution_value -<commit_msg>fix for fp to keep the best feas sol, not the last one<commit_after>/*===========================================================================*/
/*                                                                           */
/* This file is part of the SYMPHONY MILP Solver Framework.                  */
/*                                                                           */
/* SYMPHONY was jointly developed by <NAME> (<EMAIL>) and    */
/* <NAME> (<EMAIL>).                                        */
/*                                                                           */
/* (c) Copyright 2000-2008 <NAME>. All Rights Reserved.                  */
/*                                                                           */
/* This software is licensed under the Common Public License. Please see     */
/* accompanying file for terms.                                              */
/*                                                                           */
/*===========================================================================*/

#include <stdlib.h>
#include <math.h>
#include <string.h>

#include "sym_qsort.h"
#include "sym_lp.h"
#include "sym_constants.h"
#include "sym_lp_solver.h"
#include "sym_primal_heuristics.h"
#include "sym_macros.h"
#include "sym_return_values.h"

/*===========================================================================*/
/*===========================================================================*\
 * This file contains heuristics to find an integral solution after an LP
 * is solved.
 \*===========================================================================*/
/*===========================================================================*/
/*
 * TODO: 
 * make independent of solver
 */

int feasibility_pump (lp_prob *p, char *found_better_solution,
      double &solution_value, double *betterSolution)
{
   int                      termcode    = FUNCTION_TERMINATED_NORMALLY;
   FPdata                  *fp_data     = (FPdata*) malloc(sizeof(FPdata));
   LPdata                  *lp_data     = p->lp_data;
   LPdata                  *new_lp_data = (LPdata *)calloc(1,sizeof(LPdata));	
   /* no. of max pumping cycles */
   int                      max_iter    = p->par.fp_max_cycles;
   int                      n           = lp_data->n;
   /* use OSI to get lp data */
   OsiSolverInterface      *model       = p->lp_data->si;
   const CoinPackedMatrix  *matrix      = model->getMatrixByRow();
   const double            *lp_r_low    = model->getRowLower();
   const double            *lp_r_up     = model->getRowUpper();
   int                      i, r, iter, cnt, verbosity;
   int                     *indices;
   double                  *values;
   double                   fp_time, last_fp_time, real_obj_value, target_ub;
   FPvars                 **vars;
   double                   gap           = model->getInfinity();
   double                   obj_lb        = lp_data->objval;
   double                   total_time    = 0;
   const double            *mip_obj       = model->getObjCoefficients();
   char                     is_feasible   = FALSE;
   double                  *x_ip, *x_lp, new_solution_value;
   const double             fp_display_interval = p->par.fp_display_interval;

   fp_time                                = used_time(&total_time);
   if (p->lp_stat.fp_calls < 1) {
      CoinSeedRandom(17000);
   }

   /* total_time and fp_time both now have total time used by symphony's lp
    * process */
   fp_time                                = used_time(&total_time);
   last_fp_time                           = fp_time;
   /* fp_time should now be zero and total_time be still the same */

   verbosity = fp_data->verbosity     = p->par.verbosity;
   if (p->bc_index<1) {
      PRINT(verbosity, 0, ("starting feasibility pump\n"));
   }

   *found_better_solution = FALSE;
   fp_data->mip_obj       = (double *)malloc(n*DSIZE);
   fp_data->flip_fraction = p->par.fp_flip_fraction;
   memcpy(fp_data->mip_obj,mip_obj,n*DSIZE);

   /* initialize the lp solver. load the current basis */
   fp_initialize_lp_solver(p, new_lp_data, fp_data);
   x_ip = fp_data->x_ip;
   x_lp = fp_data->x_lp;
   if (p->has_ub && p->mip->mip_inf && 
         (p->mip->mip_inf->obj_size <= p->mip->mip_inf->max_row_size || 
          p->mip->mip_inf->obj_size < n/10)) {
      solution_value = p->ub-p->mip->obj_offset;
      fp_add_obj_row(new_lp_data, n, mip_obj, p->ub-p->par.granularity);
   } else {
      solution_value = model->getInfinity();
   }

   /* round the x_lp and store as x_ip, it will usually become infeasible */
   vars = fp_data->fp_vars;

   /* do the following max_iter times */
   fp_time += used_time(&total_time);
   for (iter=0; iter<max_iter && fp_time<p->par.fp_time_limit; iter++) {
      if (fp_time - last_fp_time > fp_display_interval || verbosity > 5) {
         PRINT(verbosity, 0, 
               ("feasibility pump: starting iteration %d, time used = %.2f\n",
                iter, fp_time));
         last_fp_time = fp_time;
      }
      is_feasible = FALSE;
      /* solve an lp */
      fp_round(fp_data, new_lp_data);
      if (fp_data->x_bar_len[fp_data->iter] == -1) {
         /*
          * the cost and reference point are same as some other iteration. we
          * should stop here because we are cycling
          */
         PRINT(verbosity,5,("fp: leaving because of cycling\n"));
         fp_data->iter++;
         break;
      }
      fp_is_feasible (lp_data,matrix,lp_r_low,lp_r_up,fp_data,&is_feasible);

      if (is_feasible == TRUE) {
         new_solution_value = 0;
         for (i=0;i<n;i++) {
            new_solution_value += x_ip[i]*mip_obj[i];
         }
         if (new_solution_value<solution_value-p->par.granularity) {
	    /* we found what we wanted */
	    memcpy(betterSolution, x_ip, n*DSIZE);
            solution_value = new_solution_value;
            indices = p->lp_data->tmp.i1;          /* n */
            values  = p->lp_data->tmp.d;           /* n */
            cnt     = collect_nonzeros(p, betterSolution, indices, values);
            gap     = (solution_value -
{'fraction_non_alphanumeric': 0.17817027510988118, 'fraction_numerical': 0.004720820446036138, 'mean_word_length': 1.752464157706093, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 123, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 46, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7142917', 'n_tokens_mistral': 3669, 'n_tokens_neox': 3408, 'n_words': 772}