pacoop is an application of
rmd
(rigorous MAXDET) which is a mathematically rigorous wrapper
for the package
MAXDET
of Wu, Vandenberghe and Boyd.
pacoop can be used to
approximate optimal lattice sphere packingcoverings. Furthermore,
pacoop gives
lower and upper bounds for the optimal lattice packingcovering. This part of
the computation uses rational arithmetic only and it is mathematically
rigorous.
For the underlying theory, notation and terminology see the paper
"Determinant maximization with linear matrix inequality constraints" of
Vandenberghe, Boyd and Wu, and our paper "Computational approaches to
lattice packing and covering problems"
(
math.MG/0403272).
USAGE:
pacoop [options] < file
Options:
h show this help
b read and exclude boundary facets
c certify local optimality
d x set duality gap to x
e read possible minimal edges (vectors)
i read interior point
m N set maximum iterations to N
q quick and dirty (nonrigorous)
v be verbose
n be nonverbose
INPUT:
input files (preferably with extension
.coop)
are plain text files containing the following information:
 dimension: d
 number of simplices: n
 simplices: n matrices with d rows and d columns, where in every
row the coordinates of one vertex is represented, we assume that every
simplex has the origin as a vertex
 with e, number of possible minimal vectors: r
 with e, list of possible minimal vectors: r rows and d columns, containing integral coordinate vectors
 number of basis vectors: m
 basis vectors: G_1, ..., G_m as lower triangular matrices with d
rows and d columns
 number of inequalities: k
 with b, a vector in {0,1}^k: 1 if the corresponding
inequality defines a facet of the
feasible region that contains nonpositive forms only,
0 otherwise
 inequalities: matrix with k rows and m columns (a_{ij})
 with i, interior point: (x_1, ..., x_m) a point which satisfies
Q(x_1,...,x_m) = x_1G_1 + ... + x_mG_m is positive definite, a_{i1}x_1
+ ... + a_{im} x_m >= 0, i = 1,...,k, and all circumradii of
the simplices are less or equal 1 with respect to Q(x_1,...,x_m)
 without m, maximum number of iterations: how many iterations should MAXDET
perform
 without d, absolute gap (convergence criterion): stop when the gap between primal and dual solution is less then absolute gap
EXAMPLES:

Input:
Use file input.coop given in the first example in the User's Guide of
coop.
Call:
pacoop < input.coop
Output:
*** pa ***
*** co ***
*** op ***
* computed possible minimal vectors
1 0
1 1
0 1
* computed interior point
1 0.5 1
 SOLVING MAXDET PROBLEM
 starting MAXDET (workspace = 609)
iters primal dual
4 0.611815 6.865484
9 2.999130 3.001087
15 3.000000 3.000000
18 3.000000 3.000000
22 3.000000 3.000000
 MAXDET stopped because duality_gap reached.
 primal value = 3
 dual value = 3
 minimizer = 3 1.5 3 3
 minimizer_approx = [100000000000000000000 299999999999946842521 149999999999973421261 299999999999946842521 299999999999787192450]
 CHECKING PRIMAL SOLUTION
 G(x) is positive definite.
 F(x) is positive semidefinite.
 upper_bound ~ 3
 CHECKING DUAL SOLUTION
 Tr G_i W + Tr F_i Z = c_i.
 W is positive definite.
 Z is positive semidefinite.
 lower_bound ~ 3
 duality_gap ~ 4.7895021e12
***********
* SUMMARY *
***********
* minimizer_approx = [100000000000000000000 299999999999946842521 149999999999973421261 299999999999946842521]
* gamma_lower_bound = 2/sqrt(15000000000013307133/5000000000000000000  log(1))
~ 1.154700538
* gamma_upper_bound = 2/sqrt(5999999999995743849/2000000000000000000  log(1))
~ 1.154700538
* duality_gap ~ 4.7895021e12
* Thanks for your patience...

Input:
Take same input as in the previous example, but possibly without
number of maximum iterations and duality gap.
Call:
pacoop d 0.0001 m 50 c < file.coop
Output:
*** pa ***
*** co ***
*** op ***
* computed possible minimal vectors
1 0
1 1
0 1
* computed interior point
1 0.5 1
 SOLVING MAXDET PROBLEM
 starting MAXDET (workspace = 609)
iters primal dual
4 0.611815 6.865484
9 2.999130 3.001087
12 2.999993 3.000009
 MAXDET stopped because duality_gap reached.
 primal value = 2.999992561
 dual value = 3.000009302
 minimizer = 2.999998141 1.499999071 2.999998141 2.999992561
 minimizer_approx = [100000000000000000000 299999814132312270231 149999907066156129824 29999981413231227023
1 299999256056956431493]
 CHECKING PRIMAL SOLUTION
 G(x) is positive definite.
 F(x) is positive semidefinite.
 upper_bound ~ 2.999992561
 CHECKING DUAL SOLUTION
 Tr G_i W + Tr F_i Z = c_i.
 W is positive definite.
 Z is positive semidefinite.
 lower_bound ~ 3.000009302
 duality_gap ~ 1.6741587e05
* TRYING TO OBTAIN ADDITIONAL CERTIFICATES
* NO CERTIFICATE for "opt lies on boundary"
* CERTIFIED "opt does not lie on facet 1"
* CERTIFIED "opt does not lie on facet 2"
* CERTIFIED "opt does not lie on facet 3"
***********
* SUMMARY *
***********
* CERTIFICATE for optimum in int(cone)
* minimizer_approx = [100000000000000000000 299999814132312270231 149999907066156129824 29999981413231227023
1]
* gamma_lower_bound = 2/sqrt(18750058138478526389/6250000000000000000  log(1))
~ 1.154698748
* gamma_upper_bound = 2/sqrt(299999256056956431493/100000000000000000000  log(1))
~ 1.15470197
* duality_gap ~ 1.6741587e05
* Thanks for your patience...

Input:
Same as in the previous examples.
Call:
pacoop d 0.0001 m 50 q < file.coop
Output:
*** pa ***
*** co ***
*** op ***
* computed possible minimal vectors
1 0
1 1
0 1
* computed interior point
1 0.5 1
* gamma_lower_bound ~ 1.154698748
* gamma_upper_bound ~ 1.15470197
INTERPRETATION:

Possible minimal vectors and an interior point is computed and then an approximated minimizer
is obtained, together with a certified duality gap.

In addition to the previous example pacoop tries to compute certificates for the approximated
minimizer, that prove that it lies in the interior
(implying that it gives a local minimum for the packingcovering problem)
or on the boundary of the cone given by the inequalities.

A lower and upper bound is attained in
"quickanddirtymode".
INSTALLATION:
To install
pacoop
(as well as
coop and
rmd)
you have to install
NTL
(A Library for doing Number Theory) of Victor Shoup before.
Then download the
complete rmd package
and run
make. You may have to
edit the variable
CXXFlags in the
Makefile so that it finds NTL.
If you have trouble to install our software,
please feel free to contact us.