lemon-project-template-glpk

annotate deps/glpk/src/glpnpp.h @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpnpp.h (LP/MIP preprocessor) */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9 7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9 8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9 9 * E-mail: <mao@gnu.org>.
alpar@9 10 *
alpar@9 11 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 12 * under the terms of the GNU General Public License as published by
alpar@9 13 * the Free Software Foundation, either version 3 of the License, or
alpar@9 14 * (at your option) any later version.
alpar@9 15 *
alpar@9 16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 19 * License for more details.
alpar@9 20 *
alpar@9 21 * You should have received a copy of the GNU General Public License
alpar@9 22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 23 ***********************************************************************/
alpar@9 24
alpar@9 25 #ifndef GLPNPP_H
alpar@9 26 #define GLPNPP_H
alpar@9 27
alpar@9 28 #include "glpapi.h"
alpar@9 29
alpar@9 30 typedef struct NPP NPP;
alpar@9 31 typedef struct NPPROW NPPROW;
alpar@9 32 typedef struct NPPCOL NPPCOL;
alpar@9 33 typedef struct NPPAIJ NPPAIJ;
alpar@9 34 typedef struct NPPTSE NPPTSE;
alpar@9 35 typedef struct NPPLFE NPPLFE;
alpar@9 36
alpar@9 37 struct NPP
alpar@9 38 { /* LP/MIP preprocessor workspace */
alpar@9 39 /*--------------------------------------------------------------*/
alpar@9 40 /* original problem segment */
alpar@9 41 int orig_dir;
alpar@9 42 /* optimization direction flag:
alpar@9 43 GLP_MIN - minimization
alpar@9 44 GLP_MAX - maximization */
alpar@9 45 int orig_m;
alpar@9 46 /* number of rows */
alpar@9 47 int orig_n;
alpar@9 48 /* number of columns */
alpar@9 49 int orig_nnz;
alpar@9 50 /* number of non-zero constraint coefficients */
alpar@9 51 /*--------------------------------------------------------------*/
alpar@9 52 /* transformed problem segment (always minimization) */
alpar@9 53 DMP *pool;
alpar@9 54 /* memory pool to store problem components */
alpar@9 55 char *name;
alpar@9 56 /* problem name (1 to 255 chars); NULL means no name is assigned
alpar@9 57 to the problem */
alpar@9 58 char *obj;
alpar@9 59 /* objective function name (1 to 255 chars); NULL means no name
alpar@9 60 is assigned to the objective function */
alpar@9 61 double c0;
alpar@9 62 /* constant term of the objective function */
alpar@9 63 int nrows;
alpar@9 64 /* number of rows introduced into the problem; this count
alpar@9 65 increases by one every time a new row is added and never
alpar@9 66 decreases; thus, actual number of rows may be less than nrows
alpar@9 67 due to row deletions */
alpar@9 68 int ncols;
alpar@9 69 /* number of columns introduced into the problem; this count
alpar@9 70 increases by one every time a new column is added and never
alpar@9 71 decreases; thus, actual number of column may be less than
alpar@9 72 ncols due to column deletions */
alpar@9 73 NPPROW *r_head;
alpar@9 74 /* pointer to the beginning of the row list */
alpar@9 75 NPPROW *r_tail;
alpar@9 76 /* pointer to the end of the row list */
alpar@9 77 NPPCOL *c_head;
alpar@9 78 /* pointer to the beginning of the column list */
alpar@9 79 NPPCOL *c_tail;
alpar@9 80 /* pointer to the end of the column list */
alpar@9 81 /*--------------------------------------------------------------*/
alpar@9 82 /* transformation history */
alpar@9 83 DMP *stack;
alpar@9 84 /* memory pool to store transformation entries */
alpar@9 85 NPPTSE *top;
alpar@9 86 /* pointer to most recent transformation entry */
alpar@9 87 #if 0 /* 16/XII-2009 */
alpar@9 88 int count[1+25];
alpar@9 89 /* transformation statistics */
alpar@9 90 #endif
alpar@9 91 /*--------------------------------------------------------------*/
alpar@9 92 /* resultant (preprocessed) problem segment */
alpar@9 93 int m;
alpar@9 94 /* number of rows */
alpar@9 95 int n;
alpar@9 96 /* number of columns */
alpar@9 97 int nnz;
alpar@9 98 /* number of non-zero constraint coefficients */
alpar@9 99 int *row_ref; /* int row_ref[1+m]; */
alpar@9 100 /* row_ref[i], 1 <= i <= m, is the reference number assigned to
alpar@9 101 a row, which is i-th row of the resultant problem */
alpar@9 102 int *col_ref; /* int col_ref[1+n]; */
alpar@9 103 /* col_ref[j], 1 <= j <= n, is the reference number assigned to
alpar@9 104 a column, which is j-th column of the resultant problem */
alpar@9 105 /*--------------------------------------------------------------*/
alpar@9 106 /* recovered solution segment */
alpar@9 107 int sol;
alpar@9 108 /* solution indicator:
alpar@9 109 GLP_SOL - basic solution
alpar@9 110 GLP_IPT - interior-point solution
alpar@9 111 GLP_MIP - mixed integer solution */
alpar@9 112 int scaling;
alpar@9 113 /* scaling option:
alpar@9 114 GLP_OFF - scaling is disabled
alpar@9 115 GLP_ON - scaling is enabled */
alpar@9 116 int p_stat;
alpar@9 117 /* status of primal basic solution:
alpar@9 118 GLP_UNDEF - primal solution is undefined
alpar@9 119 GLP_FEAS - primal solution is feasible
alpar@9 120 GLP_INFEAS - primal solution is infeasible
alpar@9 121 GLP_NOFEAS - no primal feasible solution exists */
alpar@9 122 int d_stat;
alpar@9 123 /* status of dual basic solution:
alpar@9 124 GLP_UNDEF - dual solution is undefined
alpar@9 125 GLP_FEAS - dual solution is feasible
alpar@9 126 GLP_INFEAS - dual solution is infeasible
alpar@9 127 GLP_NOFEAS - no dual feasible solution exists */
alpar@9 128 int t_stat;
alpar@9 129 /* status of interior-point solution:
alpar@9 130 GLP_UNDEF - interior solution is undefined
alpar@9 131 GLP_OPT - interior solution is optimal */
alpar@9 132 int i_stat;
alpar@9 133 /* status of mixed integer solution:
alpar@9 134 GLP_UNDEF - integer solution is undefined
alpar@9 135 GLP_OPT - integer solution is optimal
alpar@9 136 GLP_FEAS - integer solution is feasible
alpar@9 137 GLP_NOFEAS - no integer solution exists */
alpar@9 138 char *r_stat; /* char r_stat[1+nrows]; */
alpar@9 139 /* r_stat[i], 1 <= i <= nrows, is status of i-th row:
alpar@9 140 GLP_BS - inactive constraint
alpar@9 141 GLP_NL - active constraint on lower bound
alpar@9 142 GLP_NU - active constraint on upper bound
alpar@9 143 GLP_NF - active free row
alpar@9 144 GLP_NS - active equality constraint */
alpar@9 145 char *c_stat; /* char c_stat[1+nrows]; */
alpar@9 146 /* c_stat[j], 1 <= j <= nrows, is status of j-th column:
alpar@9 147 GLP_BS - basic variable
alpar@9 148 GLP_NL - non-basic variable on lower bound
alpar@9 149 GLP_NU - non-basic variable on upper bound
alpar@9 150 GLP_NF - non-basic free variable
alpar@9 151 GLP_NS - non-basic fixed variable */
alpar@9 152 double *r_pi; /* double r_pi[1+nrows]; */
alpar@9 153 /* r_pi[i], 1 <= i <= nrows, is Lagrange multiplier (dual value)
alpar@9 154 for i-th row (constraint) */
alpar@9 155 double *c_value; /* double c_value[1+ncols]; */
alpar@9 156 /* c_value[j], 1 <= j <= ncols, is primal value of j-th column
alpar@9 157 (structural variable) */
alpar@9 158 };
alpar@9 159
alpar@9 160 struct NPPROW
alpar@9 161 { /* row (constraint) */
alpar@9 162 int i;
alpar@9 163 /* reference number assigned to the row, 1 <= i <= nrows */
alpar@9 164 char *name;
alpar@9 165 /* row name (1 to 255 chars); NULL means no name is assigned to
alpar@9 166 the row */
alpar@9 167 double lb;
alpar@9 168 /* lower bound; -DBL_MAX means the row has no lower bound */
alpar@9 169 double ub;
alpar@9 170 /* upper bound; +DBL_MAX means the row has no upper bound */
alpar@9 171 NPPAIJ *ptr;
alpar@9 172 /* pointer to the linked list of constraint coefficients */
alpar@9 173 int temp;
alpar@9 174 /* working field used by preprocessor routines */
alpar@9 175 NPPROW *prev;
alpar@9 176 /* pointer to previous row in the row list */
alpar@9 177 NPPROW *next;
alpar@9 178 /* pointer to next row in the row list */
alpar@9 179 };
alpar@9 180
alpar@9 181 struct NPPCOL
alpar@9 182 { /* column (variable) */
alpar@9 183 int j;
alpar@9 184 /* reference number assigned to the column, 1 <= j <= ncols */
alpar@9 185 char *name;
alpar@9 186 /* column name (1 to 255 chars); NULL means no name is assigned
alpar@9 187 to the column */
alpar@9 188 char is_int;
alpar@9 189 /* 0 means continuous variable; 1 means integer variable */
alpar@9 190 double lb;
alpar@9 191 /* lower bound; -DBL_MAX means the column has no lower bound */
alpar@9 192 double ub;
alpar@9 193 /* upper bound; +DBL_MAX means the column has no upper bound */
alpar@9 194 double coef;
alpar@9 195 /* objective coefficient */
alpar@9 196 NPPAIJ *ptr;
alpar@9 197 /* pointer to the linked list of constraint coefficients */
alpar@9 198 int temp;
alpar@9 199 /* working field used by preprocessor routines */
alpar@9 200 #if 1 /* 28/XII-2009 */
alpar@9 201 union
alpar@9 202 { double ll;
alpar@9 203 /* implied column lower bound */
alpar@9 204 int pos;
alpar@9 205 /* vertex ordinal number corresponding to this binary column
alpar@9 206 in the conflict graph (0, if the vertex does not exist) */
alpar@9 207 } ll;
alpar@9 208 union
alpar@9 209 { double uu;
alpar@9 210 /* implied column upper bound */
alpar@9 211 int neg;
alpar@9 212 /* vertex ordinal number corresponding to complement of this
alpar@9 213 binary column in the conflict graph (0, if the vertex does
alpar@9 214 not exist) */
alpar@9 215 } uu;
alpar@9 216 #endif
alpar@9 217 NPPCOL *prev;
alpar@9 218 /* pointer to previous column in the column list */
alpar@9 219 NPPCOL *next;
alpar@9 220 /* pointer to next column in the column list */
alpar@9 221 };
alpar@9 222
alpar@9 223 struct NPPAIJ
alpar@9 224 { /* constraint coefficient */
alpar@9 225 NPPROW *row;
alpar@9 226 /* pointer to corresponding row */
alpar@9 227 NPPCOL *col;
alpar@9 228 /* pointer to corresponding column */
alpar@9 229 double val;
alpar@9 230 /* (non-zero) coefficient value */
alpar@9 231 NPPAIJ *r_prev;
alpar@9 232 /* pointer to previous coefficient in the same row */
alpar@9 233 NPPAIJ *r_next;
alpar@9 234 /* pointer to next coefficient in the same row */
alpar@9 235 NPPAIJ *c_prev;
alpar@9 236 /* pointer to previous coefficient in the same column */
alpar@9 237 NPPAIJ *c_next;
alpar@9 238 /* pointer to next coefficient in the same column */
alpar@9 239 };
alpar@9 240
alpar@9 241 struct NPPTSE
alpar@9 242 { /* transformation stack entry */
alpar@9 243 int (*func)(NPP *npp, void *info);
alpar@9 244 /* pointer to routine performing back transformation */
alpar@9 245 void *info;
alpar@9 246 /* pointer to specific info (depends on the transformation) */
alpar@9 247 NPPTSE *link;
alpar@9 248 /* pointer to another entry created *before* this entry */
alpar@9 249 };
alpar@9 250
alpar@9 251 struct NPPLFE
alpar@9 252 { /* linear form element */
alpar@9 253 int ref;
alpar@9 254 /* row/column reference number */
alpar@9 255 double val;
alpar@9 256 /* (non-zero) coefficient value */
alpar@9 257 NPPLFE *next;
alpar@9 258 /* pointer to another element */
alpar@9 259 };
alpar@9 260
alpar@9 261 #define npp_create_wksp _glp_npp_create_wksp
alpar@9 262 NPP *npp_create_wksp(void);
alpar@9 263 /* create LP/MIP preprocessor workspace */
alpar@9 264
alpar@9 265 #define npp_insert_row _glp_npp_insert_row
alpar@9 266 void npp_insert_row(NPP *npp, NPPROW *row, int where);
alpar@9 267 /* insert row to the row list */
alpar@9 268
alpar@9 269 #define npp_remove_row _glp_npp_remove_row
alpar@9 270 void npp_remove_row(NPP *npp, NPPROW *row);
alpar@9 271 /* remove row from the row list */
alpar@9 272
alpar@9 273 #define npp_activate_row _glp_npp_activate_row
alpar@9 274 void npp_activate_row(NPP *npp, NPPROW *row);
alpar@9 275 /* make row active */
alpar@9 276
alpar@9 277 #define npp_deactivate_row _glp_npp_deactivate_row
alpar@9 278 void npp_deactivate_row(NPP *npp, NPPROW *row);
alpar@9 279 /* make row inactive */
alpar@9 280
alpar@9 281 #define npp_insert_col _glp_npp_insert_col
alpar@9 282 void npp_insert_col(NPP *npp, NPPCOL *col, int where);
alpar@9 283 /* insert column to the column list */
alpar@9 284
alpar@9 285 #define npp_remove_col _glp_npp_remove_col
alpar@9 286 void npp_remove_col(NPP *npp, NPPCOL *col);
alpar@9 287 /* remove column from the column list */
alpar@9 288
alpar@9 289 #define npp_activate_col _glp_npp_activate_col
alpar@9 290 void npp_activate_col(NPP *npp, NPPCOL *col);
alpar@9 291 /* make column active */
alpar@9 292
alpar@9 293 #define npp_deactivate_col _glp_npp_deactivate_col
alpar@9 294 void npp_deactivate_col(NPP *npp, NPPCOL *col);
alpar@9 295 /* make column inactive */
alpar@9 296
alpar@9 297 #define npp_add_row _glp_npp_add_row
alpar@9 298 NPPROW *npp_add_row(NPP *npp);
alpar@9 299 /* add new row to the current problem */
alpar@9 300
alpar@9 301 #define npp_add_col _glp_npp_add_col
alpar@9 302 NPPCOL *npp_add_col(NPP *npp);
alpar@9 303 /* add new column to the current problem */
alpar@9 304
alpar@9 305 #define npp_add_aij _glp_npp_add_aij
alpar@9 306 NPPAIJ *npp_add_aij(NPP *npp, NPPROW *row, NPPCOL *col, double val);
alpar@9 307 /* add new element to the constraint matrix */
alpar@9 308
alpar@9 309 #define npp_row_nnz _glp_npp_row_nnz
alpar@9 310 int npp_row_nnz(NPP *npp, NPPROW *row);
alpar@9 311 /* count number of non-zero coefficients in row */
alpar@9 312
alpar@9 313 #define npp_col_nnz _glp_npp_col_nnz
alpar@9 314 int npp_col_nnz(NPP *npp, NPPCOL *col);
alpar@9 315 /* count number of non-zero coefficients in column */
alpar@9 316
alpar@9 317 #define npp_push_tse _glp_npp_push_tse
alpar@9 318 void *npp_push_tse(NPP *npp, int (*func)(NPP *npp, void *info),
alpar@9 319 int size);
alpar@9 320 /* push new entry to the transformation stack */
alpar@9 321
alpar@9 322 #define npp_erase_row _glp_npp_erase_row
alpar@9 323 void npp_erase_row(NPP *npp, NPPROW *row);
alpar@9 324 /* erase row content to make it empty */
alpar@9 325
alpar@9 326 #define npp_del_row _glp_npp_del_row
alpar@9 327 void npp_del_row(NPP *npp, NPPROW *row);
alpar@9 328 /* remove row from the current problem */
alpar@9 329
alpar@9 330 #define npp_del_col _glp_npp_del_col
alpar@9 331 void npp_del_col(NPP *npp, NPPCOL *col);
alpar@9 332 /* remove column from the current problem */
alpar@9 333
alpar@9 334 #define npp_del_aij _glp_npp_del_aij
alpar@9 335 void npp_del_aij(NPP *npp, NPPAIJ *aij);
alpar@9 336 /* remove element from the constraint matrix */
alpar@9 337
alpar@9 338 #define npp_load_prob _glp_npp_load_prob
alpar@9 339 void npp_load_prob(NPP *npp, glp_prob *orig, int names, int sol,
alpar@9 340 int scaling);
alpar@9 341 /* load original problem into the preprocessor workspace */
alpar@9 342
alpar@9 343 #define npp_build_prob _glp_npp_build_prob
alpar@9 344 void npp_build_prob(NPP *npp, glp_prob *prob);
alpar@9 345 /* build resultant (preprocessed) problem */
alpar@9 346
alpar@9 347 #define npp_postprocess _glp_npp_postprocess
alpar@9 348 void npp_postprocess(NPP *npp, glp_prob *prob);
alpar@9 349 /* postprocess solution from the resultant problem */
alpar@9 350
alpar@9 351 #define npp_unload_sol _glp_npp_unload_sol
alpar@9 352 void npp_unload_sol(NPP *npp, glp_prob *orig);
alpar@9 353 /* store solution to the original problem */
alpar@9 354
alpar@9 355 #define npp_delete_wksp _glp_npp_delete_wksp
alpar@9 356 void npp_delete_wksp(NPP *npp);
alpar@9 357 /* delete LP/MIP preprocessor workspace */
alpar@9 358
alpar@9 359 #define npp_error()
alpar@9 360
alpar@9 361 #define npp_free_row _glp_npp_free_row
alpar@9 362 void npp_free_row(NPP *npp, NPPROW *p);
alpar@9 363 /* process free (unbounded) row */
alpar@9 364
alpar@9 365 #define npp_geq_row _glp_npp_geq_row
alpar@9 366 void npp_geq_row(NPP *npp, NPPROW *p);
alpar@9 367 /* process row of 'not less than' type */
alpar@9 368
alpar@9 369 #define npp_leq_row _glp_npp_leq_row
alpar@9 370 void npp_leq_row(NPP *npp, NPPROW *p);
alpar@9 371 /* process row of 'not greater than' type */
alpar@9 372
alpar@9 373 #define npp_free_col _glp_npp_free_col
alpar@9 374 void npp_free_col(NPP *npp, NPPCOL *q);
alpar@9 375 /* process free (unbounded) column */
alpar@9 376
alpar@9 377 #define npp_lbnd_col _glp_npp_lbnd_col
alpar@9 378 void npp_lbnd_col(NPP *npp, NPPCOL *q);
alpar@9 379 /* process column with (non-zero) lower bound */
alpar@9 380
alpar@9 381 #define npp_ubnd_col _glp_npp_ubnd_col
alpar@9 382 void npp_ubnd_col(NPP *npp, NPPCOL *q);
alpar@9 383 /* process column with upper bound */
alpar@9 384
alpar@9 385 #define npp_dbnd_col _glp_npp_dbnd_col
alpar@9 386 void npp_dbnd_col(NPP *npp, NPPCOL *q);
alpar@9 387 /* process non-negative column with upper bound */
alpar@9 388
alpar@9 389 #define npp_fixed_col _glp_npp_fixed_col
alpar@9 390 void npp_fixed_col(NPP *npp, NPPCOL *q);
alpar@9 391 /* process fixed column */
alpar@9 392
alpar@9 393 #define npp_make_equality _glp_npp_make_equality
alpar@9 394 int npp_make_equality(NPP *npp, NPPROW *p);
alpar@9 395 /* process row with almost identical bounds */
alpar@9 396
alpar@9 397 #define npp_make_fixed _glp_npp_make_fixed
alpar@9 398 int npp_make_fixed(NPP *npp, NPPCOL *q);
alpar@9 399 /* process column with almost identical bounds */
alpar@9 400
alpar@9 401 #define npp_empty_row _glp_npp_empty_row
alpar@9 402 int npp_empty_row(NPP *npp, NPPROW *p);
alpar@9 403 /* process empty row */
alpar@9 404
alpar@9 405 #define npp_empty_col _glp_npp_empty_col
alpar@9 406 int npp_empty_col(NPP *npp, NPPCOL *q);
alpar@9 407 /* process empty column */
alpar@9 408
alpar@9 409 #define npp_implied_value _glp_npp_implied_value
alpar@9 410 int npp_implied_value(NPP *npp, NPPCOL *q, double s);
alpar@9 411 /* process implied column value */
alpar@9 412
alpar@9 413 #define npp_eq_singlet _glp_npp_eq_singlet
alpar@9 414 int npp_eq_singlet(NPP *npp, NPPROW *p);
alpar@9 415 /* process row singleton (equality constraint) */
alpar@9 416
alpar@9 417 #define npp_implied_lower _glp_npp_implied_lower
alpar@9 418 int npp_implied_lower(NPP *npp, NPPCOL *q, double l);
alpar@9 419 /* process implied column lower bound */
alpar@9 420
alpar@9 421 #define npp_implied_upper _glp_npp_implied_upper
alpar@9 422 int npp_implied_upper(NPP *npp, NPPCOL *q, double u);
alpar@9 423 /* process implied upper bound of column */
alpar@9 424
alpar@9 425 #define npp_ineq_singlet _glp_npp_ineq_singlet
alpar@9 426 int npp_ineq_singlet(NPP *npp, NPPROW *p);
alpar@9 427 /* process row singleton (inequality constraint) */
alpar@9 428
alpar@9 429 #define npp_implied_slack _glp_npp_implied_slack
alpar@9 430 void npp_implied_slack(NPP *npp, NPPCOL *q);
alpar@9 431 /* process column singleton (implied slack variable) */
alpar@9 432
alpar@9 433 #define npp_implied_free _glp_npp_implied_free
alpar@9 434 int npp_implied_free(NPP *npp, NPPCOL *q);
alpar@9 435 /* process column singleton (implied free variable) */
alpar@9 436
alpar@9 437 #define npp_eq_doublet _glp_npp_eq_doublet
alpar@9 438 NPPCOL *npp_eq_doublet(NPP *npp, NPPROW *p);
alpar@9 439 /* process row doubleton (equality constraint) */
alpar@9 440
alpar@9 441 #define npp_forcing_row _glp_npp_forcing_row
alpar@9 442 int npp_forcing_row(NPP *npp, NPPROW *p, int at);
alpar@9 443 /* process forcing row */
alpar@9 444
alpar@9 445 #define npp_analyze_row _glp_npp_analyze_row
alpar@9 446 int npp_analyze_row(NPP *npp, NPPROW *p);
alpar@9 447 /* perform general row analysis */
alpar@9 448
alpar@9 449 #define npp_inactive_bound _glp_npp_inactive_bound
alpar@9 450 void npp_inactive_bound(NPP *npp, NPPROW *p, int which);
alpar@9 451 /* remove row lower/upper inactive bound */
alpar@9 452
alpar@9 453 #define npp_implied_bounds _glp_npp_implied_bounds
alpar@9 454 void npp_implied_bounds(NPP *npp, NPPROW *p);
alpar@9 455 /* determine implied column bounds */
alpar@9 456
alpar@9 457 #define npp_binarize_prob _glp_npp_binarize_prob
alpar@9 458 int npp_binarize_prob(NPP *npp);
alpar@9 459 /* binarize MIP problem */
alpar@9 460
alpar@9 461 #define npp_is_packing _glp_npp_is_packing
alpar@9 462 int npp_is_packing(NPP *npp, NPPROW *row);
alpar@9 463 /* test if constraint is packing inequality */
alpar@9 464
alpar@9 465 #define npp_hidden_packing _glp_npp_hidden_packing
alpar@9 466 int npp_hidden_packing(NPP *npp, NPPROW *row);
alpar@9 467 /* identify hidden packing inequality */
alpar@9 468
alpar@9 469 #define npp_implied_packing _glp_npp_implied_packing
alpar@9 470 int npp_implied_packing(NPP *npp, NPPROW *row, int which,
alpar@9 471 NPPCOL *var[], char set[]);
alpar@9 472 /* identify implied packing inequality */
alpar@9 473
alpar@9 474 #define npp_is_covering _glp_npp_is_covering
alpar@9 475 int npp_is_covering(NPP *npp, NPPROW *row);
alpar@9 476 /* test if constraint is covering inequality */
alpar@9 477
alpar@9 478 #define npp_hidden_covering _glp_npp_hidden_covering
alpar@9 479 int npp_hidden_covering(NPP *npp, NPPROW *row);
alpar@9 480 /* identify hidden covering inequality */
alpar@9 481
alpar@9 482 #define npp_is_partitioning _glp_npp_is_partitioning
alpar@9 483 int npp_is_partitioning(NPP *npp, NPPROW *row);
alpar@9 484 /* test if constraint is partitioning equality */
alpar@9 485
alpar@9 486 #define npp_reduce_ineq_coef _glp_npp_reduce_ineq_coef
alpar@9 487 int npp_reduce_ineq_coef(NPP *npp, NPPROW *row);
alpar@9 488 /* reduce inequality constraint coefficients */
alpar@9 489
alpar@9 490 #define npp_clean_prob _glp_npp_clean_prob
alpar@9 491 void npp_clean_prob(NPP *npp);
alpar@9 492 /* perform initial LP/MIP processing */
alpar@9 493
alpar@9 494 #define npp_process_row _glp_npp_process_row
alpar@9 495 int npp_process_row(NPP *npp, NPPROW *row, int hard);
alpar@9 496 /* perform basic row processing */
alpar@9 497
alpar@9 498 #define npp_improve_bounds _glp_npp_improve_bounds
alpar@9 499 int npp_improve_bounds(NPP *npp, NPPROW *row, int flag);
alpar@9 500 /* improve current column bounds */
alpar@9 501
alpar@9 502 #define npp_process_col _glp_npp_process_col
alpar@9 503 int npp_process_col(NPP *npp, NPPCOL *col);
alpar@9 504 /* perform basic column processing */
alpar@9 505
alpar@9 506 #define npp_process_prob _glp_npp_process_prob
alpar@9 507 int npp_process_prob(NPP *npp, int hard);
alpar@9 508 /* perform basic LP/MIP processing */
alpar@9 509
alpar@9 510 #define npp_simplex _glp_npp_simplex
alpar@9 511 int npp_simplex(NPP *npp, const glp_smcp *parm);
alpar@9 512 /* process LP prior to applying primal/dual simplex method */
alpar@9 513
alpar@9 514 #define npp_integer _glp_npp_integer
alpar@9 515 int npp_integer(NPP *npp, const glp_iocp *parm);
alpar@9 516 /* process MIP prior to applying branch-and-bound method */
alpar@9 517
alpar@9 518 /**********************************************************************/
alpar@9 519
alpar@9 520 #define npp_sat_free_row _glp_npp_sat_free_row
alpar@9 521 void npp_sat_free_row(NPP *npp, NPPROW *p);
alpar@9 522 /* process free (unbounded) row */
alpar@9 523
alpar@9 524 #define npp_sat_fixed_col _glp_npp_sat_fixed_col
alpar@9 525 int npp_sat_fixed_col(NPP *npp, NPPCOL *q);
alpar@9 526 /* process fixed column */
alpar@9 527
alpar@9 528 #define npp_sat_is_bin_comb _glp_npp_sat_is_bin_comb
alpar@9 529 int npp_sat_is_bin_comb(NPP *npp, NPPROW *row);
alpar@9 530 /* test if row is binary combination */
alpar@9 531
alpar@9 532 #define npp_sat_num_pos_coef _glp_npp_sat_num_pos_coef
alpar@9 533 int npp_sat_num_pos_coef(NPP *npp, NPPROW *row);
alpar@9 534 /* determine number of positive coefficients */
alpar@9 535
alpar@9 536 #define npp_sat_num_neg_coef _glp_npp_sat_num_neg_coef
alpar@9 537 int npp_sat_num_neg_coef(NPP *npp, NPPROW *row);
alpar@9 538 /* determine number of negative coefficients */
alpar@9 539
alpar@9 540 #define npp_sat_is_cover_ineq _glp_npp_sat_is_cover_ineq
alpar@9 541 int npp_sat_is_cover_ineq(NPP *npp, NPPROW *row);
alpar@9 542 /* test if row is covering inequality */
alpar@9 543
alpar@9 544 #define npp_sat_is_pack_ineq _glp_npp_sat_is_pack_ineq
alpar@9 545 int npp_sat_is_pack_ineq(NPP *npp, NPPROW *row);
alpar@9 546 /* test if row is packing inequality */
alpar@9 547
alpar@9 548 #define npp_sat_is_partn_eq _glp_npp_sat_is_partn_eq
alpar@9 549 int npp_sat_is_partn_eq(NPP *npp, NPPROW *row);
alpar@9 550 /* test if row is partitioning equality */
alpar@9 551
alpar@9 552 #define npp_sat_reverse_row _glp_npp_sat_reverse_row
alpar@9 553 int npp_sat_reverse_row(NPP *npp, NPPROW *row);
alpar@9 554 /* multiply both sides of row by -1 */
alpar@9 555
alpar@9 556 #define npp_sat_split_pack _glp_npp_sat_split_pack
alpar@9 557 NPPROW *npp_sat_split_pack(NPP *npp, NPPROW *row, int nnn);
alpar@9 558 /* split packing inequality */
alpar@9 559
alpar@9 560 #define npp_sat_encode_pack _glp_npp_sat_encode_pack
alpar@9 561 void npp_sat_encode_pack(NPP *npp, NPPROW *row);
alpar@9 562 /* encode packing inequality */
alpar@9 563
alpar@9 564 typedef struct NPPLIT NPPLIT;
alpar@9 565 typedef struct NPPLSE NPPLSE;
alpar@9 566 typedef struct NPPSED NPPSED;
alpar@9 567
alpar@9 568 struct NPPLIT
alpar@9 569 { /* literal (binary variable or its negation) */
alpar@9 570 NPPCOL *col;
alpar@9 571 /* pointer to binary variable; NULL means constant false */
alpar@9 572 int neg;
alpar@9 573 /* negation flag:
alpar@9 574 0 - literal is variable (or constant false)
alpar@9 575 1 - literal is negation of variable (or constant true) */
alpar@9 576 };
alpar@9 577
alpar@9 578 struct NPPLSE
alpar@9 579 { /* literal set element */
alpar@9 580 NPPLIT lit;
alpar@9 581 /* literal */
alpar@9 582 NPPLSE *next;
alpar@9 583 /* pointer to another element */
alpar@9 584 };
alpar@9 585
alpar@9 586 struct NPPSED
alpar@9 587 { /* summation encoding descriptor */
alpar@9 588 /* this struct describes the equality
alpar@9 589 x + y + z = s + 2 * c,
alpar@9 590 which was encoded as CNF and included into the transformed
alpar@9 591 problem; here x and y are literals, z is either a literal or
alpar@9 592 constant zero, s and c are binary variables modeling, resp.,
alpar@9 593 the low and high (carry) sum bits */
alpar@9 594 NPPLIT x, y, z;
alpar@9 595 /* literals; if z.col = NULL, z is constant zero */
alpar@9 596 NPPCOL *s, *c;
alpar@9 597 /* binary variables modeling the sum bits */
alpar@9 598 };
alpar@9 599
alpar@9 600 #define npp_sat_encode_sum2 _glp_npp_sat_encode_sum2
alpar@9 601 void npp_sat_encode_sum2(NPP *npp, NPPLSE *set, NPPSED *sed);
alpar@9 602 /* encode 2-bit summation */
alpar@9 603
alpar@9 604 #define npp_sat_encode_sum3 _glp_npp_sat_encode_sum3
alpar@9 605 void npp_sat_encode_sum3(NPP *npp, NPPLSE *set, NPPSED *sed);
alpar@9 606 /* encode 3-bit summation */
alpar@9 607
alpar@9 608 #define npp_sat_encode_sum_ax _glp_npp_sat_encode_sum_ax
alpar@9 609 int npp_sat_encode_sum_ax(NPP *npp, NPPROW *row, NPPLIT y[]);
alpar@9 610 /* encode linear combination of 0-1 variables */
alpar@9 611
alpar@9 612 #define npp_sat_normalize_clause _glp_npp_sat_normalize_clause
alpar@9 613 int npp_sat_normalize_clause(NPP *npp, int size, NPPLIT lit[]);
alpar@9 614 /* normalize clause */
alpar@9 615
alpar@9 616 #define npp_sat_encode_clause _glp_npp_sat_encode_clause
alpar@9 617 NPPROW *npp_sat_encode_clause(NPP *npp, int size, NPPLIT lit[]);
alpar@9 618 /* translate clause to cover inequality */
alpar@9 619
alpar@9 620 #define npp_sat_encode_geq _glp_npp_sat_encode_geq
alpar@9 621 int npp_sat_encode_geq(NPP *npp, int n, NPPLIT y[], int rhs);
alpar@9 622 /* encode "not less than" constraint */
alpar@9 623
alpar@9 624 #define npp_sat_encode_leq _glp_npp_sat_encode_leq
alpar@9 625 int npp_sat_encode_leq(NPP *npp, int n, NPPLIT y[], int rhs);
alpar@9 626 /* encode "not greater than" constraint */
alpar@9 627
alpar@9 628 #define npp_sat_encode_row _glp_npp_sat_encode_row
alpar@9 629 int npp_sat_encode_row(NPP *npp, NPPROW *row);
alpar@9 630 /* encode constraint (row) of general type */
alpar@9 631
alpar@9 632 #define npp_sat_encode_prob _glp_npp_sat_encode_prob
alpar@9 633 int npp_sat_encode_prob(NPP *npp);
alpar@9 634 /* encode 0-1 feasibility problem */
alpar@9 635
alpar@9 636 #endif
alpar@9 637
alpar@9 638 /* eof */