Solve an integer progam with LattE

latte_max and latte_min use LattE's latte-maximize and latte-minimize functions to find the maximum or minimum of a linear objective function over the integers points in a polytope (i.e. satisfying linearity constraints). This makes use of the digging algorithm; see the LattE manual at http://www.math.ucdavis.edu/~latte for details.

latte_optim(
  objective,
  constraints,
  type = c("max", "min"),
  method = c("lp", "cones"),
  dir = tempdir(),
  opts = "",
  quiet = TRUE,
  shell = FALSE
)

latte_max(
  objective,
  constraints,
  method = c("lp", "cones"),
  dir = tempdir(),
  opts = "",
  quiet = TRUE
)

latte_min(
  objective,
  constraints,
  method = c("lp", "cones"),
  dir = tempdir(),
  opts = "",
  quiet = TRUE
)

Arguments

objective	A linear polynomial to pass to `mp()`, see examples
constraints	A collection of linear polynomial (in)equalities that define the feasibility region, the integers in the polytope
type	`"max"` or `"min"`
method	Method `"LP"` or `"cones"`
dir	Directory to place the files in, without an ending /
opts	Options; see the LattE manual at http://www.math.ucdavis.edu/~latte
quiet	Show latte output
shell	Messages the shell code used to do the computation

Value

A named list with components par, a named-vector of optimizing arguments, and value, the value of the objective function at the optimial point.

Examples



if (has_latte()) {

latte_max(
  "-2 x + 3 y",
  c("x + y <= 10", "x >= 0", "y >= 0")
)

latte_max(
  "-2 x + 3 y",
  c("x + y <= 10", "x >= 0", "y >= 0"),
  quiet = FALSE
)


df <- expand.grid("x" = 0:10, "y" = 0:10)
df <- subset(df, x + y <= 10L)
df$objective <- with(df, -2*x + 3*y)
library("ggplot2")
ggplot(df, aes(x, y, size = objective)) +
  geom_point()

latte_min(
  "-2 x + 3 y",
  c("x + y <= 10", "x >= 0", "y >= 0"),
  method = "cones"
)



latte_min("-2 x - 3 y - 4 z", c(
  "3 x + 2 y + z <= 10",
  "2 x + 5 y + 3 z <= 15",
  "x >= 0", "y >= 0", "z >= 0"
), "cones", quiet = FALSE)





}
#> 
#> This is LattE integrale 1.6
#> Available from http://www.math.ucdavis.edu/~latte/
#> 
#> Invocation: /Applications/latte/bin/latte-maximize.bin /var/folders/r3/126_d6t55f5d32tplbg5mk1d0c48s9/T//RtmpugrA1n/2020_03_17_23_45_35_CWowK4ZE6k/optim_code
#> 
#> Checking whether the input polytope is empty or not...size = 3 x 3
#> Number Type = rational
#> done.
#> Removing redundant inequalities and finding hidden equalities....done.
#> Reading problem.
#> 
#> Time: 0.007346 sec
#> 
#> Computing vertices and edges with cdd...size = 3 x 3
#> Number Type = integer
#> (Initially added rows ) = 2 3 4 
#> (Iter, Row, #Total, #Curr, #Feas)=     4     1         5      3      3
#> done.
#> Reading .ext file...done.
#> Reading .ead file...done.
#> Computing LP... size = 3 x 3
#> Number Type = integer
#> done.Reading .lps file...done.
#> A vertex which we found via LP is: [0 10]
#> The LP optimal value is: 30
#> Dualizing all cones...All cones are now dualized.
#> Time for dualizing general cones: 0 sec
#> Decomposing all cones.
#> Triangulating cone... done.
#> Triangulating cone... done.
#> Triangulating cone... done.
#> All cones have been decomposed.
#> 3 cones in total.
#> Computing the points in the Parallelepiped of the unimodular Cones.
#> Finished computing a rational function. 
#> Time: 0.009767 sec.
#> 
#> There is one optimal solution. 		
#> An optimal solution for [-2 3] is: [0 10].
#> The projected down opt value is: 30
#> The optimal value is: 30.
#> The gap is: 0
#> Computation done.
#> Time: 0.018309 sec.
#> 
#> This is LattE integrale 1.6
#> Available from http://www.math.ucdavis.edu/~latte/
#> 
#> Invocation: /Applications/latte/bin/latte-minimize.bin /var/folders/r3/126_d6t55f5d32tplbg5mk1d0c48s9/T//RtmpugrA1n/2020_03_17_23_45_35_G0zbi4QGpw/optim_code
#> 
#> Checking whether the input polytope is empty or not...size = 5 x 4
#> Number Type = rational
#> done.
#> Removing redundant inequalities and finding hidden equalities....done.
#> Reading problem.
#> 
#> Time: 0.009862 sec
#> 
#> Computing vertices and edges with cdd...size = 5 x 4
#> Number Type = integer
#> (Initially added rows ) = 3 4 5 6 
#> (Iter, Row, #Total, #Curr, #Feas)=     5     1         7      4      2
#> (Iter, Row, #Total, #Curr, #Feas)=     6     2        11      6      6
#> done.
#> Reading .ext file...done.
#> Reading .ead file...done.
#> Computing LP... size = 5 x 4
#> Number Type = integer
#> done.Reading .lps file...done.
#> A vertex which we found via LP is: [0 0 5]
#> The LP optimal value is: -20
#> Dualizing all cones...All cones are now dualized.
#> Time for dualizing general cones: 0 sec
#> Decomposing all cones.
#> Triangulating cone... done.
#> Triangulating cone... done.
#> Triangulating cone... done.
#> Triangulating cone... done.
#> Triangulating cone... done.
#> Triangulating cone... done.
#> All cones have been decomposed.
#> 24 cones in total.
#> Computing the points in the Parallelepiped of the unimodular Cones.
#> Finished computing a rational function. 
#> Time: 0.015672 sec.
#> 
#> There is one optimal solution. 		
#> An optimal solution for [-2 -3 -4] is: [0 0 5].
#> The projected down opt value is: -20
#> The optimal value is: -20.
#> The gap is: 0
#> Computation done.
#> Time: 0.023693 sec.
#> $par
#> x y z 
#> 0 0 5 
#> 
#> $value
#> [1] -20
#>

Arguments

Value

Examples

Contents