COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpios.h @ 2:4c8956a7bdf4

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

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 21.9 KB
Line 
1/* glpios.h (integer optimization suite) */
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 GLPIOS_H
26#define GLPIOS_H
27
28#define GLP_TREE_DEFINED
29typedef struct glp_tree glp_tree;
30
31#include "glpapi.h"
32
33typedef struct IOSLOT IOSLOT;
34typedef struct IOSNPD IOSNPD;
35typedef struct IOSBND IOSBND;
36typedef struct IOSTAT IOSTAT;
37typedef struct IOSROW IOSROW;
38typedef struct IOSAIJ IOSAIJ;
39typedef struct IOSPOOL IOSPOOL;
40typedef struct IOSCUT IOSCUT;
41
42struct glp_tree
43{     /* branch-and-bound tree */
44      int magic;
45      /* magic value used for debugging */
46      DMP *pool;
47      /* memory pool to store all IOS components */
48      int n;
49      /* number of columns (variables) */
50      /*--------------------------------------------------------------*/
51      /* problem components corresponding to the original MIP and its
52         LP relaxation (used to restore the original problem object on
53         exit from the solver) */
54      int orig_m;
55      /* number of rows */
56      unsigned char *orig_type; /* uchar orig_type[1+orig_m+n]; */
57      /* types of all variables */
58      double *orig_lb; /* double orig_lb[1+orig_m+n]; */
59      /* lower bounds of all variables */
60      double *orig_ub; /* double orig_ub[1+orig_m+n]; */
61      /* upper bounds of all variables */
62      unsigned char *orig_stat; /* uchar orig_stat[1+orig_m+n]; */
63      /* statuses of all variables */
64      double *orig_prim; /* double orig_prim[1+orig_m+n]; */
65      /* primal values of all variables */
66      double *orig_dual; /* double orig_dual[1+orig_m+n]; */
67      /* dual values of all variables */
68      double orig_obj;
69      /* optimal objective value for LP relaxation */
70      /*--------------------------------------------------------------*/
71      /* branch-and-bound tree */
72      int nslots;
73      /* length of the array of slots (enlarged automatically) */
74      int avail;
75      /* index of the first free slot; 0 means all slots are in use */
76      IOSLOT *slot; /* IOSLOT slot[1+nslots]; */
77      /* array of slots:
78         slot[0] is not used;
79         slot[p], 1 <= p <= nslots, either contains a pointer to some
80         node of the branch-and-bound tree, in which case p is used on
81         API level as the reference number of corresponding subproblem,
82         or is free; all free slots are linked into single linked list;
83         slot[1] always contains a pointer to the root node (it is free
84         only if the tree is empty) */
85      IOSNPD *head;
86      /* pointer to the head of the active list */
87      IOSNPD *tail;
88      /* pointer to the tail of the active list */
89      /* the active list is a doubly linked list of active subproblems
90         which correspond to leaves of the tree; all subproblems in the
91         active list are ordered chronologically (each a new subproblem
92         is always added to the tail of the list) */
93      int a_cnt;
94      /* current number of active nodes (including the current one) */
95      int n_cnt;
96      /* current number of all (active and inactive) nodes */
97      int t_cnt;
98      /* total number of nodes including those which have been already
99         removed from the tree; this count is increased by one whenever
100         a new node is created and never decreased */
101      /*--------------------------------------------------------------*/
102      /* problem components corresponding to the root subproblem */
103      int root_m;
104      /* number of rows */
105      unsigned char *root_type; /* uchar root_type[1+root_m+n]; */
106      /* types of all variables */
107      double *root_lb; /* double root_lb[1+root_m+n]; */
108      /* lower bounds of all variables */
109      double *root_ub; /* double root_ub[1+root_m+n]; */
110      /* upper bounds of all variables */
111      unsigned char *root_stat; /* uchar root_stat[1+root_m+n]; */
112      /* statuses of all variables */
113      /*--------------------------------------------------------------*/
114      /* current subproblem and its LP relaxation */
115      IOSNPD *curr;
116      /* pointer to the current subproblem (which can be only active);
117         NULL means the current subproblem does not exist */
118      glp_prob *mip;
119      /* original problem object passed to the solver; if the current
120         subproblem exists, its LP segment corresponds to LP relaxation
121         of the current subproblem; if the current subproblem does not
122         exist, its LP segment corresponds to LP relaxation of the root
123         subproblem (note that the root subproblem may differ from the
124         original MIP, because it may be preprocessed and/or may have
125         additional rows) */
126      unsigned char *non_int; /* uchar non_int[1+n]; */
127      /* these column flags are set each time when LP relaxation of the
128         current subproblem has been solved;
129         non_int[0] is not used;
130         non_int[j], 1 <= j <= n, is j-th column flag; if this flag is
131         set, corresponding variable is required to be integer, but its
132         value in basic solution is fractional */
133      /*--------------------------------------------------------------*/
134      /* problem components corresponding to the parent (predecessor)
135         subproblem for the current subproblem; used to inspect changes
136         on freezing the current subproblem */
137      int pred_m;
138      /* number of rows */
139      int pred_max;
140      /* length of the following four arrays (enlarged automatically),
141         pred_max >= pred_m + n */
142      unsigned char *pred_type; /* uchar pred_type[1+pred_m+n]; */
143      /* types of all variables */
144      double *pred_lb; /* double pred_lb[1+pred_m+n]; */
145      /* lower bounds of all variables */
146      double *pred_ub; /* double pred_ub[1+pred_m+n]; */
147      /* upper bounds of all variables */
148      unsigned char *pred_stat; /* uchar pred_stat[1+pred_m+n]; */
149      /* statuses of all variables */
150      /****************************************************************/
151      /* built-in cut generators segment */
152      IOSPOOL *local;
153      /* local cut pool */
154      void *mir_gen;
155      /* pointer to working area used by the MIR cut generator */
156      void *clq_gen;
157      /* pointer to working area used by the clique cut generator */
158      /*--------------------------------------------------------------*/
159      void *pcost;
160      /* pointer to working area used on pseudocost branching */
161      int *iwrk; /* int iwrk[1+n]; */
162      /* working array */
163      double *dwrk; /* double dwrk[1+n]; */
164      /* working array */
165      /*--------------------------------------------------------------*/
166      /* control parameters and statistics */
167      const glp_iocp *parm;
168      /* copy of control parameters passed to the solver */
169      glp_long tm_beg;
170      /* starting time of the search, in seconds; the total time of the
171         search is the difference between xtime() and tm_beg */
172      glp_long tm_lag;
173      /* the most recent time, in seconds, at which the progress of the
174         the search was displayed */
175      int sol_cnt;
176      /* number of integer feasible solutions found */
177      /*--------------------------------------------------------------*/
178      /* advanced solver interface */
179      int reason;
180      /* flag indicating the reason why the callback routine is being
181         called (see glpk.h) */
182      int stop;
183      /* flag indicating that the callback routine requires premature
184         termination of the search */
185      int next_p;
186      /* reference number of active subproblem selected to continue
187         the search; 0 means no subproblem has been selected */
188      int reopt;
189      /* flag indicating that the current LP relaxation needs to be
190         re-optimized */
191      int reinv;
192      /* flag indicating that some (non-active) rows were removed from
193         the current LP relaxation, so if there no new rows appear, the
194         basis must be re-factorized */
195      int br_var;
196      /* the number of variable chosen to branch on */
197      int br_sel;
198      /* flag indicating which branch (subproblem) is suggested to be
199         selected to continue the search:
200         GLP_DN_BRNCH - select down-branch
201         GLP_UP_BRNCH - select up-branch
202         GLP_NO_BRNCH - use general selection technique */
203      int child;
204      /* subproblem reference number corresponding to br_sel */
205};
206
207struct IOSLOT
208{     /* node subproblem slot */
209      IOSNPD *node;
210      /* pointer to subproblem descriptor; NULL means free slot */
211      int next;
212      /* index of another free slot (only if this slot is free) */
213};
214
215struct IOSNPD
216{     /* node subproblem descriptor */
217      int p;
218      /* subproblem reference number (it is the index to corresponding
219         slot, i.e. slot[p] points to this descriptor) */
220      IOSNPD *up;
221      /* pointer to the parent subproblem; NULL means this node is the
222         root of the tree, in which case p = 1 */
223      int level;
224      /* node level (the root node has level 0) */
225      int count;
226      /* if count = 0, this subproblem is active; if count > 0, this
227         subproblem is inactive, in which case count is the number of
228         its child subproblems */
229      /* the following three linked lists are destroyed on reviving and
230         built anew on freezing the subproblem: */
231      IOSBND *b_ptr;
232      /* linked list of rows and columns of the parent subproblem whose
233         types and bounds were changed */
234      IOSTAT *s_ptr;
235      /* linked list of rows and columns of the parent subproblem whose
236         statuses were changed */
237      IOSROW *r_ptr;
238      /* linked list of rows (cuts) added to the parent subproblem */
239      int solved;
240      /* how many times LP relaxation of this subproblem was solved;
241         for inactive subproblem this count is always non-zero;
242         for active subproblem, which is not current, this count may be
243         non-zero, if the subproblem was temporarily suspended */
244      double lp_obj;
245      /* optimal objective value to LP relaxation of this subproblem;
246         on creating a subproblem this value is inherited from its
247         parent; for the root subproblem, which has no parent, this
248         value is initially set to -DBL_MAX (minimization) or +DBL_MAX
249         (maximization); each time the subproblem is re-optimized, this
250         value is appropriately changed */
251      double bound;
252      /* local lower (minimization) or upper (maximization) bound for
253         integer optimal solution to *this* subproblem; this bound is
254         local in the sense that only subproblems in the subtree rooted
255         at this node cannot have better integer feasible solutions;
256         on creating a subproblem its local bound is inherited from its
257         parent and then can be made stronger (never weaker); for the
258         root subproblem its local bound is initially set to -DBL_MAX
259         (minimization) or +DBL_MAX (maximization) and then improved as
260         the root LP relaxation has been solved */
261      /* the following two quantities are defined only if LP relaxation
262         of this subproblem was solved at least once (solved > 0): */
263      int ii_cnt;
264      /* number of integer variables whose value in optimal solution to
265         LP relaxation of this subproblem is fractional */
266      double ii_sum;
267      /* sum of integer infeasibilities */
268#if 1 /* 30/XI-2009 */
269      int changed;
270      /* how many times this subproblem was re-formulated (by adding
271         cutting plane constraints) */
272#endif
273      int br_var;
274      /* ordinal number of branching variable, 1 <= br_var <= n, used
275         to split this subproblem; 0 means that either this subproblem
276         is active or branching was made on a constraint */
277      double br_val;
278      /* (fractional) value of branching variable in optimal solution
279         to final LP relaxation of this subproblem */
280      void *data; /* char data[tree->cb_size]; */
281      /* pointer to the application-specific data */
282      IOSNPD *temp;
283      /* working pointer used by some routines */
284      IOSNPD *prev;
285      /* pointer to previous subproblem in the active list */
286      IOSNPD *next;
287      /* pointer to next subproblem in the active list */
288};
289
290struct IOSBND
291{     /* bounds change entry */
292      int k;
293      /* ordinal number of corresponding row (1 <= k <= m) or column
294         (m+1 <= k <= m+n), where m and n are the number of rows and
295         columns, resp., in the parent subproblem */
296      unsigned char type;
297      /* new type */
298      double lb;
299      /* new lower bound */
300      double ub;
301      /* new upper bound */
302      IOSBND *next;
303      /* pointer to next entry for the same subproblem */
304};
305
306struct IOSTAT
307{     /* status change entry */
308      int k;
309      /* ordinal number of corresponding row (1 <= k <= m) or column
310         (m+1 <= k <= m+n), where m and n are the number of rows and
311         columns, resp., in the parent subproblem */
312      unsigned char stat;
313      /* new status */
314      IOSTAT *next;
315      /* pointer to next entry for the same subproblem */
316};
317
318struct IOSROW
319{     /* row (constraint) addition entry */
320      char *name;
321      /* row name or NULL */
322      unsigned char origin;
323      /* row origin flag (see glp_attr.origin) */
324      unsigned char klass;
325      /* row class descriptor (see glp_attr.klass) */
326      unsigned char type;
327      /* row type (GLP_LO, GLP_UP, etc.) */
328      double lb;
329      /* row lower bound */
330      double ub;
331      /* row upper bound */
332      IOSAIJ *ptr;
333      /* pointer to the row coefficient list */
334      double rii;
335      /* row scale factor */
336      unsigned char stat;
337      /* row status (GLP_BS, GLP_NL, etc.) */
338      IOSROW *next;
339      /* pointer to next entry for the same subproblem */
340};
341
342struct IOSAIJ
343{     /* constraint coefficient */
344      int j;
345      /* variable (column) number, 1 <= j <= n */
346      double val;
347      /* non-zero coefficient value */
348      IOSAIJ *next;
349      /* pointer to next coefficient for the same row */
350};
351
352struct IOSPOOL
353{     /* cut pool */
354      int size;
355      /* pool size = number of cuts in the pool */
356      IOSCUT *head;
357      /* pointer to the first cut */
358      IOSCUT *tail;
359      /* pointer to the last cut */
360      int ord;
361      /* ordinal number of the current cut, 1 <= ord <= size */
362      IOSCUT *curr;
363      /* pointer to the current cut */
364};
365
366struct IOSCUT
367{     /* cut (cutting plane constraint) */
368      char *name;
369      /* cut name or NULL */
370      unsigned char klass;
371      /* cut class descriptor (see glp_attr.klass) */
372      IOSAIJ *ptr;
373      /* pointer to the cut coefficient list */
374      unsigned char type;
375      /* cut type:
376         GLP_LO: sum a[j] * x[j] >= b
377         GLP_UP: sum a[j] * x[j] <= b
378         GLP_FX: sum a[j] * x[j]  = b */
379      double rhs;
380      /* cut right-hand side */
381      IOSCUT *prev;
382      /* pointer to previous cut */
383      IOSCUT *next;
384      /* pointer to next cut */
385};
386
387#define ios_create_tree _glp_ios_create_tree
388glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm);
389/* create branch-and-bound tree */
390
391#define ios_revive_node _glp_ios_revive_node
392void ios_revive_node(glp_tree *tree, int p);
393/* revive specified subproblem */
394
395#define ios_freeze_node _glp_ios_freeze_node
396void ios_freeze_node(glp_tree *tree);
397/* freeze current subproblem */
398
399#define ios_clone_node _glp_ios_clone_node
400void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]);
401/* clone specified subproblem */
402
403#define ios_delete_node _glp_ios_delete_node
404void ios_delete_node(glp_tree *tree, int p);
405/* delete specified subproblem */
406
407#define ios_delete_tree _glp_ios_delete_tree
408void ios_delete_tree(glp_tree *tree);
409/* delete branch-and-bound tree */
410
411#define ios_eval_degrad _glp_ios_eval_degrad
412void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up);
413/* estimate obj. degrad. for down- and up-branches */
414
415#define ios_round_bound _glp_ios_round_bound
416double ios_round_bound(glp_tree *tree, double bound);
417/* improve local bound by rounding */
418
419#define ios_is_hopeful _glp_ios_is_hopeful
420int ios_is_hopeful(glp_tree *tree, double bound);
421/* check if subproblem is hopeful */
422
423#define ios_best_node _glp_ios_best_node
424int ios_best_node(glp_tree *tree);
425/* find active node with best local bound */
426
427#define ios_relative_gap _glp_ios_relative_gap
428double ios_relative_gap(glp_tree *tree);
429/* compute relative mip gap */
430
431#define ios_solve_node _glp_ios_solve_node
432int ios_solve_node(glp_tree *tree);
433/* solve LP relaxation of current subproblem */
434
435#define ios_create_pool _glp_ios_create_pool
436IOSPOOL *ios_create_pool(glp_tree *tree);
437/* create cut pool */
438
439#define ios_add_row _glp_ios_add_row
440int ios_add_row(glp_tree *tree, IOSPOOL *pool,
441      const char *name, int klass, int flags, int len, const int ind[],
442      const double val[], int type, double rhs);
443/* add row (constraint) to the cut pool */
444
445#define ios_find_row _glp_ios_find_row
446IOSCUT *ios_find_row(IOSPOOL *pool, int i);
447/* find row (constraint) in the cut pool */
448
449#define ios_del_row _glp_ios_del_row
450void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i);
451/* remove row (constraint) from the cut pool */
452
453#define ios_clear_pool _glp_ios_clear_pool
454void ios_clear_pool(glp_tree *tree, IOSPOOL *pool);
455/* remove all rows (constraints) from the cut pool */
456
457#define ios_delete_pool _glp_ios_delete_pool
458void ios_delete_pool(glp_tree *tree, IOSPOOL *pool);
459/* delete cut pool */
460
461#define ios_preprocess_node _glp_ios_preprocess_node
462int ios_preprocess_node(glp_tree *tree, int max_pass);
463/* preprocess current subproblem */
464
465#define ios_driver _glp_ios_driver
466int ios_driver(glp_tree *tree);
467/* branch-and-bound driver */
468
469/**********************************************************************/
470
471typedef struct IOSVEC IOSVEC;
472
473struct IOSVEC
474{     /* sparse vector v = (v[j]) */
475      int n;
476      /* dimension, n >= 0 */
477      int nnz;
478      /* number of non-zero components, 0 <= nnz <= n */
479      int *pos; /* int pos[1+n]; */
480      /* pos[j] = k, 1 <= j <= n, is position of (non-zero) v[j] in the
481         arrays ind and val, where 1 <= k <= nnz; pos[j] = 0 means that
482         v[j] is structural zero */
483      int *ind; /* int ind[1+n]; */
484      /* ind[k] = j, 1 <= k <= nnz, is index of v[j] */
485      double *val; /* double val[1+n]; */
486      /* val[k], 1 <= k <= nnz, is a numeric value of v[j] */
487};
488
489#define ios_create_vec _glp_ios_create_vec
490IOSVEC *ios_create_vec(int n);
491/* create sparse vector */
492
493#define ios_check_vec _glp_ios_check_vec
494void ios_check_vec(IOSVEC *v);
495/* check that sparse vector has correct representation */
496
497#define ios_get_vj _glp_ios_get_vj
498double ios_get_vj(IOSVEC *v, int j);
499/* retrieve component of sparse vector */
500
501#define ios_set_vj _glp_ios_set_vj
502void ios_set_vj(IOSVEC *v, int j, double val);
503/* set/change component of sparse vector */
504
505#define ios_clear_vec _glp_ios_clear_vec
506void ios_clear_vec(IOSVEC *v);
507/* set all components of sparse vector to zero */
508
509#define ios_clean_vec _glp_ios_clean_vec
510void ios_clean_vec(IOSVEC *v, double eps);
511/* remove zero or small components from sparse vector */
512
513#define ios_copy_vec _glp_ios_copy_vec
514void ios_copy_vec(IOSVEC *x, IOSVEC *y);
515/* copy sparse vector (x := y) */
516
517#define ios_linear_comb _glp_ios_linear_comb
518void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y);
519/* compute linear combination (x := x + a * y) */
520
521#define ios_delete_vec _glp_ios_delete_vec
522void ios_delete_vec(IOSVEC *v);
523/* delete sparse vector */
524
525/**********************************************************************/
526
527#define ios_gmi_gen _glp_ios_gmi_gen
528void ios_gmi_gen(glp_tree *tree);
529/* generate Gomory's mixed integer cuts */
530
531#define ios_mir_init _glp_ios_mir_init
532void *ios_mir_init(glp_tree *tree);
533/* initialize MIR cut generator */
534
535#define ios_mir_gen _glp_ios_mir_gen
536void ios_mir_gen(glp_tree *tree, void *gen);
537/* generate MIR cuts */
538
539#define ios_mir_term _glp_ios_mir_term
540void ios_mir_term(void *gen);
541/* terminate MIR cut generator */
542
543#define ios_cov_gen _glp_ios_cov_gen
544void ios_cov_gen(glp_tree *tree);
545/* generate mixed cover cuts */
546
547#define ios_clq_init _glp_ios_clq_init
548void *ios_clq_init(glp_tree *tree);
549/* initialize clique cut generator */
550
551#define ios_clq_gen _glp_ios_clq_gen
552void ios_clq_gen(glp_tree *tree, void *gen);
553/* generate clique cuts */
554
555#define ios_clq_term _glp_ios_clq_term
556void ios_clq_term(void *gen);
557/* terminate clique cut generator */
558
559#define ios_pcost_init _glp_ios_pcost_init
560void *ios_pcost_init(glp_tree *tree);
561/* initialize working data used on pseudocost branching */
562
563#define ios_pcost_branch _glp_ios_pcost_branch
564int ios_pcost_branch(glp_tree *T, int *next);
565/* choose branching variable with pseudocost branching */
566
567#define ios_pcost_update _glp_ios_pcost_update
568void ios_pcost_update(glp_tree *tree);
569/* update history information for pseudocost branching */
570
571#define ios_pcost_free _glp_ios_pcost_free
572void ios_pcost_free(glp_tree *tree);
573/* free working area used on pseudocost branching */
574
575#define ios_feas_pump _glp_ios_feas_pump
576void ios_feas_pump(glp_tree *T);
577/* feasibility pump heuristic */
578
579#define ios_process_cuts _glp_ios_process_cuts
580void ios_process_cuts(glp_tree *T);
581/* process cuts stored in the local cut pool */
582
583#define ios_choose_node _glp_ios_choose_node
584int ios_choose_node(glp_tree *T);
585/* select subproblem to continue the search */
586
587#define ios_choose_var _glp_ios_choose_var
588int ios_choose_var(glp_tree *T, int *next);
589/* select variable to branch on */
590
591#endif
592
593/* eof */
Note: See TracBrowser for help on using the repository browser.