|
D.4.10.1 solve_IP
Procedure from library intprog.lib (see intprog_lib).
- 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.
- Return:
same type as bx: solution of the associated integer programming
problem(s) as explained in
Toric ideals and integer programming.
- 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.
Example:
| 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;"";
→ 0,1,0
→
// 2. call with list of right-hand vectors
intvec b2=-1,1;
list l=b1,b2;
l;
→ [1]:
→ 1,1
→ [2]:
→ -1,1
list solution_list=solve_IP(A,l,c,"ct");
solution_list;"";
→ [1]:
→ 0,1,0
→ [2]:
→ not solvable
→
// 3. call with single initial solution vector
A=2,1,-1,-1,1,2;
b1=3,4,5;
solve_IP(A,b1,c,"du");"";
→ 0,7,2
→
// 4. call with single initial solution vector
// and algorithm needing a positive row space vector
solution_vector=solve_IP(A,b1,c,"hs");"";
→ ERROR: The chosen algorithm needs a positive vector in the row space of t\
he matrix.
→ 0
→
// 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;"";
→ 0,7,2
→
// 6. call with list of initial solution vectors
// and positive row space vector
b2=7,8,0;
l=b1,b2;
l;
→ [1]:
→ 3,4,5
→ [2]:
→ 7,8,0
solution_list=solve_IP(A,l,c,"blr",prsv);
solution_list;
→ [1]:
→ 0,7,2
→ [2]:
→ 7,8,0
|
See also:
Integer programming;
intprog_lib;
toric_lib.
|