# User's Guide for coop (covering optimizer)

coop is an application of rmd (rigorous MAXDET) which is a mathematically rigorous wrapper for the package MAXDET of Wu, Vandenberghe and Boyd. coop can be used to approximate optimal lattice sphere coverings. Furthermore, coop gives lower and upper bounds of the covering density for the optimal lattice covering. 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:

```coop [options] < file
Options:
-h   show this help
-b   read and exclude boundary facets
-c   certify local optimality
-d x set duality gap to x
-m N set maximum iterations to N
-q   quick and dirty (non-rigorous)
-v   be verbose
-n   be non-verbose
```

### 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
• 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 non-positive 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:

1. Input:
Create a file input.coop containing (in that order) dimension, data for simplex, basis, inequalities, maximum number of iterations and duality gap:
```2

1
1 0
1 1

3
1
0 0
0
1 0
0
0 1

3
0 -2 0
0 2 2
2 2 0

100

1e-5
```

Call:
```coop < input.coop
```

Output:
```*** co ***
*** op ***

* computed interior point
1 -0.5 1

- SOLVING MAXDET PROBLEM
- starting MAXDET (workspace = 535)
iters         primal           dual
2        -1.642480        -7.642480
4        -1.909503        -1.909738
6        -1.909543        -1.909543
9        -1.909543        -1.909543
- MAXDET stopped because duality_gap reached.
- primal value = -1.909542505
- dual value   = -1.909542505
- minimizer = 3 -1.5 3
- minimizer_approx = [100000000000000000000 299999999999802691164 -149999999999901367787 299999999999801536532]

- CHECKING PRIMAL SOLUTION
- G(x) is positive definite.
- F(x) is positive semidefinite.
- upper_bound ~ -1.909542505

- CHECKING DUAL SOLUTION
- Tr G_i W + Tr F_i Z = c_i.
- W is positive definite.
- Z is positive semidefinite.
- lower_bound  ~ -1.909542505
- duality_gap ~ 7.929101818e-12

***********
* SUMMARY *
***********

* minimizer_approx = [100000000000000000000 299999999999802691164 -149999999999901367787 299999999999801536532]
* theta_lower_bound = 1/sqrt(exp(198230321/25000000000000000000 - log(740740740741719125903704026765674793287/5000000000000000000000000000000000000000)))
~ 0.3849001795
* theta_upper_bound = 1/sqrt(exp(0 - log(10000000000000000000000000000000000000000/67499999999910857972700029430282418325879)))
~ 0.3849001795
* duality_gap ~ 7.929101818e-12
```

2. Input:
Take same input as in the previous example, but possibly without number of maximum iterations and duality gap.
```
```

Call:
```coop -d 0.0001 -m 50 -c < input.coop
```

Output:
```*** co ***
*** op ***

* computed interior point
1 -0.5 1

- SOLVING MAXDET PROBLEM
- starting MAXDET (workspace = 535)
iters         primal           dual
2        -1.642480        -7.642480
4        -1.909503        -1.909738
6        -1.909542        -1.909544
- MAXDET stopped because duality_gap reached.
- primal value = -1.909542278
- dual value   = -1.909543638
- minimizer = 2.99999966 -1.49999983 2.99999966
- minimizer_approx = [50000000000000000000 149999983003100068046 -74999991501550047493 149999983003099490730]

- CHECKING PRIMAL SOLUTION
- G(x) is positive definite.
- F(x) is positive semidefinite.
- upper_bound ~ -1.909542278

- CHECKING DUAL SOLUTION
- Tr G_i W + Tr F_i Z = c_i.
- W is positive definite.
- Z is positive semidefinite.
- lower_bound  ~ -1.909543638
- duality_gap ~ 1.359752956e-06

* 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 = [50000000000000000000 149999983003100068046 -74999991501550047493 149999983003099490730]
* theta_lower_bound = 1/sqrt(exp(33993823892359/25000000000000000000 - log(185185227152847362204403558894956470769/1250000000000000000000000000000000000000)))
~ 0.3848999614
* theta_upper_bound = 1/sqrt(exp(0 - log(2500000000000000000000000000000000000000/16874996175697643363415514173940390628531)))
~ 0.3849002231
* duality_gap ~ 1.359752956e-06
```

3. Input:
Same as in the previous examples.
```
```

Call:
```coop -d 0.0001 -m 50 -q < file.coop
```

Output:
```*** co ***
*** op ***

* computed interior point
1 -0.5 1

* theta_lower_bound ~ 0.3848999614
* theta_upper_bound ~ 0.3849002231
```

### INTERPRETATION:

1. An interior point is computed and then an approximated minimizer is obtained, together with a certified duality gap.
2. In addition to the previous example coop 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 covering problem) or on the boundary of the cone given by the inequalities.
3. A lower and upper bound is attained in "quick-and-dirty-mode".

### INSTALLATION:

To install coop (as well as pacoop 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.