1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
@c ---content LibInfo---
@comment This file was generated by doc2tex.pl from d2t_singular/intprog_lib.doc
@comment DO NOT EDIT DIRECTLY, BUT EDIT d2t_singular/intprog_lib.doc INSTEAD
@c library version: (1.5,2001/02/06)
@c library file: ../Singular/LIB/intprog.lib
@cindex intprog.lib
@cindex intprog_lib
@table @asis
@item @strong{Library:}
intprog.lib
@item @strong{Purpose:}
Integer Programming with Groebner Basis Methods
@item @strong{Author:}
Christine Theis, email: ctheis@@math.uni-sb.de
@end table
@strong{Procedures:}
@menu
* solve_IP:: procedures for solving Integer Programming problems
@end menu
@c ---end content LibInfo---
@c ------------------- solve_IP -------------
@node solve_IP,,, intprog_lib
@subsubsection solve_IP
@cindex solve_IP
@c ---content solve_IP---
Procedure from library @code{intprog.lib} (@pxref{intprog_lib}).
@table @asis
@item @strong{Usage:}
solve_IP(A,bx,c,alg); A intmat, bx intvec, c intvec, alg string.
solve_IP(A,bx,c,alg); A intmat, bx list of intvec, c intvec,
alg string.
@*solve_IP(A,bx,c,alg,prsv); A intmat, bx intvec, c intvec,
alg string, prsv intvec.
@*solve_IP(A,bx,c,alg,prsv); A intmat, bx list of intvec, c intvec,
alg string, prsv intvec.
@item @strong{Return:}
same type as bx: solution of the associated integer programming
problem(s) as explained in
@ref{Toric ideals and integer programming}.
@item @strong{Note:}
This procedure returns the solution(s) of the given IP-problem(s)
or the message `not solvable'.
@*One may call the procedure with several different algorithms:
@*- the algorithm of Conti/Traverso (ct),
@*- the positive variant of the algorithm of Conti/Traverso (pct),
@*- the algorithm of Conti/Traverso using elimination (ect),
@*- the algorithm of Pottier (pt),
@*- an algorithm of Bigatti/La Scala/Robbiano (blr),
@*- the algorithm of Hosten/Sturmfels (hs),
@*- the algorithm of DiBiase/Urbanke (du).
The argument `alg' should be the abbreviation for an algorithm as
above: ct, pct, ect, pt, blr, hs or du.
`ct' allows computation of an optimal solution of the IP-problem
directly from the right-hand vector b.
@*The same is true for its `positive' variant `pct' which may only be
applied if A and b have nonnegative entries.
@*All other algorithms need initial solutions of the IP-problem.
If `alg' is chosen to be `ct' or `pct', bx is read as the right hand
vector b of the system Ax=b. b should then be an intvec of size m
where m is the number of rows of A.
@*Furthermore, bx and A should be nonnegative if `pct' is used.
If `alg' is chosen to be `ect',`pt',`blr',`hs' or `du',
bx is read as an initial solution x of the system Ax=b.
bx should then be a nonnegative intvec of size n where n is the
number of columns of A.
If `alg' is chosen to be `blr' or `hs', the algorithm needs a vector
with positive coefficients in the row space of A.
@*If no row of A contains only positive entries, one has to use the
versions of solve_IP which take such a vector prsv as an argument.
solve_IP may also be called with a list bx of intvecs instead of a
single intvec.
@end table
@strong{Example:}
@smallexample
@c computed example solve_IP d2t_singular/intprog_lib.doc:85
LIB "intprog.lib";
// 1. call with single right-hand vector
intmat A[2][3]=1,1,0,0,1,1;
intvec b1=1,1;
intvec c=2,2,1;
intvec solution_vector=solve_IP(A,b1,c,"pct");
solution_vector;"";
@expansion{} 0,1,0
@expansion{}
// 2. call with list of right-hand vectors
intvec b2=-1,1;
list l=b1,b2;
l;
@expansion{} [1]:
@expansion{} 1,1
@expansion{} [2]:
@expansion{} -1,1
list solution_list=solve_IP(A,l,c,"ct");
solution_list;"";
@expansion{} [1]:
@expansion{} 0,1,0
@expansion{} [2]:
@expansion{} not solvable
@expansion{}
// 3. call with single initial solution vector
A=2,1,-1,-1,1,2;
b1=3,4,5;
solve_IP(A,b1,c,"du");"";
@expansion{} 0,7,2
@expansion{}
// 4. call with single initial solution vector
// and algorithm needing a positive row space vector
solution_vector=solve_IP(A,b1,c,"hs");"";
@expansion{} ERROR: The chosen algorithm needs a positive vector in the row space of t\
he matrix.
@expansion{} 0
@expansion{}
// 5. call with single initial solution vector
// and positive row space vector
intvec prsv=1,2,1;
solution_vector=solve_IP(A,b1,c,"hs",prsv);
solution_vector;"";
@expansion{} 0,7,2
@expansion{}
// 6. call with list of initial solution vectors
// and positive row space vector
b2=7,8,0;
l=b1,b2;
l;
@expansion{} [1]:
@expansion{} 3,4,5
@expansion{} [2]:
@expansion{} 7,8,0
solution_list=solve_IP(A,l,c,"blr",prsv);
solution_list;
@expansion{} [1]:
@expansion{} 0,7,2
@expansion{} [2]:
@expansion{} 7,8,0
@c end example solve_IP d2t_singular/intprog_lib.doc:85
@end smallexample
@c inserted refs from d2t_singular/intprog_lib.doc:120
@ifinfo
@menu
See also:
* Integer programming::
* intprog_lib::
* toric_lib::
@end menu
@end ifinfo
@iftex
@strong{See also:}
@ref{Integer programming};
@ref{intprog_lib};
@ref{toric_lib}.
@end iftex
@c end inserted refs from d2t_singular/intprog_lib.doc:120
@c ---end content solve_IP---
|
