alpar@9: /* glpnpp.h (LP/MIP preprocessor) */
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@9: *
alpar@9: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9: *  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9: *  E-mail: <mao@gnu.org>.
alpar@9: *
alpar@9: *  GLPK is free software: you can redistribute it and/or modify it
alpar@9: *  under the terms of the GNU General Public License as published by
alpar@9: *  the Free Software Foundation, either version 3 of the License, or
alpar@9: *  (at your option) any later version.
alpar@9: *
alpar@9: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9: *  License for more details.
alpar@9: *
alpar@9: *  You should have received a copy of the GNU General Public License
alpar@9: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9: ***********************************************************************/
alpar@9: 
alpar@9: #ifndef GLPNPP_H
alpar@9: #define GLPNPP_H
alpar@9: 
alpar@9: #include "glpapi.h"
alpar@9: 
alpar@9: typedef struct NPP NPP;
alpar@9: typedef struct NPPROW NPPROW;
alpar@9: typedef struct NPPCOL NPPCOL;
alpar@9: typedef struct NPPAIJ NPPAIJ;
alpar@9: typedef struct NPPTSE NPPTSE;
alpar@9: typedef struct NPPLFE NPPLFE;
alpar@9: 
alpar@9: struct NPP
alpar@9: {     /* LP/MIP preprocessor workspace */
alpar@9:       /*--------------------------------------------------------------*/
alpar@9:       /* original problem segment */
alpar@9:       int orig_dir;
alpar@9:       /* optimization direction flag:
alpar@9:          GLP_MIN - minimization
alpar@9:          GLP_MAX - maximization */
alpar@9:       int orig_m;
alpar@9:       /* number of rows */
alpar@9:       int orig_n;
alpar@9:       /* number of columns */
alpar@9:       int orig_nnz;
alpar@9:       /* number of non-zero constraint coefficients */
alpar@9:       /*--------------------------------------------------------------*/
alpar@9:       /* transformed problem segment (always minimization) */
alpar@9:       DMP *pool;
alpar@9:       /* memory pool to store problem components */
alpar@9:       char *name;
alpar@9:       /* problem name (1 to 255 chars); NULL means no name is assigned
alpar@9:          to the problem */
alpar@9:       char *obj;
alpar@9:       /* objective function name (1 to 255 chars); NULL means no name
alpar@9:          is assigned to the objective function */
alpar@9:       double c0;
alpar@9:       /* constant term of the objective function */
alpar@9:       int nrows;
alpar@9:       /* number of rows introduced into the problem; this count
alpar@9:          increases by one every time a new row is added and never
alpar@9:          decreases; thus, actual number of rows may be less than nrows
alpar@9:          due to row deletions */
alpar@9:       int ncols;
alpar@9:       /* number of columns introduced into the problem; this count
alpar@9:          increases by one every time a new column is added and never
alpar@9:          decreases; thus, actual number of column may be less than
alpar@9:          ncols due to column deletions */
alpar@9:       NPPROW *r_head;
alpar@9:       /* pointer to the beginning of the row list */
alpar@9:       NPPROW *r_tail;
alpar@9:       /* pointer to the end of the row list */
alpar@9:       NPPCOL *c_head;
alpar@9:       /* pointer to the beginning of the column list */
alpar@9:       NPPCOL *c_tail;
alpar@9:       /* pointer to the end of the column list */
alpar@9:       /*--------------------------------------------------------------*/
alpar@9:       /* transformation history */
alpar@9:       DMP *stack;
alpar@9:       /* memory pool to store transformation entries */
alpar@9:       NPPTSE *top;
alpar@9:       /* pointer to most recent transformation entry */
alpar@9: #if 0 /* 16/XII-2009 */
alpar@9:       int count[1+25];
alpar@9:       /* transformation statistics */
alpar@9: #endif
alpar@9:       /*--------------------------------------------------------------*/
alpar@9:       /* resultant (preprocessed) problem segment */
alpar@9:       int m;
alpar@9:       /* number of rows */
alpar@9:       int n;
alpar@9:       /* number of columns */
alpar@9:       int nnz;
alpar@9:       /* number of non-zero constraint coefficients */
alpar@9:       int *row_ref; /* int row_ref[1+m]; */
alpar@9:       /* row_ref[i], 1 <= i <= m, is the reference number assigned to
alpar@9:          a row, which is i-th row of the resultant problem */
alpar@9:       int *col_ref; /* int col_ref[1+n]; */
alpar@9:       /* col_ref[j], 1 <= j <= n, is the reference number assigned to
alpar@9:          a column, which is j-th column of the resultant problem */
alpar@9:       /*--------------------------------------------------------------*/
alpar@9:       /* recovered solution segment */
alpar@9:       int sol;
alpar@9:       /* solution indicator:
alpar@9:          GLP_SOL - basic solution
alpar@9:          GLP_IPT - interior-point solution
alpar@9:          GLP_MIP - mixed integer solution */
alpar@9:       int scaling;
alpar@9:       /* scaling option:
alpar@9:          GLP_OFF - scaling is disabled
alpar@9:          GLP_ON  - scaling is enabled */
alpar@9:       int p_stat;
alpar@9:       /* status of primal basic solution:
alpar@9:          GLP_UNDEF  - primal solution is undefined
alpar@9:          GLP_FEAS   - primal solution is feasible
alpar@9:          GLP_INFEAS - primal solution is infeasible
alpar@9:          GLP_NOFEAS - no primal feasible solution exists */
alpar@9:       int d_stat;
alpar@9:       /* status of dual basic solution:
alpar@9:          GLP_UNDEF  - dual solution is undefined
alpar@9:          GLP_FEAS   - dual solution is feasible
alpar@9:          GLP_INFEAS - dual solution is infeasible
alpar@9:          GLP_NOFEAS - no dual feasible solution exists */
alpar@9:       int t_stat;
alpar@9:       /* status of interior-point solution:
alpar@9:          GLP_UNDEF  - interior solution is undefined
alpar@9:          GLP_OPT    - interior solution is optimal */
alpar@9:       int i_stat;
alpar@9:       /* status of mixed integer solution:
alpar@9:          GLP_UNDEF  - integer solution is undefined
alpar@9:          GLP_OPT    - integer solution is optimal
alpar@9:          GLP_FEAS   - integer solution is feasible
alpar@9:          GLP_NOFEAS - no integer solution exists */
alpar@9:       char *r_stat; /* char r_stat[1+nrows]; */
alpar@9:       /* r_stat[i], 1 <= i <= nrows, is status of i-th row:
alpar@9:          GLP_BS - inactive constraint
alpar@9:          GLP_NL - active constraint on lower bound
alpar@9:          GLP_NU - active constraint on upper bound
alpar@9:          GLP_NF - active free row
alpar@9:          GLP_NS - active equality constraint */
alpar@9:       char *c_stat; /* char c_stat[1+nrows]; */
alpar@9:       /* c_stat[j], 1 <= j <= nrows, is status of j-th column:
alpar@9:          GLP_BS - basic variable
alpar@9:          GLP_NL - non-basic variable on lower bound
alpar@9:          GLP_NU - non-basic variable on upper bound
alpar@9:          GLP_NF - non-basic free variable
alpar@9:          GLP_NS - non-basic fixed variable */
alpar@9:       double *r_pi; /* double r_pi[1+nrows]; */
alpar@9:       /* r_pi[i], 1 <= i <= nrows, is Lagrange multiplier (dual value)
alpar@9:          for i-th row (constraint) */
alpar@9:       double *c_value; /* double c_value[1+ncols]; */
alpar@9:       /* c_value[j], 1 <= j <= ncols, is primal value of j-th column
alpar@9:          (structural variable) */
alpar@9: };
alpar@9: 
alpar@9: struct NPPROW
alpar@9: {     /* row (constraint) */
alpar@9:       int i;
alpar@9:       /* reference number assigned to the row, 1 <= i <= nrows */
alpar@9:       char *name;
alpar@9:       /* row name (1 to 255 chars); NULL means no name is assigned to
alpar@9:          the row */
alpar@9:       double lb;
alpar@9:       /* lower bound; -DBL_MAX means the row has no lower bound */
alpar@9:       double ub;
alpar@9:       /* upper bound; +DBL_MAX means the row has no upper bound */
alpar@9:       NPPAIJ *ptr;
alpar@9:       /* pointer to the linked list of constraint coefficients */
alpar@9:       int temp;
alpar@9:       /* working field used by preprocessor routines */
alpar@9:       NPPROW *prev;
alpar@9:       /* pointer to previous row in the row list */
alpar@9:       NPPROW *next;
alpar@9:       /* pointer to next row in the row list */
alpar@9: };
alpar@9: 
alpar@9: struct NPPCOL
alpar@9: {     /* column (variable) */
alpar@9:       int j;
alpar@9:       /* reference number assigned to the column, 1 <= j <= ncols */
alpar@9:       char *name;
alpar@9:       /* column name (1 to 255 chars); NULL means no name is assigned
alpar@9:          to the column */
alpar@9:       char is_int;
alpar@9:       /* 0 means continuous variable; 1 means integer variable */
alpar@9:       double lb;
alpar@9:       /* lower bound; -DBL_MAX means the column has no lower bound */
alpar@9:       double ub;
alpar@9:       /* upper bound; +DBL_MAX means the column has no upper bound */
alpar@9:       double coef;
alpar@9:       /* objective coefficient */
alpar@9:       NPPAIJ *ptr;
alpar@9:       /* pointer to the linked list of constraint coefficients */
alpar@9:       int temp;
alpar@9:       /* working field used by preprocessor routines */
alpar@9: #if 1 /* 28/XII-2009 */
alpar@9:       union
alpar@9:       {  double ll;
alpar@9:          /* implied column lower bound */
alpar@9:          int pos;
alpar@9:          /* vertex ordinal number corresponding to this binary column
alpar@9:             in the conflict graph (0, if the vertex does not exist) */
alpar@9:       }  ll;
alpar@9:       union
alpar@9:       {  double uu;
alpar@9:          /* implied column upper bound */
alpar@9:          int neg;
alpar@9:          /* vertex ordinal number corresponding to complement of this
alpar@9:             binary column in the conflict graph (0, if the vertex does
alpar@9:             not exist) */
alpar@9:       }  uu;
alpar@9: #endif
alpar@9:       NPPCOL *prev;
alpar@9:       /* pointer to previous column in the column list */
alpar@9:       NPPCOL *next;
alpar@9:       /* pointer to next column in the column list */
alpar@9: };
alpar@9: 
alpar@9: struct NPPAIJ
alpar@9: {     /* constraint coefficient */
alpar@9:       NPPROW *row;
alpar@9:       /* pointer to corresponding row */
alpar@9:       NPPCOL *col;
alpar@9:       /* pointer to corresponding column */
alpar@9:       double val;
alpar@9:       /* (non-zero) coefficient value */
alpar@9:       NPPAIJ *r_prev;
alpar@9:       /* pointer to previous coefficient in the same row */
alpar@9:       NPPAIJ *r_next;
alpar@9:       /* pointer to next coefficient in the same row */
alpar@9:       NPPAIJ *c_prev;
alpar@9:       /* pointer to previous coefficient in the same column */
alpar@9:       NPPAIJ *c_next;
alpar@9:       /* pointer to next coefficient in the same column */
alpar@9: };
alpar@9: 
alpar@9: struct NPPTSE
alpar@9: {     /* transformation stack entry */
alpar@9:       int (*func)(NPP *npp, void *info);
alpar@9:       /* pointer to routine performing back transformation */
alpar@9:       void *info;
alpar@9:       /* pointer to specific info (depends on the transformation) */
alpar@9:       NPPTSE *link;
alpar@9:       /* pointer to another entry created *before* this entry */
alpar@9: };
alpar@9: 
alpar@9: struct NPPLFE
alpar@9: {     /* linear form element */
alpar@9:       int ref;
alpar@9:       /* row/column reference number */
alpar@9:       double val;
alpar@9:       /* (non-zero) coefficient value */
alpar@9:       NPPLFE *next;
alpar@9:       /* pointer to another element */
alpar@9: };
alpar@9: 
alpar@9: #define npp_create_wksp _glp_npp_create_wksp
alpar@9: NPP *npp_create_wksp(void);
alpar@9: /* create LP/MIP preprocessor workspace */
alpar@9: 
alpar@9: #define npp_insert_row _glp_npp_insert_row
alpar@9: void npp_insert_row(NPP *npp, NPPROW *row, int where);
alpar@9: /* insert row to the row list */
alpar@9: 
alpar@9: #define npp_remove_row _glp_npp_remove_row
alpar@9: void npp_remove_row(NPP *npp, NPPROW *row);
alpar@9: /* remove row from the row list */
alpar@9: 
alpar@9: #define npp_activate_row _glp_npp_activate_row
alpar@9: void npp_activate_row(NPP *npp, NPPROW *row);
alpar@9: /* make row active */
alpar@9: 
alpar@9: #define npp_deactivate_row _glp_npp_deactivate_row
alpar@9: void npp_deactivate_row(NPP *npp, NPPROW *row);
alpar@9: /* make row inactive */
alpar@9: 
alpar@9: #define npp_insert_col _glp_npp_insert_col
alpar@9: void npp_insert_col(NPP *npp, NPPCOL *col, int where);
alpar@9: /* insert column to the column list */
alpar@9: 
alpar@9: #define npp_remove_col _glp_npp_remove_col
alpar@9: void npp_remove_col(NPP *npp, NPPCOL *col);
alpar@9: /* remove column from the column list */
alpar@9: 
alpar@9: #define npp_activate_col _glp_npp_activate_col
alpar@9: void npp_activate_col(NPP *npp, NPPCOL *col);
alpar@9: /* make column active */
alpar@9: 
alpar@9: #define npp_deactivate_col _glp_npp_deactivate_col
alpar@9: void npp_deactivate_col(NPP *npp, NPPCOL *col);
alpar@9: /* make column inactive */
alpar@9: 
alpar@9: #define npp_add_row _glp_npp_add_row
alpar@9: NPPROW *npp_add_row(NPP *npp);
alpar@9: /* add new row to the current problem */
alpar@9: 
alpar@9: #define npp_add_col _glp_npp_add_col
alpar@9: NPPCOL *npp_add_col(NPP *npp);
alpar@9: /* add new column to the current problem */
alpar@9: 
alpar@9: #define npp_add_aij _glp_npp_add_aij
alpar@9: NPPAIJ *npp_add_aij(NPP *npp, NPPROW *row, NPPCOL *col, double val);
alpar@9: /* add new element to the constraint matrix */
alpar@9: 
alpar@9: #define npp_row_nnz _glp_npp_row_nnz
alpar@9: int npp_row_nnz(NPP *npp, NPPROW *row);
alpar@9: /* count number of non-zero coefficients in row */
alpar@9: 
alpar@9: #define npp_col_nnz _glp_npp_col_nnz
alpar@9: int npp_col_nnz(NPP *npp, NPPCOL *col);
alpar@9: /* count number of non-zero coefficients in column */
alpar@9: 
alpar@9: #define npp_push_tse _glp_npp_push_tse
alpar@9: void *npp_push_tse(NPP *npp, int (*func)(NPP *npp, void *info),
alpar@9:       int size);
alpar@9: /* push new entry to the transformation stack */
alpar@9: 
alpar@9: #define npp_erase_row _glp_npp_erase_row
alpar@9: void npp_erase_row(NPP *npp, NPPROW *row);
alpar@9: /* erase row content to make it empty */
alpar@9: 
alpar@9: #define npp_del_row _glp_npp_del_row
alpar@9: void npp_del_row(NPP *npp, NPPROW *row);
alpar@9: /* remove row from the current problem */
alpar@9: 
alpar@9: #define npp_del_col _glp_npp_del_col
alpar@9: void npp_del_col(NPP *npp, NPPCOL *col);
alpar@9: /* remove column from the current problem */
alpar@9: 
alpar@9: #define npp_del_aij _glp_npp_del_aij
alpar@9: void npp_del_aij(NPP *npp, NPPAIJ *aij);
alpar@9: /* remove element from the constraint matrix */
alpar@9: 
alpar@9: #define npp_load_prob _glp_npp_load_prob
alpar@9: void npp_load_prob(NPP *npp, glp_prob *orig, int names, int sol,
alpar@9:       int scaling);
alpar@9: /* load original problem into the preprocessor workspace */
alpar@9: 
alpar@9: #define npp_build_prob _glp_npp_build_prob
alpar@9: void npp_build_prob(NPP *npp, glp_prob *prob);
alpar@9: /* build resultant (preprocessed) problem */
alpar@9: 
alpar@9: #define npp_postprocess _glp_npp_postprocess
alpar@9: void npp_postprocess(NPP *npp, glp_prob *prob);
alpar@9: /* postprocess solution from the resultant problem */
alpar@9: 
alpar@9: #define npp_unload_sol _glp_npp_unload_sol
alpar@9: void npp_unload_sol(NPP *npp, glp_prob *orig);
alpar@9: /* store solution to the original problem */
alpar@9: 
alpar@9: #define npp_delete_wksp _glp_npp_delete_wksp
alpar@9: void npp_delete_wksp(NPP *npp);
alpar@9: /* delete LP/MIP preprocessor workspace */
alpar@9: 
alpar@9: #define npp_error()
alpar@9: 
alpar@9: #define npp_free_row _glp_npp_free_row
alpar@9: void npp_free_row(NPP *npp, NPPROW *p);
alpar@9: /* process free (unbounded) row */
alpar@9: 
alpar@9: #define npp_geq_row _glp_npp_geq_row
alpar@9: void npp_geq_row(NPP *npp, NPPROW *p);
alpar@9: /* process row of 'not less than' type */
alpar@9: 
alpar@9: #define npp_leq_row _glp_npp_leq_row
alpar@9: void npp_leq_row(NPP *npp, NPPROW *p);
alpar@9: /* process row of 'not greater than' type */
alpar@9: 
alpar@9: #define npp_free_col _glp_npp_free_col
alpar@9: void npp_free_col(NPP *npp, NPPCOL *q);
alpar@9: /* process free (unbounded) column */
alpar@9: 
alpar@9: #define npp_lbnd_col _glp_npp_lbnd_col
alpar@9: void npp_lbnd_col(NPP *npp, NPPCOL *q);
alpar@9: /* process column with (non-zero) lower bound */
alpar@9: 
alpar@9: #define npp_ubnd_col _glp_npp_ubnd_col
alpar@9: void npp_ubnd_col(NPP *npp, NPPCOL *q);
alpar@9: /* process column with upper bound */
alpar@9: 
alpar@9: #define npp_dbnd_col _glp_npp_dbnd_col
alpar@9: void npp_dbnd_col(NPP *npp, NPPCOL *q);
alpar@9: /* process non-negative column with upper bound */
alpar@9: 
alpar@9: #define npp_fixed_col _glp_npp_fixed_col
alpar@9: void npp_fixed_col(NPP *npp, NPPCOL *q);
alpar@9: /* process fixed column */
alpar@9: 
alpar@9: #define npp_make_equality _glp_npp_make_equality
alpar@9: int npp_make_equality(NPP *npp, NPPROW *p);
alpar@9: /* process row with almost identical bounds */
alpar@9: 
alpar@9: #define npp_make_fixed _glp_npp_make_fixed
alpar@9: int npp_make_fixed(NPP *npp, NPPCOL *q);
alpar@9: /* process column with almost identical bounds */
alpar@9: 
alpar@9: #define npp_empty_row _glp_npp_empty_row
alpar@9: int npp_empty_row(NPP *npp, NPPROW *p);
alpar@9: /* process empty row */
alpar@9: 
alpar@9: #define npp_empty_col _glp_npp_empty_col
alpar@9: int npp_empty_col(NPP *npp, NPPCOL *q);
alpar@9: /* process empty column */
alpar@9: 
alpar@9: #define npp_implied_value _glp_npp_implied_value
alpar@9: int npp_implied_value(NPP *npp, NPPCOL *q, double s);
alpar@9: /* process implied column value */
alpar@9: 
alpar@9: #define npp_eq_singlet _glp_npp_eq_singlet
alpar@9: int npp_eq_singlet(NPP *npp, NPPROW *p);
alpar@9: /* process row singleton (equality constraint) */
alpar@9: 
alpar@9: #define npp_implied_lower _glp_npp_implied_lower
alpar@9: int npp_implied_lower(NPP *npp, NPPCOL *q, double l);
alpar@9: /* process implied column lower bound */
alpar@9: 
alpar@9: #define npp_implied_upper _glp_npp_implied_upper
alpar@9: int npp_implied_upper(NPP *npp, NPPCOL *q, double u);
alpar@9: /* process implied upper bound of column */
alpar@9: 
alpar@9: #define npp_ineq_singlet _glp_npp_ineq_singlet
alpar@9: int npp_ineq_singlet(NPP *npp, NPPROW *p);
alpar@9: /* process row singleton (inequality constraint) */
alpar@9: 
alpar@9: #define npp_implied_slack _glp_npp_implied_slack
alpar@9: void npp_implied_slack(NPP *npp, NPPCOL *q);
alpar@9: /* process column singleton (implied slack variable) */
alpar@9: 
alpar@9: #define npp_implied_free _glp_npp_implied_free
alpar@9: int npp_implied_free(NPP *npp, NPPCOL *q);
alpar@9: /* process column singleton (implied free variable) */
alpar@9: 
alpar@9: #define npp_eq_doublet _glp_npp_eq_doublet
alpar@9: NPPCOL *npp_eq_doublet(NPP *npp, NPPROW *p);
alpar@9: /* process row doubleton (equality constraint) */
alpar@9: 
alpar@9: #define npp_forcing_row _glp_npp_forcing_row
alpar@9: int npp_forcing_row(NPP *npp, NPPROW *p, int at);
alpar@9: /* process forcing row */
alpar@9: 
alpar@9: #define npp_analyze_row _glp_npp_analyze_row
alpar@9: int npp_analyze_row(NPP *npp, NPPROW *p);
alpar@9: /* perform general row analysis */
alpar@9: 
alpar@9: #define npp_inactive_bound _glp_npp_inactive_bound
alpar@9: void npp_inactive_bound(NPP *npp, NPPROW *p, int which);
alpar@9: /* remove row lower/upper inactive bound */
alpar@9: 
alpar@9: #define npp_implied_bounds _glp_npp_implied_bounds
alpar@9: void npp_implied_bounds(NPP *npp, NPPROW *p);
alpar@9: /* determine implied column bounds */
alpar@9: 
alpar@9: #define npp_binarize_prob _glp_npp_binarize_prob
alpar@9: int npp_binarize_prob(NPP *npp);
alpar@9: /* binarize MIP problem */
alpar@9: 
alpar@9: #define npp_is_packing _glp_npp_is_packing
alpar@9: int npp_is_packing(NPP *npp, NPPROW *row);
alpar@9: /* test if constraint is packing inequality */
alpar@9: 
alpar@9: #define npp_hidden_packing _glp_npp_hidden_packing
alpar@9: int npp_hidden_packing(NPP *npp, NPPROW *row);
alpar@9: /* identify hidden packing inequality */
alpar@9: 
alpar@9: #define npp_implied_packing _glp_npp_implied_packing
alpar@9: int npp_implied_packing(NPP *npp, NPPROW *row, int which,
alpar@9:       NPPCOL *var[], char set[]);
alpar@9: /* identify implied packing inequality */
alpar@9: 
alpar@9: #define npp_is_covering _glp_npp_is_covering
alpar@9: int npp_is_covering(NPP *npp, NPPROW *row);
alpar@9: /* test if constraint is covering inequality */
alpar@9: 
alpar@9: #define npp_hidden_covering _glp_npp_hidden_covering
alpar@9: int npp_hidden_covering(NPP *npp, NPPROW *row);
alpar@9: /* identify hidden covering inequality */
alpar@9: 
alpar@9: #define npp_is_partitioning _glp_npp_is_partitioning
alpar@9: int npp_is_partitioning(NPP *npp, NPPROW *row);
alpar@9: /* test if constraint is partitioning equality */
alpar@9: 
alpar@9: #define npp_reduce_ineq_coef _glp_npp_reduce_ineq_coef
alpar@9: int npp_reduce_ineq_coef(NPP *npp, NPPROW *row);
alpar@9: /* reduce inequality constraint coefficients */
alpar@9: 
alpar@9: #define npp_clean_prob _glp_npp_clean_prob
alpar@9: void npp_clean_prob(NPP *npp);
alpar@9: /* perform initial LP/MIP processing */
alpar@9: 
alpar@9: #define npp_process_row _glp_npp_process_row
alpar@9: int npp_process_row(NPP *npp, NPPROW *row, int hard);
alpar@9: /* perform basic row processing */
alpar@9: 
alpar@9: #define npp_improve_bounds _glp_npp_improve_bounds
alpar@9: int npp_improve_bounds(NPP *npp, NPPROW *row, int flag);
alpar@9: /* improve current column bounds */
alpar@9: 
alpar@9: #define npp_process_col _glp_npp_process_col
alpar@9: int npp_process_col(NPP *npp, NPPCOL *col);
alpar@9: /* perform basic column processing */
alpar@9: 
alpar@9: #define npp_process_prob _glp_npp_process_prob
alpar@9: int npp_process_prob(NPP *npp, int hard);
alpar@9: /* perform basic LP/MIP processing */
alpar@9: 
alpar@9: #define npp_simplex _glp_npp_simplex
alpar@9: int npp_simplex(NPP *npp, const glp_smcp *parm);
alpar@9: /* process LP prior to applying primal/dual simplex method */
alpar@9: 
alpar@9: #define npp_integer _glp_npp_integer
alpar@9: int npp_integer(NPP *npp, const glp_iocp *parm);
alpar@9: /* process MIP prior to applying branch-and-bound method */
alpar@9: 
alpar@9: /**********************************************************************/
alpar@9: 
alpar@9: #define npp_sat_free_row _glp_npp_sat_free_row
alpar@9: void npp_sat_free_row(NPP *npp, NPPROW *p);
alpar@9: /* process free (unbounded) row */
alpar@9: 
alpar@9: #define npp_sat_fixed_col _glp_npp_sat_fixed_col
alpar@9: int npp_sat_fixed_col(NPP *npp, NPPCOL *q);
alpar@9: /* process fixed column */
alpar@9: 
alpar@9: #define npp_sat_is_bin_comb _glp_npp_sat_is_bin_comb
alpar@9: int npp_sat_is_bin_comb(NPP *npp, NPPROW *row);
alpar@9: /* test if row is binary combination */
alpar@9: 
alpar@9: #define npp_sat_num_pos_coef _glp_npp_sat_num_pos_coef
alpar@9: int npp_sat_num_pos_coef(NPP *npp, NPPROW *row);
alpar@9: /* determine number of positive coefficients */
alpar@9: 
alpar@9: #define npp_sat_num_neg_coef _glp_npp_sat_num_neg_coef
alpar@9: int npp_sat_num_neg_coef(NPP *npp, NPPROW *row);
alpar@9: /* determine number of negative coefficients */
alpar@9: 
alpar@9: #define npp_sat_is_cover_ineq _glp_npp_sat_is_cover_ineq
alpar@9: int npp_sat_is_cover_ineq(NPP *npp, NPPROW *row);
alpar@9: /* test if row is covering inequality */
alpar@9: 
alpar@9: #define npp_sat_is_pack_ineq _glp_npp_sat_is_pack_ineq
alpar@9: int npp_sat_is_pack_ineq(NPP *npp, NPPROW *row);
alpar@9: /* test if row is packing inequality */
alpar@9: 
alpar@9: #define npp_sat_is_partn_eq _glp_npp_sat_is_partn_eq
alpar@9: int npp_sat_is_partn_eq(NPP *npp, NPPROW *row);
alpar@9: /* test if row is partitioning equality */
alpar@9: 
alpar@9: #define npp_sat_reverse_row _glp_npp_sat_reverse_row
alpar@9: int npp_sat_reverse_row(NPP *npp, NPPROW *row);
alpar@9: /* multiply both sides of row by -1 */
alpar@9: 
alpar@9: #define npp_sat_split_pack _glp_npp_sat_split_pack
alpar@9: NPPROW *npp_sat_split_pack(NPP *npp, NPPROW *row, int nnn);
alpar@9: /* split packing inequality */
alpar@9: 
alpar@9: #define npp_sat_encode_pack _glp_npp_sat_encode_pack
alpar@9: void npp_sat_encode_pack(NPP *npp, NPPROW *row);
alpar@9: /* encode packing inequality */
alpar@9: 
alpar@9: typedef struct NPPLIT NPPLIT;
alpar@9: typedef struct NPPLSE NPPLSE;
alpar@9: typedef struct NPPSED NPPSED;
alpar@9: 
alpar@9: struct NPPLIT
alpar@9: {     /* literal (binary variable or its negation) */
alpar@9:       NPPCOL *col;
alpar@9:       /* pointer to binary variable; NULL means constant false */
alpar@9:       int neg;
alpar@9:       /* negation flag:
alpar@9:          0 - literal is variable (or constant false)
alpar@9:          1 - literal is negation of variable (or constant true) */
alpar@9: };
alpar@9: 
alpar@9: struct NPPLSE
alpar@9: {     /* literal set element */
alpar@9:       NPPLIT lit;
alpar@9:       /* literal */
alpar@9:       NPPLSE *next;
alpar@9:       /* pointer to another element */
alpar@9: };
alpar@9: 
alpar@9: struct NPPSED
alpar@9: {     /* summation encoding descriptor */
alpar@9:       /* this struct describes the equality
alpar@9:             x + y + z = s + 2 * c,
alpar@9:          which was encoded as CNF and included into the transformed
alpar@9:          problem; here x and y are literals, z is either a literal or
alpar@9:          constant zero, s and c are binary variables modeling, resp.,
alpar@9:          the low and high (carry) sum bits */
alpar@9:       NPPLIT x, y, z;
alpar@9:       /* literals; if z.col = NULL, z is constant zero */
alpar@9:       NPPCOL *s, *c;
alpar@9:       /* binary variables modeling the sum bits */
alpar@9: };
alpar@9: 
alpar@9: #define npp_sat_encode_sum2 _glp_npp_sat_encode_sum2
alpar@9: void npp_sat_encode_sum2(NPP *npp, NPPLSE *set, NPPSED *sed);
alpar@9: /* encode 2-bit summation */
alpar@9: 
alpar@9: #define npp_sat_encode_sum3 _glp_npp_sat_encode_sum3
alpar@9: void npp_sat_encode_sum3(NPP *npp, NPPLSE *set, NPPSED *sed);
alpar@9: /* encode 3-bit summation */
alpar@9: 
alpar@9: #define npp_sat_encode_sum_ax _glp_npp_sat_encode_sum_ax
alpar@9: int npp_sat_encode_sum_ax(NPP *npp, NPPROW *row, NPPLIT y[]);
alpar@9: /* encode linear combination of 0-1 variables */
alpar@9: 
alpar@9: #define npp_sat_normalize_clause _glp_npp_sat_normalize_clause
alpar@9: int npp_sat_normalize_clause(NPP *npp, int size, NPPLIT lit[]);
alpar@9: /* normalize clause */
alpar@9: 
alpar@9: #define npp_sat_encode_clause _glp_npp_sat_encode_clause
alpar@9: NPPROW *npp_sat_encode_clause(NPP *npp, int size, NPPLIT lit[]);
alpar@9: /* translate clause to cover inequality */
alpar@9: 
alpar@9: #define npp_sat_encode_geq _glp_npp_sat_encode_geq
alpar@9: int npp_sat_encode_geq(NPP *npp, int n, NPPLIT y[], int rhs);
alpar@9: /* encode "not less than" constraint */
alpar@9: 
alpar@9: #define npp_sat_encode_leq _glp_npp_sat_encode_leq
alpar@9: int npp_sat_encode_leq(NPP *npp, int n, NPPLIT y[], int rhs);
alpar@9: /* encode "not greater than" constraint */
alpar@9: 
alpar@9: #define npp_sat_encode_row _glp_npp_sat_encode_row
alpar@9: int npp_sat_encode_row(NPP *npp, NPPROW *row);
alpar@9: /* encode constraint (row) of general type */
alpar@9: 
alpar@9: #define npp_sat_encode_prob _glp_npp_sat_encode_prob
alpar@9: int npp_sat_encode_prob(NPP *npp);
alpar@9: /* encode 0-1 feasibility problem */
alpar@9: 
alpar@9: #endif
alpar@9: 
alpar@9: /* eof */