COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpapi.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: 12.2 KB
Line 
1/* glpapi.h (application program interface) */
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 GLPAPI_H
26#define GLPAPI_H
27
28#define GLP_PROB_DEFINED
29typedef struct glp_prob glp_prob;
30
31#include "glpk.h"
32#include "glpavl.h"
33#include "glpbfd.h"
34
35typedef struct GLPROW GLPROW;
36typedef struct GLPCOL GLPCOL;
37typedef struct GLPAIJ GLPAIJ;
38
39#define GLP_PROB_MAGIC 0xD7D9D6C2
40
41struct glp_prob
42{     /* LP/MIP problem object */
43      int magic;
44      /* magic value used for debugging */
45      DMP *pool;
46      /* memory pool to store problem object components */
47      glp_tree *tree;
48      /* pointer to the search tree; set by the MIP solver when this
49         object is used in the tree as a core MIP object */
50      void *parms;
51      /* reserved for backward compatibility */
52      /*--------------------------------------------------------------*/
53      /* LP/MIP data */
54      char *name;
55      /* problem name (1 to 255 chars); NULL means no name is assigned
56         to the problem */
57      char *obj;
58      /* objective function name (1 to 255 chars); NULL means no name
59         is assigned to the objective function */
60      int dir;
61      /* optimization direction flag (objective "sense"):
62         GLP_MIN - minimization
63         GLP_MAX - maximization */
64      double c0;
65      /* constant term of the objective function ("shift") */
66      int m_max;
67      /* length of the array of rows (enlarged automatically) */
68      int n_max;
69      /* length of the array of columns (enlarged automatically) */
70      int m;
71      /* number of rows, 0 <= m <= m_max */
72      int n;
73      /* number of columns, 0 <= n <= n_max */
74      int nnz;
75      /* number of non-zero constraint coefficients, nnz >= 0 */
76      GLPROW **row; /* GLPROW *row[1+m_max]; */
77      /* row[i], 1 <= i <= m, is a pointer to i-th row */
78      GLPCOL **col; /* GLPCOL *col[1+n_max]; */
79      /* col[j], 1 <= j <= n, is a pointer to j-th column */
80      AVL *r_tree;
81      /* row index to find rows by their names; NULL means this index
82         does not exist */
83      AVL *c_tree;
84      /* column index to find columns by their names; NULL means this
85         index does not exist */
86      /*--------------------------------------------------------------*/
87      /* basis factorization (LP) */
88      int valid;
89      /* the factorization is valid only if this flag is set */
90      int *head; /* int head[1+m_max]; */
91      /* basis header (valid only if the factorization is valid);
92         head[i] = k is the ordinal number of auxiliary (1 <= k <= m)
93         or structural (m+1 <= k <= m+n) variable which corresponds to
94         i-th basic variable xB[i], 1 <= i <= m */
95      glp_bfcp *bfcp;
96      /* basis factorization control parameters; may be NULL */
97      BFD *bfd; /* BFD bfd[1:m,1:m]; */
98      /* basis factorization driver; may be NULL */
99      /*--------------------------------------------------------------*/
100      /* basic solution (LP) */
101      int pbs_stat;
102      /* primal basic solution status:
103         GLP_UNDEF  - primal solution is undefined
104         GLP_FEAS   - primal solution is feasible
105         GLP_INFEAS - primal solution is infeasible
106         GLP_NOFEAS - no primal feasible solution exists */
107      int dbs_stat;
108      /* dual basic solution status:
109         GLP_UNDEF  - dual solution is undefined
110         GLP_FEAS   - dual solution is feasible
111         GLP_INFEAS - dual solution is infeasible
112         GLP_NOFEAS - no dual feasible solution exists */
113      double obj_val;
114      /* objective function value */
115      int it_cnt;
116      /* simplex method iteration count; increased by one on performing
117         one simplex iteration */
118      int some;
119      /* ordinal number of some auxiliary or structural variable having
120         certain property, 0 <= some <= m+n */
121      /*--------------------------------------------------------------*/
122      /* interior-point solution (LP) */
123      int ipt_stat;
124      /* interior-point solution status:
125         GLP_UNDEF  - interior solution is undefined
126         GLP_OPT    - interior solution is optimal
127         GLP_INFEAS - interior solution is infeasible
128         GLP_NOFEAS - no feasible solution exists */
129      double ipt_obj;
130      /* objective function value */
131      /*--------------------------------------------------------------*/
132      /* integer solution (MIP) */
133      int mip_stat;
134      /* integer solution status:
135         GLP_UNDEF  - integer solution is undefined
136         GLP_OPT    - integer solution is optimal
137         GLP_FEAS   - integer solution is feasible
138         GLP_NOFEAS - no integer solution exists */
139      double mip_obj;
140      /* objective function value */
141};
142
143struct GLPROW
144{     /* LP/MIP row (auxiliary variable) */
145      int i;
146      /* ordinal number (1 to m) assigned to this row */
147      char *name;
148      /* row name (1 to 255 chars); NULL means no name is assigned to
149         this row */
150      AVLNODE *node;
151      /* pointer to corresponding node in the row index; NULL means
152         that either the row index does not exist or this row has no
153         name assigned */
154#if 1 /* 20/IX-2008 */
155      int level;
156      unsigned char origin;
157      unsigned char klass;
158#endif
159      int type;
160      /* type of the auxiliary variable:
161         GLP_FR - free variable
162         GLP_LO - variable with lower bound
163         GLP_UP - variable with upper bound
164         GLP_DB - double-bounded variable
165         GLP_FX - fixed variable */
166      double lb; /* non-scaled */
167      /* lower bound; if the row has no lower bound, lb is zero */
168      double ub; /* non-scaled */
169      /* upper bound; if the row has no upper bound, ub is zero */
170      /* if the row type is GLP_FX, ub is equal to lb */
171      GLPAIJ *ptr; /* non-scaled */
172      /* pointer to doubly linked list of constraint coefficients which
173         are placed in this row */
174      double rii;
175      /* diagonal element r[i,i] of scaling matrix R for this row;
176         if the scaling is not used, r[i,i] is 1 */
177      int stat;
178      /* status of the auxiliary variable:
179         GLP_BS - basic variable
180         GLP_NL - non-basic variable on lower bound
181         GLP_NU - non-basic variable on upper bound
182         GLP_NF - non-basic free variable
183         GLP_NS - non-basic fixed variable */
184      int bind;
185      /* if the auxiliary variable is basic, head[bind] refers to this
186         row, otherwise, bind is 0; this attribute is valid only if the
187         basis factorization is valid */
188      double prim; /* non-scaled */
189      /* primal value of the auxiliary variable in basic solution */
190      double dual; /* non-scaled */
191      /* dual value of the auxiliary variable in basic solution */
192      double pval; /* non-scaled */
193      /* primal value of the auxiliary variable in interior solution */
194      double dval; /* non-scaled */
195      /* dual value of the auxiliary variable in interior solution */
196      double mipx; /* non-scaled */
197      /* primal value of the auxiliary variable in integer solution */
198};
199
200struct GLPCOL
201{     /* LP/MIP column (structural variable) */
202      int j;
203      /* ordinal number (1 to n) assigned to this column */
204      char *name;
205      /* column name (1 to 255 chars); NULL means no name is assigned
206         to this column */
207      AVLNODE *node;
208      /* pointer to corresponding node in the column index; NULL means
209         that either the column index does not exist or the column has
210         no name assigned */
211      int kind;
212      /* kind of the structural variable:
213         GLP_CV - continuous variable
214         GLP_IV - integer or binary variable */
215      int type;
216      /* type of the structural variable:
217         GLP_FR - free variable
218         GLP_LO - variable with lower bound
219         GLP_UP - variable with upper bound
220         GLP_DB - double-bounded variable
221         GLP_FX - fixed variable */
222      double lb; /* non-scaled */
223      /* lower bound; if the column has no lower bound, lb is zero */
224      double ub; /* non-scaled */
225      /* upper bound; if the column has no upper bound, ub is zero */
226      /* if the column type is GLP_FX, ub is equal to lb */
227      double coef; /* non-scaled */
228      /* objective coefficient at the structural variable */
229      GLPAIJ *ptr; /* non-scaled */
230      /* pointer to doubly linked list of constraint coefficients which
231         are placed in this column */
232      double sjj;
233      /* diagonal element s[j,j] of scaling matrix S for this column;
234         if the scaling is not used, s[j,j] is 1 */
235      int stat;
236      /* status of the structural variable:
237         GLP_BS - basic variable
238         GLP_NL - non-basic variable on lower bound
239         GLP_NU - non-basic variable on upper bound
240         GLP_NF - non-basic free variable
241         GLP_NS - non-basic fixed variable */
242      int bind;
243      /* if the structural variable is basic, head[bind] refers to
244         this column; otherwise, bind is 0; this attribute is valid only
245         if the basis factorization is valid */
246      double prim; /* non-scaled */
247      /* primal value of the structural variable in basic solution */
248      double dual; /* non-scaled */
249      /* dual value of the structural variable in basic solution */
250      double pval; /* non-scaled */
251      /* primal value of the structural variable in interior solution */
252      double dval; /* non-scaled */
253      /* dual value of the structural variable in interior solution */
254      double mipx; /* non-scaled */
255      /* primal value of the structural variable in integer solution */
256};
257
258struct GLPAIJ
259{     /* constraint coefficient a[i,j] */
260      GLPROW *row;
261      /* pointer to row, where this coefficient is placed */
262      GLPCOL *col;
263      /* pointer to column, where this coefficient is placed */
264      double val;
265      /* numeric (non-zero) value of this coefficient */
266      GLPAIJ *r_prev;
267      /* pointer to previous coefficient in the same row */
268      GLPAIJ *r_next;
269      /* pointer to next coefficient in the same row */
270      GLPAIJ *c_prev;
271      /* pointer to previous coefficient in the same column */
272      GLPAIJ *c_next;
273      /* pointer to next coefficient in the same column */
274};
275
276void _glp_check_kkt(glp_prob *P, int sol, int cond, double *ae_max,
277      int *ae_ind, double *re_max, int *re_ind);
278/* check feasibility and optimality conditions */
279
280#define lpx_put_solution _glp_put_solution
281void lpx_put_solution(glp_prob *lp, int inval, const int *p_stat,
282      const int *d_stat, const double *obj_val, const int r_stat[],
283      const double r_prim[], const double r_dual[], const int c_stat[],
284      const double c_prim[], const double c_dual[]);
285/* store basic solution components */
286
287#define lpx_put_mip_soln _glp_put_mip_soln
288void lpx_put_mip_soln(LPX *lp, int i_stat, double row_mipx[],
289      double col_mipx[]);
290/* store mixed integer solution components */
291
292#if 1 /* 28/XI-2009 */
293int _glp_analyze_row(glp_prob *P, int len, const int ind[],
294      const double val[], int type, double rhs, double eps, int *_piv,
295      double *_x, double *_dx, double *_y, double *_dy, double *_dz);
296/* simulate one iteration of dual simplex method */
297#endif
298
299#if 1 /* 08/XII-2009 */
300void _glp_mpl_init_rand(glp_tran *tran, int seed);
301#endif
302
303#define glp_skpgen _glp_skpgen
304void glp_skpgen(int n, int r, int type, int v, int s, int a[],
305   int *b, int c[]);
306/* Pisinger's 0-1 single knapsack problem generator */
307
308#if 1 /* 28/V-2010 */
309int _glp_intopt1(glp_prob *P, const glp_iocp *parm);
310#endif
311
312#endif
313
314/* eof */
Note: See TracBrowser for help on using the repository browser.