quadprog не может найти решение

Я пытаюсь оптимизировать расположение набора коробок w.r.t. места их вешалок s.t. ящики максимально выровнены со своими вешалками и не вытесняют друг друга. С помощью квадропрограммы.

Давы:

1.  box hanger x-locations (P). =710  850  990 1130
2.  box-sizes (W). =690 550 690 130 
3.  usable x-spread tuple (S). =-150 2090
4.  number of boxes (K). =4
5.  minimum interbox spread (G). =50
6.  box x-locations (X). =objective

Мы видим, что общий требуемый разброс по оси x равен sum(W) + 3G = 2060 + 150 = 2210, тогда как доступный разброс по оси x равен S[2] - S1 = 2240. Итак, решение должно существовать.

Мин:

sumof (P[i] – X[i])^2

s.t.:

(1) X[i+i] – X[i] >= G + ½ ( W[i+1] + W[i] ); i = 1..(K-1), т.е. ящики не вытесняют друг друга

        -X[i] + X[i+1] >= -( -G – ½ (W[i+1] + W[i]) )

(2) X1 >= S[left] + ½ W1 и (3) X[K] ‹= S[right] – ½ W[K], т.е. ящики находятся в пределах заданного x-разброса

        X[1] >= - ( S[left] + ½ W[1] )
        -X[K] >= - ( S[right] – ½ W[K] )

всего 5 ограничений - 3 для межбоксового разворота и 2 для конечностей.

in R:

> Dmat = matrix(0,4,4)
> diag(Dmat) = 1
> dvec = P, the hanger locations
[1]  710  850  990 1130
> bvec 
[1] -670 -670 -460 -195 2025
> t(Amat)
     [,1] [,2] [,3] [,4]
[1,]   -1    1    0    0
[2,]    0   -1    1    0
[3,]    0    0   -1    1
[4,]    1    0    0    0
[5,]    0    0    0   -1
> solve.QP(Dmat, dvec, Amat, bvec)
Error in solve.QP(Dmat, dvec, Amat, bvec) : 
  constraints are inconsistent, no solution!

Совершенно очевидно, что я пропустил или неправильно определил проблему (Пакет 'quadprog'< /а>)! Я использую quadprog, так как нашел его порт JavaScript.

Большое спасибо.


r quadprog
person Dinesh    schedule 12.07.2015    source источник
comment
Ваше утверждение о том, что S[2] - S1 = 2240, неверно для заданных значений S[1] и S[2]. Однако, если вы измените знак S[1] так, чтобы S[1] = -150, тогда ваша математика работает, иsolve.QP возвращает решение.   -  person WaltS    schedule 13.07.2015
comment
Вы правы, должно было быть -150.   -  person Dinesh    schedule 13.07.2015

Ответы (2)


arrow_upward
1
arrow_downward

Я не уверен, что это решает вашу физическую проблему, но приведенный ниже код, похоже, решает проблему оптимизации, как вы ее указали. Я обобщил его на переменное количество ящиков и включил график для проверки решения.

  library(quadprog)
  p  <- c(710,  850,  990, 1130)   # hanger positions
  w  <- c(690, 550, 690, 130)      # box widths
  g <- 50                          # min box separation
  s <- c(-150, 2390)               # min and max postions of box edges

  k <- length(w)                   # number of boxes
  Dmat <- 2*diag(nrow=k)
  dvec <- p
# separation constraints
  Amat <- -diag(nrow=k,ncol=(k-1))
  Amat[lower.tri(Amat)] <- unlist(lapply((k-1):1, function(n) c(1,numeric(n-1))))
  bvec <- sapply(1:(k-1), function(n) g + (w[n+1]+w[n])/2)
# x-spread constraints
  Amat <- cbind(Amat, c(1,numeric(k-1)), c(numeric(k-1),-1))
  bvec <- c(bvec, s[1] + w[1]/2, -(s[2] - w[k]/2))

  sol <- solve.QP(Dmat, dvec, Amat, bvec)
  plot(x=s, y=c(0,0), type="l", ylim=c(-2.5,0))
  points(x=p, y=numeric(k), pch=19)
  segments(x0=sol$solution, y0=-1, x1=p, y1=0)
  rect(xleft=sol$solution-w/2, xright=sol$solution+w/2, ytop=-1.0, ybottom=-2, density=8)

введите здесь описание изображения

person WaltS    schedule 13.07.2015

arrow_upward
1
arrow_downward

Проблема заключается в настройке Amat, bvec или обоих. solve.QP пытается найти решение b задачи квадратичного программирования с учетом ограничения, которое

t(Amat)*b >= bvec

Расширяя это ограничение в вашем примере, мы хотим найти вектор b := c(b[1], b[2], b[3], b[4]), который удовлетворяет условиям:

  • -b[1] + b[2] >= -670,

  • -b[2] + b[3] >= -670,

  • -b[3] + b[4] >= -460,

  • b[1] >= -195

  • и -b[4] >= 2025 (т. е. b[4] <= -2025).

Однако, сложив вместе первые четыре неравенства, мы получим b[4] >= -670-670-460-195 = -1995. Другими словами, b[4] должно быть больше -1995 и меньше -2025. Это противоречие, и поэтому solve.QP не может найти решения.

Попытка этого примера с ограничением -b[4] >= -2025 путем установки bvec = c(-670, -670, -460, -195, -2025) дает решение. Не вдаваясь слишком глубоко в вашу формулировку выше, возможно, это было задумано (или другое из этих значений должно было быть положительным)?

person N McWilliams    schedule 12.07.2015
comment
Спасибо, я внес поправку. Я получаю результат (710 850 990 1130), но это приводит к перекрытию полей, поэтому, думаю, мне нужно вернуться к чертежной доске - может потребоваться больше ограничений - person Dinesh; 13.07.2015
comment
Кстати, в документе quadprog указано, что он решает t(Amat)*b >= -bvec, а это не то, что вы написали. Уточнение, пожалуйста? - person Dinesh; 13.07.2015
comment
Это не говорит об этом. В нем говорится, что он находит вектор b, который минимизирует -t(dvec)*b + 0.5*t(b)*Dmat*b, или, другими словами, из ?solve.QP, решает задачи квадратичного программирования вида min(-d^T b + 1/2 b^T D b), но с ограничениями A^T б ›= б_0. То есть любое найденное b должно также удовлетворять t(Amat)*b >= bvec, что я и написал изначально. - person N McWilliams; 13.07.2015