COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpnpp.h @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

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