source: git/IntegerProgramming/solve_IP.hlp @ 074171

spielwiese
Last change on this file since 074171 was 6ba162, checked in by Hans Schönemann <hannes@…>, 24 years ago
This commit was generated by cvs2svn to compensate for changes in r4282, which included commits to RCS files with non-trunk default branches. git-svn-id: file:///usr/local/Singular/svn/trunk@4283 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 8.1 KB
Line 
1USAGE: solve_IP [options] toric_file problem_file
2           
3             
4           
5DESCRIPTION:
6             
7solve_IP is a program for solving integer programming problems with
8the Buchberger algorithm:
9             
10Let A an integral (mxn)-matrix, b a vector with m integral
11coefficients and c a vector with n nonnegative real coefficients. The
12solution of the IP-problem
13         
14    minimize{ cx | Ax=b, all components of x are nonnegative integers }
15             
16proceeds in two steps:
17           
181. We compute the toric ideal of A and its Groebner basis with respect
19   to a term ordering refining the cost function c.
20           
212. We reduce the right hand vector b or an initial solution of the
22   problem modulo this ideal.
23             
24For these purposes, we can use seven different algorithms:
25The algorithm of Conti/Traverso (ct) can compute an optimal solution
26of the IP-problem directly from the right hand vector b. The same is
27true for its "positive" variant (pct) which can only be applied if A
28and b have nonnegative entries, but should be faster in that case.
29All other algorithms need initial solutions of the IP-problem. Except
30from the elimination version of the Conti-Traverso algorithm (ect),
31they should be more efficient than the algorithm mentionned before.
32These are the algorithms of Pottier (pt), Bigatti/La Scala/Robbiano
33(blr), Hosten/Sturmfels (hs) and Di Biase/Urbanke (du). The last two
34seem to be the fastest in the actual implementation.
35               
36           
37               
38FILE FORMAT:
39               
40The first input file may be a MATRIX or a GROEBNER file; these two
41types are called "toric files". The second input file has to be a
42PROBLEM file.
43               
44If the PROBLEM file contains a positive number of problems ,i.e. right
45hand vectors or initial solutions, solve_IP appends its solutions to a
46SOLUTION file named like the first input file with extensions replaced
47by
48         
49        .sol.<alg>
50             
51where sol stands for solution and <alg> is the abbreviation of the
52used algorithm as above. When called with a MATRIX file, solve_IP
53produces a GROEBNER file named like the MATRIX file with extensions
54replaced by     
55             
56        .GB.<alg>
57             
58where GB stands for GROEBNER.
59               
60A MATRIX file should look as follows:
61           
62           
63  MATRIX             
64           
65  columns:
66  <number of columns>
67             
68  cost vector:
69  <coefficients of the cost vector>
70         
71  rows:
72  <number of rows>
73           
74  matrix:
75  <matrix coefficients>
76         
77  positive row space vector:             
78  <coefficients of row space vector>                                 
79         
80       
81The last two lines are only needed when solve_IP is called with the
82algorithms of Hosten/Sturmfels or Bigatti/La Scala/Robbiano, i.e. the
83options 
84         
85        -alg hs
86or
87        -alg blr
88         
89The other algorithms ignore these lines. 
90       
91Example:
92       
93       
94  MATRIX
95       
96  columns:
97  3
98           
99  cost vector:
100  1 1 1
101     
102  rows:
103  2
104         
105  matrix:
106  1 2 3
107  4 5 6
108         
109  positive row space vector:
110  1 2 3
111         
112         
113A GROEBNER file looks as follows:
114         
115         
116  GROEBNER
117           
118  computed with algorithm:
119  <algorithm name abbreviation>       (* abbreviations as above *)
120  from file(s):                       (* the following four lines are
121  <name of respective MATRIX file>       optional *)
122  computation time:                     
123  <computation time in seconds>         
124             
125  term ordering:
126  elimination block
127  <number of elimination variables>
128  <LEX / DEG_LEX                      (* only if number of elimination
129  / DEG_REV_LEX>                         variables >0 *)
130  weighted block
131  <number of weighted variables>
132  <W_LEX / W_REV_LEX                  (* number of weighted variables   
133  / W_DEG_LEX / W_DEG_REV_LEX>           should always be >0 *)
134  <weight_vector>
135             
136  size:
137  <number of elements>
138         
139  Groebner basis:
140  <basis elements>                   
141           
142  <settings for the Buchberger
143   algorithm and compiler settings>  (* optional *)             
144           
145                 
146The Groebner basis consists always of binomials of the form x^a - x^b
147where x^a and x^b are relatively prime. Such a binomial can be
148represented by the vector a-b. The basis elements in the GROEBNER file
149are given by the coefficients of this vector representation.
150The settings for BuchbergerŽs algorithm and the compiler flags are
151produced when the GROEBNER file is generated by a call of solve_IP
152with the verbose output option
153         
154        -v, --verbose 
155             
156Example (not belonging to the example above):
157         
158         
159  GROEBNER
160         
161  computed with algorithm:
162  du
163       
164  term ordering:       
165  elimination block:
166  0
167  weighted block:
168  3
169  W_LEX
170  1 2 3
171           
172  size:
173  1
174             
175  Groebner basis:
176  2 3 -2                            (*  x^2 * y^3 - z^2  *)
177           
178               
179A PROBLEM file should look as follows:
180         
181             
182  PROBLEM
183             
184  vector size:
185  <vector dimension>
186           
187  number of instances:
188  <number of vectors>
189             
190  right-hand or initial solution vectors:     
191  <vector coefficients>                   
192         
193           
194A 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:       
204  <vector as in the problem file>
205  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           
212  ...                                         (* further vectors,
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
222             ct           for Conti/Traverso,
223             pct          for the positive Conti/Traverso,
224             ect          for Conti/Traverso with elimination,
225             pt           for Pottier,
226             hs           for Hosten/Sturmfels,
227             du           for Di Biase/Urbanke,
228             blr          for Bigatti-LaScal-Robbiano.
229               
230 -p         <number>      percentage of new generators to cause an
231                          autoreduction during BuchbergerŽs algorithm;
232                          <number> may be an arbitrary float, a
233                          negative value allows no intermediate
234                          autoreductions
235                          default is
236                          -p 12.0 
237               
238 -S [RP] [M] [B] [M] [2]  criteria to use in BuchbergerŽs algorithm
239                          for discarding unneccessary S-pairs
240             RP           relatively prime leading terms
241             M            Gebauer-Moeller criterion M
242             F            Gebauer-Moeller criterion F
243             B            Gebauer-Moeller criterion B
244             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
250                          BuchbergerŽs algorithm and the compiler
251                          flags into the output GROEBNER file
252             
253-V <number>,
254--version <number>        version of BuchbergerŽs algorithm to use;
255                          <number> may be 1, 1a, 2 or 3
256                          default is
257                          -V 1 
258                 
259                   
260When called with a GROEBNER file, these options do not affect
261computation and are ignored by solve_IP.
Note: See TracBrowser for help on using the repository browser.