Changeset 75f460 in git for IntegerProgramming


Ignore:
Timestamp:
Dec 16, 2014, 3:43:21 PM (8 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')
Children:
fce947c9e6c3e8c6d5a622c7f6b0d724580993cc
Parents:
a2e4470c6e9a666de8ab7b706370c15e13092f76
Message:
format
Location:
IntegerProgramming
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • IntegerProgramming/change_cost.hlp

    ra2e447 r75f460  
    11USAGE: change_cost [options] groebner_file new_cost_file
    2            
    3              
    4            
     2
     3
     4
    55DESCRIPTION:
    6              
     6
    77change_cost is a program for recomputing the reduced Groebner basis of
    88a toric ideal with respect to a term ordering with modified
    … …  
    1010programming (see the help for solve_IP for more information).
    1111The program simply restarts BuchbergerŽs algorithm on an already
    12 computed toric ideal using the modified term ordering.               
    13            
    14                
    15      
     12computed toric ideal using the modified term ordering.
     13
     14
     15
    1616FILE FORMAT:
    17                
     17
    1818The first input file has to be a GROEBNER file; the second input file
    1919should to be a NEW_COST file. For convenience, also MATRIX files are
    2020accepted as second input files. For their format see the help for the
    21 solve_IP or the toric_ideal program. 
    22                
     21solve_IP or the toric_ideal program.
     22
    2323change_cost writes the new Groebner basis into a GROEBNER file named
    2424like the second input file with extensions replaced by
    25          
     25
    2626        .GB.<alg>
    27              
     27
    2828where GB stands for GROEBNER and <alg> is the abbreviation of the
    29 algorithm used for computing the input GROEBNER file (see the help for 
     29algorithm used for computing the input GROEBNER file (see the help for
    3030solve_IP or toric_ideal for an explaination).
    31                
     31
    3232A GROEBNER file looks as follows:
    33          
    34          
    35   GROEBNER 
    36            
     33
     34
     35  GROEBNER
     36
    3737  computed with algorithm:
    3838  <algorithm name abbreviation>       (* abbreviations as above *)
    39   from file(s):                       (* the following four lines are 
     39  from file(s):                       (* the following four lines are
    4040  <name of respective MATRIX file>       optional *)
    41   computation time:                     
    42   <computation time in seconds>         
    43              
     41  computation time:
     42  <computation time in seconds>
     43
    4444  term ordering:
    4545  elimination block
    … …  
    4949  weighted block
    5050  <number of weighted variables>
    51   <W_LEX / W_REV_LEX                  (* number of weighted variables   
     51  <W_LEX / W_REV_LEX                  (* number of weighted variables
    5252  / W_DEG_LEX / W_DEG_REV_LEX>           should always be >0 *)
    5353  <weight_vector>
    54              
     54
    5555  size:
    5656  <number of elements>
    57          
     57
    5858  Groebner basis:
    59   <basis elements>                   
    60            
    61   <settings for the Buchberger 
    62    algorithm and compiler settings>  (* optional *)             
    63            
    64                  
     59  <basis elements>
     60
     61  <settings for the Buchberger
     62   algorithm and compiler settings>  (* optional *)
     63
     64
    6565The Groebner basis consists always of binomials of the form x^a - x^b
    6666where x^a and x^b are relatively prime. Such a binomial can be
    67 represented by the vector a-b. The basis elements in the GROEBNER file 
     67represented by the vector a-b. The basis elements in the GROEBNER file
    6868are given by the coefficients of this vector representation.
    6969The settings for BuchbergerŽs algorithm and the compiler flags are
    7070produced when the GROEBNER file is generated by a call of solve_IP
    7171with the verbose output option
    72          
    73         -v, --verbose 
    74              
     72
     73        -v, --verbose
     74
    7575Example:
    76          
    77          
     76
     77
    7878  GROEBNER
    79          
     79
    8080  computed with algorithm:
    8181  du
    82        
    83   term ordering:       
     82
     83  term ordering:
    8484  elimination block:
    8585  0
    … …  
    8888  W_LEX
    8989  1 2 3
    90            
     90
    9191  size:
    9292  1
    93              
     93
    9494  Groebner basis:
    95   2 3 -2                            (*  x^2 * y^3 - z^2  *) 
    96            
    97                
     95  2 3 -2                            (*  x^2 * y^3 - z^2  *)
     96
     97
    9898A NEW_COST file should look as follows:
    99            
    100            
    101   NEW_COST             
    102            
    103   variables:                   
    104   <number of weighted variables>         
    105              
     99
     100
     101  NEW_COST
     102
     103  variables:
     104  <number of weighted variables>
     105
    106106  cost vector:
    107   <coefficients of the new weight vector>       
    108                
    109        
    110                
    111 OPTIONS: 
    112          
     107  <coefficients of the new weight vector>
     108
     109
     110
     111OPTIONS:
     112
    113113 -p         <number>      percentage of new generators to cause an
    114                           autoreduction during BuchbergerŽs algorithm; 
     114                          autoreduction during BuchbergerŽs algorithm;
    115115                          <number> may be an arbitrary float, a
    116116                          negative value allows no intermediate
    117117                          autoreductions
    118                           default is 
    119                           -p 12.0 
    120                
     118                          default is
     119                          -p 12.0
     120
    121121 -S [RP] [M] [B] [M] [2]  criteria to use in BuchbergerŽs algorithm
    122122                          for discarding unneccessary S-pairs
    … …  
    126126             B            Gebauer-Moeller criterion B
    127127             2            BuchbergerŽs second criterion
    128                           default is 
    129                           -S RP M B             
    130              
    131  -v,         
    132 --verbose                 verbose output mode; writes the settings for 
     128                          default is
     129                          -S RP M B
     130
     131 -v,
     132--verbose                 verbose output mode; writes the settings for
    133133                          BuchbergerŽs algorithm and the compiler
    134                           flags into the output GROEBNER file 
    135              
    136 -V <number>, 
     134                          flags into the output GROEBNER file
     135
     136-V <number>,
    137137--version <number>        version of BuchbergerŽs algorithm to use;
    138138                          <number> may be 1, 1a, 2 or 3
    139139                          default is
    140                           -V 1 
    141                  
     140                          -V 1
     141

  • IntegerProgramming/solve_IP.hlp

    ra2e447 r75f460  
    11USAGE: solve_IP [options] toric_file problem_file
    2            
    3              
    4            
     2
     3
     4
    55DESCRIPTION:
    6              
     6
    77solve_IP is a program for solving integer programming problems with
    88the Buchberger algorithm:
    9              
     9
    1010Let A an integral (mxn)-matrix, b a vector with m integral
    1111coefficients and c a vector with n nonnegative real coefficients. The
    12 solution of the IP-problem 
    13          
     12solution of the IP-problem
     13
    1414    minimize{ cx | Ax=b, all components of x are nonnegative integers }
    15              
     15
    1616proceeds in two steps:
    17            
     17
    18181. We compute the toric ideal of A and its Groebner basis with respect
    19    to a term ordering refining the cost function c. 
    20            
     19   to a term ordering refining the cost function c.
     20
    21212. We reduce the right hand vector b or an initial solution of the
    2222   problem modulo this ideal.
    23              
     23
    2424For these purposes, we can use seven different algorithms:
    2525The algorithm of Conti/Traverso (ct) can compute an optimal solution
    2626of the IP-problem directly from the right hand vector b. The same is
    2727true for its "positive" variant (pct) which can only be applied if A
    28 and b have nonnegative entries, but should be faster in that case. 
     28and b have nonnegative entries, but should be faster in that case.
    2929All other algorithms need initial solutions of the IP-problem. Except
    3030from the elimination version of the Conti-Traverso algorithm (ect),
    … …  
    3333(blr), Hosten/Sturmfels (hs) and Di Biase/Urbanke (du). The last two
    3434seem to be the fastest in the actual implementation.
    35                
    36            
    37                
     35
     36
     37
    3838FILE FORMAT:
    39                
     39
    4040The first input file may be a MATRIX or a GROEBNER file; these two
    4141types are called "toric files". The second input file has to be a
    42 PROBLEM file. 
    43                
     42PROBLEM file.
     43
    4444If the PROBLEM file contains a positive number of problems ,i.e. right
    4545hand vectors or initial solutions, solve_IP appends its solutions to a
    4646SOLUTION file named like the first input file with extensions replaced
    47 by 
    48          
     47by
     48
    4949        .sol.<alg>
    50              
     50
    5151where sol stands for solution and <alg> is the abbreviation of the
    5252used algorithm as above. When called with a MATRIX file, solve_IP
    5353produces a GROEBNER file named like the MATRIX file with extensions
    54 replaced by     
    55              
    56         .GB.<alg> 
    57              
     54replaced by
     55
     56        .GB.<alg>
     57
    5858where GB stands for GROEBNER.
    59                
     59
    6060A MATRIX file should look as follows:
    61            
    62            
    63   MATRIX             
    64            
     61
     62
     63  MATRIX
     64
    6565  columns:
    6666  <number of columns>
    67              
     67
    6868  cost vector:
    6969  <coefficients of the cost vector>
    70          
     70
    7171  rows:
    7272  <number of rows>
    73            
     73
    7474  matrix:
    7575  <matrix coefficients>
    76          
    77   positive row space vector:             
    78   <coefficients of row space vector>                                 
    79          
    80        
     76
     77  positive row space vector:
     78  <coefficients of row space vector>
     79
     80
    8181The last two lines are only needed when solve_IP is called with the
    8282algorithms of Hosten/Sturmfels or Bigatti/La Scala/Robbiano, i.e. the
    83 options 
    84          
     83options
     84
    8585        -alg hs
    8686or
    8787        -alg blr
    88          
    89 The other algorithms ignore these lines. 
    90        
     88
     89The other algorithms ignore these lines.
     90
    9191Example:
    92        
    93        
     92
     93
    9494  MATRIX
    95        
     95
    9696  columns:
    9797  3
    98            
     98
    9999  cost vector:
    100100  1 1 1
    101      
     101
    102102  rows:
    103103  2
    104          
     104
    105105  matrix:
    106106  1 2 3
    107107  4 5 6
    108          
     108
    109109  positive row space vector:
    110110  1 2 3
    111          
    112          
     111
     112
    113113A GROEBNER file looks as follows:
    114          
    115          
    116   GROEBNER 
    117            
     114
     115
     116  GROEBNER
     117
    118118  computed with algorithm:
    119119  <algorithm name abbreviation>       (* abbreviations as above *)
    120   from file(s):                       (* the following four lines are 
     120  from file(s):                       (* the following four lines are
    121121  <name of respective MATRIX file>       optional *)
    122   computation time:                     
    123   <computation time in seconds>         
    124              
     122  computation time:
     123  <computation time in seconds>
     124
    125125  term ordering:
    126126  elimination block
    … …  
    130130  weighted block
    131131  <number of weighted variables>
    132   <W_LEX / W_REV_LEX                  (* number of weighted variables   
     132  <W_LEX / W_REV_LEX                  (* number of weighted variables
    133133  / W_DEG_LEX / W_DEG_REV_LEX>           should always be >0 *)
    134134  <weight_vector>
    135              
     135
    136136  size:
    137137  <number of elements>
    138          
     138
    139139  Groebner basis:
    140   <basis elements>                   
    141            
    142   <settings for the Buchberger 
    143    algorithm and compiler settings>  (* optional *)             
    144            
    145                  
     140  <basis elements>
     141
     142  <settings for the Buchberger
     143   algorithm and compiler settings>  (* optional *)
     144
     145
    146146The Groebner basis consists always of binomials of the form x^a - x^b
    147147where x^a and x^b are relatively prime. Such a binomial can be
    148 represented by the vector a-b. The basis elements in the GROEBNER file 
     148represented by the vector a-b. The basis elements in the GROEBNER file
    149149are given by the coefficients of this vector representation.
    150150The settings for BuchbergerŽs algorithm and the compiler flags are
    151151produced when the GROEBNER file is generated by a call of solve_IP
    152152with the verbose output option
    153          
    154         -v, --verbose 
    155              
     153
     154        -v, --verbose
     155
    156156Example (not belonging to the example above):
    157          
    158          
     157
     158
    159159  GROEBNER
    160          
     160
    161161  computed with algorithm:
    162162  du
    163        
    164   term ordering:       
     163
     164  term ordering:
    165165  elimination block:
    166166  0
    … …  
    169169  W_LEX
    170170  1 2 3
    171            
     171
    172172  size:
    173173  1
    174              
     174
    175175  Groebner basis:
    176   2 3 -2                            (*  x^2 * y^3 - z^2  *) 
    177            
    178                
     176  2 3 -2                            (*  x^2 * y^3 - z^2  *)
     177
     178
    179179A PROBLEM file should look as follows:
    180          
    181              
     180
     181
    182182  PROBLEM
    183              
     183
    184184  vector size:
    185185  <vector dimension>
    186            
     186
    187187  number of instances:
    188188  <number of vectors>
    189              
    190   right-hand or initial solution vectors:     
    191   <vector coefficients>                   
    192          
    193            
     189
     190  right-hand or initial solution vectors:
     191  <vector coefficients>
     192
     193
    194194A SOLUTION file looks as follows:
    195          
    196   SOLUTION                                   
    197                
    198   computed with algorithm:               
    199   <algorithm name abbreviation>         
    200   from file:                                  (* the GROEBNER file *)   
    201   <file name>                                 
    202              
    203   <right hand/initial solution> vector:       
     195
     196  SOLUTION
     197
     198  computed with algorithm:
     199  <algorithm name abbreviation>
     200  from file:                                  (* the GROEBNER file *)
     201  <file name>
     202
     203  <right hand/initial solution> vector:
    204204  <vector as in the problem file>
    205205  solvable:                                   (* only if right-hand
    206   <YES/NO>                                       vector is given *) 
    207   optimal solution:                           (* only in the case of 
    208   <optimal solution vector>                      existence *) 
    209   computation time:                           (* only for reduction *) 
    210   <reduction time in seconds>                 
    211            
     206  <YES/NO>                                       vector is given *)
     207  optimal solution:                           (* only in the case of
     208  <optimal solution vector>                      existence *)
     209  computation time:                           (* only for reduction *)
     210  <reduction time in seconds>
     211
    212212  ...                                         (* further vectors,
    213                                                  same format *) 
    214          
    215        
    216              
    217 OPTIONS: 
    218          
    219  -alg       <alg>,     
    220 --algorithm <alg>         algorithm to use for solving the given IP 
    221                           instances; <alg> may be 
     213                                                 same format *)
     214
     215
     216
     217OPTIONS:
     218
     219 -alg       <alg>,
     220--algorithm <alg>         algorithm to use for solving the given IP
     221                          instances; <alg> may be
    222222             ct           for Conti/Traverso,
    223223             pct          for the positive Conti/Traverso,
    … …  
    227227             du           for Di Biase/Urbanke,
    228228             blr          for Bigatti-LaScal-Robbiano.
    229                
     229
    230230 -p         <number>      percentage of new generators to cause an
    231                           autoreduction during BuchbergerŽs algorithm; 
     231                          autoreduction during BuchbergerŽs algorithm;
    232232                          <number> may be an arbitrary float, a
    233233                          negative value allows no intermediate
    234234                          autoreductions
    235                           default is 
    236                           -p 12.0 
    237                
     235                          default is
     236                          -p 12.0
     237
    238238 -S [RP] [M] [B] [M] [2]  criteria to use in BuchbergerŽs algorithm
    239239                          for discarding unneccessary S-pairs
    … …  
    243243             B            Gebauer-Moeller criterion B
    244244             2            BuchbergerŽs second criterion
    245                           default is 
    246                           -S RP M B             
    247              
    248  -v,         
    249 --verbose                 verbose output mode; writes the settings for 
     245                          default is
     246                          -S RP M B
     247
     248 -v,
     249--verbose                 verbose output mode; writes the settings for
    250250                          BuchbergerŽs algorithm and the compiler
    251                           flags into the output GROEBNER file 
    252              
    253 -V <number>, 
     251                          flags into the output GROEBNER file
     252
     253-V <number>,
    254254--version <number>        version of BuchbergerŽs algorithm to use;
    255255                          <number> may be 1, 1a, 2 or 3
    256256                          default is
    257                           -V 1 
    258                  
    259                    
     257                          -V 1
     258
     259
    260260When called with a GROEBNER file, these options do not affect
    261261computation and are ignored by solve_IP.

  • IntegerProgramming/toric_ideal.hlp

    ra2e447 r75f460  
    1 USAGE: toric_ideal [options] matrix_file 
    2                  
    3              
    4              
     1USAGE: toric_ideal [options] matrix_file
     2
     3
     4
    55DESCRIPTION:
    6        
     6
    77toric_ideal is a program for computing the toric ideal of a matrix A.
    88This ideal is always given by the reduced Groebner basis with respect
    99to a given term ordering which is computed via BuchbergerŽs
    10 algorithm. 
     10algorithm.
    1111For this purpose, we can use six different algorithms:
    1212The algorithm of Conti/Traverso (ct) computes the toric ideal of an
    1313extended matrix. This ideal can be used later for solving integer
    1414programming problems for given right hand vectors. By eliminating
    15 auxiliary variables, we can get the toric ideal of the original matrix 
     15auxiliary variables, we can get the toric ideal of the original matrix
    1616from it. The same is true for the "positive" variant of the
    1717Conti-Traverso-algorithm (pct) which can only be applied if A has
    … …  
    2323are the algorithms of Pottier (pt), Bigatti/La Scala/Robbiano (blr),
    2424Hosten/Sturmfels (hs) and Di Biase/Urbanke (du). The last two seem to
    25 be the fastest in the actual implementation. 
    26          
    27                                
    28                            
     25be the fastest in the actual implementation.
     26
     27
     28
    2929FILE FORMAT:
    30          
     30
    3131The input file has to be a MATRIX file. toric_ideal produces a
    32 GROEBNER file named like the MATRIX file with extensions replaced by     
    33            
    34         .GB.<alg> 
    35            
     32GROEBNER file named like the MATRIX file with extensions replaced by
     33
     34        .GB.<alg>
     35
    3636where GB stands for GROEBNER and <alg> is the abbreviation for the
    3737used algorithm as above.
    38          
     38
    3939A MATRIX file should look as follows:
    40        
    41        
    42   MATRIX             
    43            
     40
     41
     42  MATRIX
     43
    4444  columns:
    4545  <number of columns>
    46          
     46
    4747  cost vector:
    4848  <coefficients of the cost vector>
    49        
     49
    5050  rows:
    5151  <number of rows>
    52          
     52
    5353  matrix:
    5454  <matrix coefficients>
    55            
    56   positive row space vector:             
    57   <coefficients of row space vector>                                 
    58          
    59              
    60 The last two lines are only needed when toric_ideal is called with the 
     55
     56  positive row space vector:
     57  <coefficients of row space vector>
     58
     59
     60The last two lines are only needed when toric_ideal is called with the
    6161algorithms of Hosten/Sturmfels or Bigatti/La Scala/Robbiano, i.e. the
    62 options 
    63        
     62options
     63
    6464        -alg hs
    6565or
    6666        -alg blr
    67          
    68 The other algorithms ignore these lines. 
    69          
     67
     68The other algorithms ignore these lines.
     69
    7070Example:
    71      
    72      
     71
     72
    7373  MATRIX
    74      
     74
    7575  columns:
    7676  3
    77          
     77
    7878  cost vector:
    7979  1 1 1
    80        
     80
    8181  rows:
    8282  2
    83        
     83
    8484  matrix:
    8585  1 2 3
    8686  4 5 6
    87          
     87
    8888  positive row space vector:
    8989  1 2 3
    90          
    91          
     90
     91
    9292A GROEBNER file looks as follows:
    93        
    94              
    95   GROEBNER 
    96            
     93
     94
     95  GROEBNER
     96
    9797  computed with algorithm:
    9898  <algorithm name abbreviation>       (* abbreviations as above *)
    99   from file(s):                       (* the following four lines are 
     99  from file(s):                       (* the following four lines are
    100100  <name of respective MATRIX file>       optional *)
    101   computation time:                     
    102   <computation time in seconds>         
    103            
     101  computation time:
     102  <computation time in seconds>
     103
    104104  term ordering:
    105105  elimination block
    … …  
    109109  weighted block
    110110  <number of weighted variables>
    111   <W_LEX / W_REV_LEX                  (* number of weighted variables   
     111  <W_LEX / W_REV_LEX                  (* number of weighted variables
    112112  / W_DEG_LEX / W_DEG_REV_LEX>           should always be >0 *)
    113113  <weight_vector>
    114          
     114
    115115  size:
    116116  <number of elements>
    117            
     117
    118118  Groebner basis:
    119   <basis elements>                   
    120            
    121   <settings for the Buchberger 
    122    algorithm and compiler settings>  (* optional *)             
    123          
    124            
     119  <basis elements>
     120
     121  <settings for the Buchberger
     122   algorithm and compiler settings>  (* optional *)
     123
     124
    125125The Groebner basis consists always of binomials of the form x^a - x^b
    126126where x^a and x^b are relatively prime. Such a binomial can be
    127 represented by the vector a-b. The basis elements in the GROEBNER file 
     127represented by the vector a-b. The basis elements in the GROEBNER file
    128128are given by the coefficients of this vector representation.
    129129The settings for BuchbergerŽs algorithm and the compiler flags are
    130 produced when the GROEBNER file is generated by a call of toric_ideal 
     130produced when the GROEBNER file is generated by a call of toric_ideal
    131131with the verbose output option
    132          
    133         -v, --verbose 
    134          
     132
     133        -v, --verbose
     134
    135135Example (not belonging to the example above):
    136            
    137        
     136
     137
    138138  GROEBNER
    139          
     139
    140140  computed with algorithm:
    141141  du
    142          
    143   term ordering:       
     142
     143  term ordering:
    144144  elimination block:
    145145  0
    … …  
    148148  W_LEX
    149149  1 2 3
    150          
     150
    151151  size:
    152152  1
    153            
     153
    154154  Groebner basis:
    155   2 3 -2                            (*  x^2 * y^3 - z^2  *) 
    156            
    157          
    158              
    159 OPTIONS: 
    160          
    161  -alg       <alg>,     
     155  2 3 -2                            (*  x^2 * y^3 - z^2  *)
     156
     157
     158
     159OPTIONS:
     160
     161 -alg       <alg>,
    162162--algorithm <alg>         algorithm to use for computing the toric
    163                           ideal; <alg> may be 
     163                          ideal; <alg> may be
    164164             ct           for Conti/Traverso,
    165165             pct          for the positive Conti/Traverso,
    … …  
    169169             du           for Di Biase/Urbanke,
    170170             blr          for Bigatti-LaScal-Robbiano.
    171              
     171
    172172 -p         <number>      percentage of new generators to cause an
    173                           autoreduction during BuchbergerŽs algorithm; 
     173                          autoreduction during BuchbergerŽs algorithm;
    174174                          <number> may be an arbitrary float, a
    175175                          negative value allows no intermediate
    176176                          autoreductions
    177                           default is 
    178                           -p 12.0 
     177                          default is
     178                          -p 12.0
    179179
    180180 -S [RP] [M] [B] [M] [2]  criteria to use in BuchbergerŽs algorithm
    … …  
    185185             B            Gebauer-Moeller criterion B
    186186             2            BuchbergerŽs second criterion
    187                           default is 
    188                           -S RP M B             
    189                  
    190  -v,         
    191 --verbose                 verbose output mode; writes the settings for 
     187                          default is
     188                          -S RP M B
     189
     190 -v,
     191--verbose                 verbose output mode; writes the settings for
    192192                          BuchbergerŽs algorithm and the compiler
    193                           flags into the output GROEBNER file 
    194                      
    195 -V <number>, 
     193                          flags into the output GROEBNER file
     194
     195-V <number>,
    196196--version <number>        version of BuchbergerŽs algorithm to use;
    197197                          <number> may be 1, 1a, 2 or 3
    198198                          default is
    199                           -V 1 
    200        
    201 
     199                          -V 1
     200
     201
Note: See TracChangeset for help on using the changeset viewer.