# Singular          #### 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

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=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,1 list solution_list=solve_IP(A,l,c,"ct"); solution_list;""; ==> : ==> 0,1,0 ==> : ==> 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; ==> : ==> 3,4,5 ==> : ==> 7,8,0 solution_list=solve_IP(A,l,c,"blr",prsv); solution_list; ==> : ==> 0,7,2 ==> : ==> 7,8,0 ``` 