src

presolve.c File Reference

#include "qs_config.h"
#include "iqsutil.h"
#include "lpdata.h"
#include "lpdefs.h"

Include dependency graph for presolve.c:

Go to the source code of this file.

Data Structures

struct  edge
struct  graph
struct  intptr
struct  node

Defines

#define ILL_LP_STATUS_OK   (0)
#define ILL_PRE_COL_LOGICAL   (1)
#define ILL_PRE_COL_STRUC   (0)
#define ILL_PRE_DELETE_EMPTY_COLUMN   (7)
#define ILL_PRE_DELETE_EMPTY_ROW   (1)
#define ILL_PRE_DELETE_FIXED_VARIABLE   (3)
#define ILL_PRE_DELETE_FORCED_VARIABLE   (4)
#define ILL_PRE_DELETE_FREE_SINGLETON_VARIABLE   (6)
#define ILL_PRE_DELETE_SINGLETON_ROW   (2)
#define ILL_PRE_DELETE_SINGLETON_VARIABLE   (5)
#define ILL_PRE_FEAS_TOL   PFEAS_TOLER
#define ILL_PRE_ZERO_TOL   PIVOT_TOLER

Functions

static int add_to_list (ILLptrworld *world, intptr **list, int i)
static int build_graph (ILLlpdata *lp, graph *G)
static void dump_graph (graph *G)
static void dump_line (ILLlp_preline *line)
static int duplicate_cols (graph *G, int *hit)
static int duplicate_rows (graph *G, int *hit)
static int empty_columns (graph *G, ILLlp_predata *pre)
static int fixed_variables (graph *G, ILLlp_predata *pre)
static int forcing_constraints (graph *G, ILLlp_predata *pre, int *hit)
static void free_graph (graph *G)
static int gather_dup_lists (int *s, int count, int *duptotal, int **dupcnt, int **dupind)
static void get_implied_rhs_bounds (graph *G, int i, EGlpNum_t *lb, EGlpNum_t *ub)
static void get_implied_variable_bounds (graph *G, int j, edge *a_ij, EGlpNum_t *lb, EGlpNum_t *ub)
static int get_next_preop (ILLlp_predata *pre, ILLlp_preop **op)
static int grab_lp_info (graph *G, char **colnames, ILLlp_sinfo *info)
static int grab_lp_line (graph *G, int indx, ILLlp_preline *line, int row_or_col)
 ILL_PTRWORLD_ROUTINES (ILL_PTRWORLD_LISTFREE_ROUTINE(intptr, intptralloc, intptr_bulkalloc, intptrfree)
void ILLlp_predata_free (ILLlp_predata *pre)
void ILLlp_predata_init (ILLlp_predata *pre)
void ILLlp_preline_free (ILLlp_preline *line)
void ILLlp_preline_init (ILLlp_preline *line)
void ILLlp_preop_free (ILLlp_preop *op)
void ILLlp_preop_init (ILLlp_preop *op)
int ILLlp_presolve (ILLlpdata *lp, int pre_types)
int ILLlp_scale (ILLlpdata *lp)
void ILLlp_sinfo_free (ILLlp_sinfo *sinfo)
void ILLlp_sinfo_init (ILLlp_sinfo *sinfo)
int ILLlp_sinfo_print (ILLlp_sinfo *s)
static void init_graph (graph *G)
static void set_fixed_variable (graph *G, int j, EGlpNum_t val)
static int simple_presolve (ILLlpdata *lp, ILLlp_predata *pre, ILLlp_sinfo *info, int pre_types, int *status)
static int singleton_columns (graph *G, ILLlp_predata *pre, int *hit)
static int singleton_rows (graph *G, ILLlp_predata *pre, int *hit)

Variables

static int debug = 0
static int TRACE = 0

Define Documentation

#define ILL_LP_STATUS_OK   (0)

Definition at line 52 of file presolve.c.

Referenced by ILLlp_presolve(), and simple_presolve().

#define ILL_PRE_COL_LOGICAL   (1)

Definition at line 65 of file presolve.c.

Referenced by dump_graph().

#define ILL_PRE_COL_STRUC   (0)

Definition at line 64 of file presolve.c.

Referenced by duplicate_cols(), duplicate_rows(), and grab_lp_info().

#define ILL_PRE_DELETE_EMPTY_COLUMN   (7)

Definition at line 62 of file presolve.c.

Referenced by empty_columns(), and simple_presolve().

#define ILL_PRE_DELETE_EMPTY_ROW   (1)

Definition at line 56 of file presolve.c.

Referenced by simple_presolve(), and singleton_rows().

#define ILL_PRE_DELETE_FIXED_VARIABLE   (3)

Definition at line 58 of file presolve.c.

Referenced by fixed_variables(), and simple_presolve().

#define ILL_PRE_DELETE_FORCED_VARIABLE   (4)

Definition at line 59 of file presolve.c.

Referenced by forcing_constraints(), and simple_presolve().

#define ILL_PRE_DELETE_FREE_SINGLETON_VARIABLE   (6)

Definition at line 61 of file presolve.c.

Referenced by simple_presolve(), and singleton_columns().

#define ILL_PRE_DELETE_SINGLETON_ROW   (2)

Definition at line 57 of file presolve.c.

Referenced by simple_presolve(), and singleton_rows().

#define ILL_PRE_DELETE_SINGLETON_VARIABLE   (5)

Definition at line 60 of file presolve.c.

Referenced by simple_presolve(), and singleton_columns().

#define ILL_PRE_FEAS_TOL   PFEAS_TOLER

Definition at line 53 of file presolve.c.

Referenced by empty_columns(), forcing_constraints(), get_implied_variable_bounds(), and singleton_rows().

#define ILL_PRE_ZERO_TOL   PIVOT_TOLER

Definition at line 54 of file presolve.c.

Referenced by duplicate_cols(), and duplicate_rows().

Function Documentation

static int add_to_list ( ILLptrworld *  world,
intptr **  list,
int  i 
)

Definition at line 2241 of file presolve.c.

References ILL_RETURN, intptr::next, and intptr::this_val.

Referenced by singleton_rows().

static int build_graph ( ILLlpdata *  lp,
graph *  G 
)

Definition at line 2264 of file presolve.c.

References ILLlpdata::A, graph::adjspace, edge::coef, graph::cols, node::deg, graph::edgelist, ILL_SAFE_MALLOC, ILLlpdata::ncols, ILLlpdata::nrows, graph::nzcount, ILLlpdata::nzcount, ILLlpdata::objsense, graph::objsense, graph::rows, node::rowsense, and ILLlpdata::sense.

Referenced by simple_presolve().

static void dump_graph ( graph *  G  ) 

Definition at line 2385 of file presolve.c.

References node::adj, edge::coef, edge::col, graph::cols, node::coltype, edge::coltype, node::deg, node::del, graph::ecount, ILL_PRE_COL_LOGICAL, node::lower, graph::ncols, graph::nrows, node::obj, node::rhs, edge::row, graph::rows, and node::upper.

Referenced by simple_presolve().

static void dump_line ( ILLlp_preline *  line  ) 

Definition at line 812 of file presolve.c.

References ILLlp_preline::count, ILLlp_preline::ind, ILLlp_preline::lower, ILLlp_preline::obj, ILLlp_preline::rhs, ILLlp_preline::row_or_col, ILLlp_preline::upper, and ILLlp_preline::val.

Referenced by simple_presolve().

static int duplicate_cols ( graph *  G,
int *  hit 
)

Definition at line 1799 of file presolve.c.

References node::adj, edge::coef, edge::col, graph::cols, node::coltype, node::deg, edge::del, node::del, gather_dup_lists(), ILL_CLEANUP_IF, ILL_IFFREE, ILL_MAXINT, ILL_PRE_COL_STRUC, ILL_PRE_ZERO_TOL, ILL_RETURN, ILL_SAFE_MALLOC, ILLutil_zeit(), k2, graph::ncols, graph::nrows, graph::rows, and t.

Referenced by simple_presolve().

Here is the call graph for this function:

static int duplicate_rows ( graph *  G,
int *  hit 
)

Definition at line 1660 of file presolve.c.

References node::adj, edge::coef, graph::cols, node::coltype, node::deg, edge::del, node::del, ILL_IFFREE, ILL_MAXINT, ILL_PRE_COL_STRUC, ILL_PRE_ZERO_TOL, ILL_RETURN, ILL_SAFE_MALLOC, ILLutil_zeit(), k2, graph::ncols, graph::nrows, edge::row, graph::rows, node::rowsense, and t.

Referenced by simple_presolve().

Here is the call graph for this function:

static int empty_columns ( graph *  G,
ILLlp_predata *  pre 
)

Definition at line 1082 of file presolve.c.

References node::adj, ILLlp_preop::colindex, graph::cols, node::deg, node::del, get_next_preop(), grab_lp_line(), ILL_CLEANUP_IF, ILL_MAXDOUBLE, ILL_MINDOUBLE, ILL_PRE_DELETE_EMPTY_COLUMN, ILL_PRE_FEAS_TOL, ILL_RETURN, ILLlp_preop::line, node::lower, graph::ncols, node::obj, graph::objsense, ILLlp_preop::ptype, ILLlp_preop::rowindex, set_fixed_variable(), and node::upper.

Referenced by simple_presolve().

Here is the call graph for this function:

static int fixed_variables ( graph *  G,
ILLlp_predata *  pre 
)

Definition at line 1045 of file presolve.c.

References ILLlp_preop::colindex, graph::cols, node::del, get_next_preop(), grab_lp_line(), ILL_CLEANUP_IF, ILL_PRE_DELETE_FIXED_VARIABLE, ILL_RETURN, ILLlp_preop::line, node::lower, graph::ncols, ILLlp_preop::ptype, ILLlp_preop::rowindex, set_fixed_variable(), and node::upper.

Referenced by simple_presolve().

Here is the call graph for this function:

static int forcing_constraints ( graph *  G,
ILLlp_predata *  pre,
int *  hit 
)

Definition at line 1336 of file presolve.c.

References node::adj, edge::coef, edge::col, ILLlp_preop::colindex, graph::cols, node::deg, edge::del, node::del, get_implied_rhs_bounds(), get_next_preop(), grab_lp_line(), ILL_CLEANUP_IF, ILL_PRE_DELETE_FORCED_VARIABLE, ILL_PRE_FEAS_TOL, ILLlp_preop::line, node::lower, graph::nrows, ILLlp_predata::opcount, ILLlp_preop::ptype, ILLlp_preop::rowindex, graph::rows, set_fixed_variable(), and node::upper.

Referenced by simple_presolve().

Here is the call graph for this function:

static void free_graph ( graph *  G  ) 

Definition at line 2458 of file presolve.c.

References graph::adjspace, edge::coef, graph::cols, graph::edgelist, ILL_IFFREE, ILLptrworld_delete(), init_graph(), graph::intptrworld, graph::nzcount, and graph::rows.

Here is the call graph for this function:

static int gather_dup_lists ( int *  s,
int  count,
int *  duptotal,
int **  dupcnt,
int **  dupind 
)

Definition at line 1931 of file presolve.c.

References ILL_IFFREE, ILL_MAXINT, ILL_RETURN, and ILL_SAFE_MALLOC.

Referenced by duplicate_cols().

static void get_implied_rhs_bounds ( graph *  G,
int  i,
EGlpNum_t *  lb,
EGlpNum_t *  ub 
)

Definition at line 2075 of file presolve.c.

References node::adj, edge::coef, edge::col, graph::cols, node::deg, edge::del, ILL_MAXDOUBLE, ILL_MINDOUBLE, and graph::rows.

Referenced by forcing_constraints(), and get_implied_variable_bounds().

static void get_implied_variable_bounds ( graph *  G,
int  j,
edge *  a_ij,
EGlpNum_t *  lb,
EGlpNum_t *  ub 
)

Definition at line 2164 of file presolve.c.

References edge::coef, graph::cols, get_implied_rhs_bounds(), ILL_MAXDOUBLE, ILL_MINDOUBLE, ILL_PRE_FEAS_TOL, node::lower, node::rhs, edge::row, graph::rows, and node::upper.

Referenced by singleton_columns().

Here is the call graph for this function:

static int get_next_preop ( ILLlp_predata *  pre,
ILLlp_preop **  op 
)

Definition at line 2215 of file presolve.c.

References ILL_RETURN, ILLlp_preop_init(), ILLlp_predata::opcount, ILLlp_predata::oplist, and ILLlp_predata::opsize.

Referenced by empty_columns(), fixed_variables(), forcing_constraints(), singleton_columns(), and singleton_rows().

Here is the call graph for this function:

static int grab_lp_info ( graph *  G,
char **  colnames,
ILLlp_sinfo *  info 
)

Definition at line 838 of file presolve.c.

References ILLlp_sinfo::A, node::adj, edge::coef, ILLlp_sinfo::colnames, graph::cols, ILLlp_sinfo::colsize, node::coltype, node::deg, node::del, ILL_namebufsize, ILL_PRE_COL_STRUC, ILL_SAFE_MALLOC, node::lower, ILLlp_sinfo::lower, ILLmatrix::matbeg, ILLmatrix::matcnt, ILLmatrix::matcols, ILLmatrix::matcolsize, ILLmatrix::matfree, ILLmatrix::matind, ILLmatrix::matrows, ILLmatrix::matsize, ILLmatrix::matval, ILLlp_sinfo::ncols, graph::ncols, ILLlp_sinfo::nrows, graph::nrows, ILLlp_sinfo::nzcount, node::obj, ILLlp_sinfo::obj, node::rhs, ILLlp_sinfo::rhs, edge::row, graph::rows, ILLlp_sinfo::rowsize, node::upper, and ILLlp_sinfo::upper.

static int grab_lp_line ( graph *  G,
int  indx,
ILLlp_preline *  line,
int  row_or_col 
)

Definition at line 747 of file presolve.c.

References node::adj, graph::cols, ILLlp_preline::count, node::deg, edge::del, and graph::rows.

Referenced by empty_columns(), fixed_variables(), forcing_constraints(), singleton_columns(), and singleton_rows().

ILL_PTRWORLD_ROUTINES ( ILL_PTRWORLD_LISTFREE_ROUTINE (  intptr,
intptralloc  ,
intptr_bulkalloc  ,
intptrfree   
)

Definition at line 218 of file presolve.c.

References ILL_MAXDOUBLE, ILL_SAFE_MALLOC, ILLlp_rows_clear(), ILLmatrix::matbeg, ILLmatrix::matcnt, ILLmatrix::matcols, ILLmatrix::matcolsize, ILLmatrix::matfree, ILLmatrix::matind, ILLmatrix::matsize, and ILLmatrix::matval.

Here is the call graph for this function:

void ILLlp_predata_free ( ILLlp_predata *  pre  ) 

Definition at line 2599 of file presolve.c.

References ILLlp_predata::colfixval, ILLlp_predata::colmap, ILLlp_predata::colscale, ILL_IFFREE, ILLlp_predata_init(), ILLlp_preop_free(), ILLlp_predata::opcount, ILLlp_predata::oplist, ILLlp_predata::rowfixval, ILLlp_predata::rowmap, and ILLlp_predata::rowscale.

Referenced by ILLlp_presolve().

Here is the call graph for this function:

void ILLlp_predata_init ( ILLlp_predata *  pre  ) 

void ILLlp_preline_free ( ILLlp_preline *  line  ) 

Definition at line 2663 of file presolve.c.

References ILL_IFFREE, ILLlp_preline::ind, ILLlp_preline::lower, ILLlp_preline::obj, ILLlp_preline::rhs, ILLlp_preline::upper, and ILLlp_preline::val.

Referenced by ILLlp_preop_free().

void ILLlp_preline_init ( ILLlp_preline *  line  ) 

Definition at line 2644 of file presolve.c.

References ILLlp_preline::count, ILLlp_preline::ind, ILLlp_preline::lower, ILLlp_preline::obj, ILLlp_preline::rhs, ILLlp_preline::upper, and ILLlp_preline::val.

Referenced by ILLlp_preop_init().

void ILLlp_preop_free ( ILLlp_preop *  op  ) 

Definition at line 2634 of file presolve.c.

References ILLlp_preline_free(), ILLlp_preop_init(), and ILLlp_preop::line.

Referenced by ILLlp_predata_free().

Here is the call graph for this function:

void ILLlp_preop_init ( ILLlp_preop *  op  ) 

Definition at line 2622 of file presolve.c.

References ILLlp_preop::colindex, ILLlp_preline_init(), ILLlp_preop::line, ILLlp_preop::ptype, and ILLlp_preop::rowindex.

Referenced by get_next_preop(), and ILLlp_preop_free().

Here is the call graph for this function:

int ILLlp_presolve ( ILLlpdata *  lp,
int  pre_types 
)

Definition at line 462 of file presolve.c.

References ILL_CLEANUP_IF, ILL_IFFREE, ILL_LP_STATUS_OK, ILL_RETURN, ILL_SAFE_MALLOC, ILLlp_predata_free(), ILLlp_predata_init(), ILLlp_sinfo_free(), ILLlp_sinfo_init(), ILLlpdata::presolve, simple_presolve(), and ILLlpdata::sinfo.

Here is the call graph for this function:

int ILLlp_scale ( ILLlpdata *  lp  ) 

Definition at line 349 of file presolve.c.

References ILLlpdata::A, ILL_ERROR, ILL_MAXDOUBLE, ILL_MINDOUBLE, ILLlpdata::lower, ILLmatrix::matbeg, ILLmatrix::matcnt, ILLmatrix::matind, ILLmatrix::matval, ILLlpdata::ncols, ILLlpdata::nrows, ILLlpdata::nstruct, ILLlpdata::obj, ILLlpdata::rhs, ILLlpdata::rowmap, ILLlpdata::structmap, and ILLlpdata::upper.

void ILLlp_sinfo_free ( ILLlp_sinfo *  sinfo  ) 

void ILLlp_sinfo_init ( ILLlp_sinfo *  sinfo  ) 

int ILLlp_sinfo_print ( ILLlp_sinfo *  s  ) 

Definition at line 2482 of file presolve.c.

References ILLlp_sinfo::A, ILLlpdata::A, ILLlp_sinfo::colnames, ILLlpdata::colnames, ILL_IFFREE, ILL_RETURN, ILL_SAFE_MALLOC, ILLlpdata_init(), ILLlpdata::intmarker, ILLlp_sinfo::lower, ILLlpdata::lower, ILLmatrix::matbeg, ILLmatrix::matcnt, ILLmatrix::matind, ILLmatrix::matval, ILLlp_sinfo::ncols, ILLlpdata::ncols, ILLlp_sinfo::nrows, ILLlpdata::nrows, ILLlp_sinfo::nzcount, ILLlpdata::nzcount, ILLlp_sinfo::obj, ILLlpdata::obj, ILLlpdata::objname, ILLlp_sinfo::objsense, ILLlpdata::objsense, ILLlpdata::probname, ILLlp_sinfo::rhs, ILLlpdata::rhs, ILLlpdata::rownames, ILLlpdata::sense, ILLlp_sinfo::upper, and ILLlpdata::upper.

Here is the call graph for this function:

static void init_graph ( graph *  G  ) 

Definition at line 2442 of file presolve.c.

References graph::adjspace, graph::cols, graph::ecount, graph::edgelist, ILLptrworld_init(), graph::intptrworld, graph::ncols, graph::nrows, and graph::rows.

Referenced by free_graph(), and simple_presolve().

Here is the call graph for this function:

static void set_fixed_variable ( graph *  G,
int  j,
EGlpNum_t  val 
) [static]

Definition at line 2054 of file presolve.c.

References node::adj, edge::coef, graph::cols, node::deg, edge::del, node::del, edge::row, and graph::rows.

Referenced by empty_columns(), fixed_variables(), and forcing_constraints().

static int simple_presolve ( ILLlpdata *  lp,
ILLlp_predata *  pre,
ILLlp_sinfo *  info,
int  pre_types,
int *  status 
) [static]

Definition at line 580 of file presolve.c.

References build_graph(), ILLlp_preop::colindex, debug, dump_graph(), dump_line(), duplicate_cols(), duplicate_rows(), empty_columns(), fixed_variables(), forcing_constraints(), ILL_CLEANUP_IF, ILL_LP_STATUS_OK, ILL_PRE_DELETE_EMPTY_COLUMN, ILL_PRE_DELETE_EMPTY_ROW, ILL_PRE_DELETE_FIXED_VARIABLE, ILL_PRE_DELETE_FORCED_VARIABLE, ILL_PRE_DELETE_FREE_SINGLETON_VARIABLE, ILL_PRE_DELETE_SINGLETON_ROW, ILL_PRE_DELETE_SINGLETON_VARIABLE, ILL_PRE_DUPLICATE_COL, ILL_PRE_DUPLICATE_ROW, ILL_PRE_EMPTY_COL, ILL_PRE_FIXED, ILL_PRE_FORCING, ILL_PRE_SINGLE_COL, ILL_PRE_SINGLE_ROW, init_graph(), ILLlp_preop::line, ILLlpdata::ncols, ILLlpdata::nrows, ILLlpdata::nzcount, ILLlp_predata::opcount, ILLlp_predata::oplist, ILLlp_preop::ptype, ILLlp_preop::rowindex, singleton_columns(), and singleton_rows().

Referenced by ILLlp_presolve().

Here is the call graph for this function:

static int singleton_columns ( graph *  G,
ILLlp_predata *  pre,
int *  hit 
)

Definition at line 1416 of file presolve.c.

References node::adj, edge::coef, edge::col, ILLlp_preop::colindex, graph::cols, node::deg, edge::del, node::del, get_implied_variable_bounds(), get_next_preop(), grab_lp_line(), ILL_CLEANUP_IF, ILL_MAXDOUBLE, ILL_MINDOUBLE, ILL_PRE_DELETE_FREE_SINGLETON_VARIABLE, ILL_PRE_DELETE_SINGLETON_VARIABLE, ILLlp_preop::line, node::lower, graph::ncols, node::obj, ILLlp_predata::opcount, ILLlp_preop::ptype, ILLlp_preop::rowindex, graph::rows, and node::upper.

Referenced by simple_presolve().

Here is the call graph for this function:

static int singleton_rows ( graph *  G,
ILLlp_predata *  pre,
int *  hit 
)

Definition at line 1167 of file presolve.c.

References add_to_list(), node::adj, edge::coef, edge::col, ILLlp_preop::colindex, graph::cols, node::deg, edge::del, node::del, get_next_preop(), grab_lp_line(), ILL_CLEANUP_IF, ILL_PRE_DELETE_EMPTY_ROW, ILL_PRE_DELETE_SINGLETON_ROW, ILL_PRE_FEAS_TOL, ILL_SAFE_MALLOC, graph::intptrworld, ILLlp_preop::line, node::lower, intptr::next, graph::nrows, ILLlp_preop::ptype, ILLlp_preline::rhs, node::rhs, edge::row, ILLlp_preop::rowindex, graph::rows, and node::upper.

Referenced by simple_presolve().

Here is the call graph for this function:

Variable Documentation

int debug = 0 [static]

Definition at line 67 of file presolve.c.

Referenced by simple_presolve().

int TRACE = 0 [static]

Definition at line 24 of file presolve.c.

Generated on Thu Mar 29 09:45:27 2012 for QSopt_ex by  doxygen 1.4.7