할당 최적화/덮음 덮기

다음 작업을 수행했지만 작동하는 해결책을 찾지 못했습니다.할당 최적화/덮음 덮기

네트워크 노드 배치를위한 최적의 솔루션을 찾아야합니다. 목적은 연결 케이블의 굴착 비용을 최소화하는 것입니다. 일부 파기 비용은 서로에 달려 있습니다. 예 : 2 개의 노드가 연속적으로 있고 첫 번째 케이블을 파다면 두 번째 노드를 파기 위해이 파기 비용을 주먹 노드에 포함 할 필요가 없다고 상상해보십시오. 그러나 두 번째 노드를 선택하기 만하면 노드 1과 노드 1에서 노드 2로 파기 비용을 추가해야합니다.

각 노드마다 특정 수의 사용자가 제공 될 수 있습니다. 최소한 예를 들어 사용자 범위에 도달하려면 사용자의 90 %가 제약 조건입니다.

나는 차 프로그램을 사용하려고하지만 CVX 그것을 좋아하지 않는다 : 더 나은 아이디어를 가진 사람이 예컨대 진 선형 또는 차 프로그래밍을 사용하여 ...

cvx_begin 
variable x(n,1) binary; 
minimize(x'*Q*x) 
subject to 
    x'*A*x >= 0.9; 
cvx_end

있습니까? 감사 BR

출처

2016-11-07 user7125961

''패키지 X는 그것을 좋아하지 않는다. '는 오류 설명이 아니다. 여기서는 도움을받을 수 없습니다. 그리고 네, 바이너리/정수 변수를 통합해야 할 것 같습니다. 키워드 : * 지시자 변수 *. 하지만 지금은 더 많은 것을하는 것은 너무 막연합니다 (''2 개의 노드가 연속적으로 : 어떤 유클리드 공간 격자인가 ...). – sascha

데이터 네트워크의 라우터 또는 집계 지점과 같이 네트워크 토폴로지 측면에서 2 개의 노드가 연속적으로 배치됩니다. CVX 오류 메시지 : 철저한 볼록 프로그래밍 오류 : 잘못된 제약 조건 : {convex}> = {real constant} – user7125961

이것은 제약 조건 인'''x '* A * x> = 0.9'''가 DCP의 규칙에 이를 달성하기 위해서는 문제를 재구성해야합니다. 그러나 우리는 Q가 어떻게 생겼는지 모른다. (단지 주석 :'''x '* A * x <= 0.9'''는 유효한 제약 조건이지만 원하는 것은 아닙니다). – sascha

x'Ax

는 a(i,j)*x(i)*x(j)의 요약입니다. 이와

z(i,j) <= x(i) 
z(i,j) <= x(j) 
z(i,j) >= x(i)+x(j)-1 
z(i,j) in {0,1}

당신이 선형 MIP 문제가 : 제품 z(i,j)=x(i)*x(j)에 의해 선형화 할 수있다. x(i)^2=x(i)z(i,j)

'로 특별하게 처리 할 수

우리는 A와 Q 삼각 행렬을 할 수 있습니다 대칭을
대각선을 이용하여 :

우리는이 공식에서 사용할 수있는 몇 가지 최적화가 있습니다 s는 엄격하게 삼각형 구조로 축소 될 수있다.

출처

2016-11-07 14:43:48

답변

관련 문제