문제 : Bob의 판매

문제 : Bob의 판매

---

참고 : 이것은 SWF 파일의 레코드 순서 지정과 관련된 실제 문제를 추상적으로 바꾸어 놓은 것입니다. 솔루션은 오픈 소스 애플리케이션을 개선하는 데 도움이됩니다.

Bob은 상점이 있고 판매를 원합니다. 그의 상점에는 여러 제품이 있으며, 그는 재고에있는 각 제품의 특정 정수 단위 수량을 보유하고 있습니다. 그는 또한 많은 선반에 부착 된 가격 레이블 (제품 수만큼)을 가지고 있으며 가격은 이미 인쇄되어 있습니다. 그는 모든 제품에 어떤 가격 레이블 (해당 제품의 전체 재고에 대한 한 품목의 단가)을 표시 할 수 있지만 일부 제품에는 추가 제한이 있습니다. 이러한 제품은 특정 다른 제품보다 저렴하지 않을 수 있습니다.

Bob의 모든 상품의 총 비용이 가능한 한 낮도록 가격 레이블을 정렬하는 방법을 찾아야합니다. 총 비용은 각 제품에 할당 된 가격 레이블에 해당 제품의 재고 수량을 곱한 합계입니다.

---

주어진:

• N – 제품 및 가격 레이블 수
• S _i , 0≤ i <N – 인덱스가 i 인 제품 재고 수량 (정수)
• P _j , 0≤ j <N – 인덱스 j (정수)가있는 가격 레이블의 가격
• K – 추가 제약 쌍의 수
• A _k , B _k , 0≤ k <K – 추가 제약 조건에 대한 제품 색인
  • 모든 제품 인덱스는 B에 한 번만 나타날 수 있습니다. 따라서이 인접 목록에 의해 형성된 그래프는 실제로 방향성 트리 집합입니다.

프로그램은 다음을 찾아야합니다.

• M _i , 0≤ i <N – 제품 인덱스에서 가격 레이블 인덱스로 매핑 (P _{M i} 는 제품 i의 가격 임 )

조건을 충족하려면 :

1. P _{M A k} ≤ P _{M B k} , 0≤ k <K 인 경우
2. 0≤ i <N에 대한 Σ (S _i × P _{M i} ) 는 최소입니다.

---

첫 번째 조건이 아닌 경우 솔루션은 단순히 가격별로 라벨을 정렬하고 수량별로 제품을 정렬하고 둘 다 직접 일치시키는 것입니다.

입력의 일반적인 값은 N, K <10000입니다. 실제 문제에는 몇 가지 고유 한 가격표 (1,2,3,4) 만 있습니다.

---

다음은 토폴로지 정렬을 포함한 대부분의 간단한 솔루션이 작동하지 않는 이유에 대한 한 가지 예입니다.

수량이 1 ~ 10 인 품목 10 개와 가격이 $ 1 ~ $ 10 인 가격 레이블 10 개가 있습니다. 한 가지 조건이 있습니다. 수량이 10 인 품목은 수량이 1 인 품목보다 저렴하지 않아야합니다.

최적의 솔루션은 다음과 같습니다.

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

총 비용은 $ 249입니다. 1,10 페어를 양쪽 극단 근처에 배치하면 총 비용이 더 높아집니다.

---

문제는 일반적인 경우의 NP 완전성입니다. 이것은 3 분할 (빈 패킹의 여전히 강력한 NP- 완전 버전)의 감소를 통해 확인할 수 있습니다.

하자 w는 ₁ , ..., w는 _N 이 3 분할 경우의 물체의 중량이 될 수 있도록 , b는 빈 크기 및 수 K = / 3 N 채워질 수있다 빈들의 수. 따라서 빈당 정확히 3 개의 개체가 있도록 개체를 분할 할 수있는 경우 3 개의 파티션이 있습니다.

감소를 위해 N = kb로 설정 하고 각 bin은 동일한 가격의 b 가격 레이블로 표시됩니다 (P _i가 b 번째 레이블 마다 증가 한다고 생각해보십시오 ). 하자 t _i가 , 1≤ i가 ≤ k는 상기에 상응하는 라벨의 금액이 I 번째 빈. 각 w _i에 대해 수량 w _i + 1 의 하나의 제품 S _j (이것을 w _i 의 루트 제품이라고 부릅니다 )와 다른 w _i - S _j 보다 저렴해야하는 수량 1의 1 개 제품이 있습니다. (이것을 휴가 제품이라고 부릅니다).

들면 t _난 (2B + 1) = ^I가 , 1≤ i가 ≤ k는 , 3 분할이있는 경우와 밥에 판매 될 수있는 경우에만 2B Σ _{1≤ I ≤ K} t _I :

• 3 분할에 대한 솔루션이있는 경우 동일한 빈에 할당 된 객체 w _i , w _j , w _l에 해당하는 모든 b 제품 에 제한 사항을 위반하지 않고 동일한 가격으로 레이블을 지정할 수 있습니다. 따라서 솔루션의 비용은 2b Σ _{1≤ i ≤ k} t _i입니다 (가격이 t _i 인 제품의 총 수량 이 2b 이므로 ).
  
• Bob 's Sale의 최적 솔루션을 고려하십시오. 먼저 어떤 솔루션에서든 3 개 이상의 루트 제품이 동일한 가격 레이블을 공유한다는 점을 관찰하십시오. "너무 많은"각 루트 제품에 대해 3 개 미만의 루트 제품에 고정되는 저렴한 가격표가 있습니다. 이것은 가격 레이블 당 루트 제품이 정확히 3 개 (존재하는 경우) 인 솔루션보다 더 나쁩니다.
  이제 가격 당 3 개의 루트 레이블이있는 Bob 's Sale의 솔루션이 여전히있을 수 있지만 휴가 제품은 동일한 가격 레이블을 사용하지 않습니다 (통이 흘러 넘치는 종류). 가장 비싼 가격 라벨 에 더 저렴한 태그가 달린 잎 제품이있는 w _i 의 루트 제품을 태그한다고합시다 . 이것은 3 개의 루트 레이블 w _i , w _j , w _l가장 비싼 가격으로 태그를 붙이면 b 가되지 않습니다 . 따라서이 가격으로 태그가 지정된 제품의 총 비용은 최소 2b + 1 입니다.
  따라서 이러한 솔루션의 비용은 t _k (2b + 1) + 다른 할당 비용입니다. 기존 3 개 파티션의 최적 비용은 2b Σ _{1≤ i ≤ k} t _i 이므로 방금 고려한 사례가 더 나쁘다는 것을 보여야합니다. 이것은 t _k > 2b Σ _{1≤ i ≤ k-1} t _{i 인 경우입니다} ( 이제 합에서 k-1이 됩니다). t _i 설정= (2b + 1) ⁱ , 1≤ i ≤ k , 이것이 사실입니다. 이것은 또한 가장 비싼 가격표가 "나쁜"가격표는 아니지만 다른 것이라면 유효합니다.

따라서 이것은 파괴적인 부분입니다 ;-) 그러나 다른 가격표의 수가 일정하다면 다항식 시간에 그것을 풀기 위해 동적 프로그래밍을 사용할 수 있습니다.

---

이 문제는 CS 문헌에서 고려 된 많은 스케줄링 문제와 유사합니다. 하나로서 다시 말씀 드리겠습니다.

문제 ( "우선 순위, 가중치 및 일반적인 지연 페널티가있는 비 선점 단일 시스템 스케줄링")

입력:

• 작업 1,…, n

• 작업에 대한 "나무와 같은"우선 순위 관계 (Hasse 다이어그램은 포리스트 임)

• 가중치 w ₍₁₎ , ..., w _N

• {1,…, n}에서 Z ₊ 까지 감소하지 않는 지연 패널티 함수 L (t)

산출:

• 모든 i prec j에 대해 π (i) <π (j)를 갖는 제약 조건에 따라 ∑ _j w _j L (π (j))를 최소화하는 {1,…, n}의 순열 π .

서신 : 직업 <=> 제품; i prec j <=> i는 j보다 가격이 낮습니다. 무게 <=> 수량; L (t) <=> t ^번째 최저 가격

L이 선형이면 Horn [1]으로 인해 효율적인 다항식 시간 알고리즘이 있습니다. 이 기사는 급여 벽 뒤에 있지만 주요 아이디어는

1. 모든 j에 대해 j와 평균 가중치가 최대 인 후속 작업 만 포함하는 연결된 작업 집합을 찾습니다. 예를 들어, n = 6이고 선행 제약 조건이 1 prec 2 및 2 prec 3 및 2 prec 4 및 4 prec 5 인 경우 2에 대해 고려중인 세트는 {2}, {2, 3}, {2, 4입니다. }, {2, 3, 4}, {2, 4, 5}, {2, 3, 4, 5}. 실제로 동적 프로그래밍에 의해 상향식으로 계산할 수있는 최대 평균 가중치 만 필요합니다.

2. 관련 세트의 평균 가중치 순서대로 작업을 탐욕스럽게 예약합니다.

CyberShadow의 예에서는 n = 10 및 1 prec 10 및 w _j = j 및 L (t) = t가 있습니다. 1 단계에서 계산 된 값은 다음과 같습니다.

• 직업 1 : 5.5 (평균 1과 10)

• 직업 2 : 2

• 직업 3 : 3

• 작업 4 : 4

• 직업 5 : 5

• 직업 6 : 6

• 직업 7 : 7

• 직업 8 : 8

• 직업 9 : 9

• 작업 10:10

최적의 순서는 9, 8, 7, 6, 1, 10, 5, 4, 3, 2입니다.

---

이 알고리즘은 최적의 증명이 로컬 개선을 사용하기 때문에 L의 다른 선택에 대해서도 실제로 잘 작동 할 수 있습니다. 또는 CS Theory Stack Exchange의 누군가가 아이디어를 가지고있을 것입니다.

[1] WA 혼. 트리 형 우선 순위 및 선형 지연 페널티를 사용하는 단일 머신 작업 시퀀스 . 응용 수학에 관한 SIAM 저널, Vol. 23, No. 2 (1972 년 9 월), pp. 189–202.

---

문제가 재미 있다고 생각했기 때문에 제약 프로그래밍을 사용하여 솔루션을 찾는 모델을 만들었습니다. 모델은 MiniZinc 라는 모델링 언어로 작성되었습니다 .

include "globals.mzn";

%%% Data declaration
% Number of products
int: n;
% Quantity of stock
array[1..n] of int: stock;
% Number of distinct price labels
int: m;
% Labels
array[1..m] of int: labels;
constraint assert(forall(i,j in 1..m where i < j) (labels[i] < labels[j]),
              "All labels must be distinct and ordered");
% Quantity of each label
array[1..m] of int: num_labels;
% Number of precedence constraints
int: k;
% Precedence constraints
array[1..k, 1..2] of 1..n: precedences;

%%% Variables
% Price given to product i
array[1..n] of var min(labels)..max(labels): prices :: is_output;
% Objective to minimize
var int: objective :: is_output;

%%% Constraints
% Each label is used once
constraint global_cardinality_low_up_closed(prices, labels, num_labels, num_labels);

% Prices respect precedences
constraint forall(i in 1..k) (
            prices[precedences[i, 1]] <= prices[precedences[i, 2]]
       );

% Calculate the objective
constraint objective = sum(i in 1..n) (prices[i]*stock[i]);

%%% Find the minimal solution
solve minimize objective;

문제에 대한 데이터는 별도의 파일로 제공됩니다.

%%% Data definitions
n = 10;
stock = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
m = 10;
labels = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
num_labels = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
k = 1;
precedences = [| 1, 10 |];

이 모델은 상당히 순진하고 간단하며 멋진 것은 아닙니다. 예제 문제를 해결하기 위해 Gecode 백엔드를 사용하면 다음 출력이 생성됩니다 (모델이 model.mzn에 있고 데이터가 data.dzn에 있다고 가정).

$ mzn2fzn -I/usr/local/share/gecode/mznlib/ model.mzn data.dzn
$ fz -mode stat -threads 0 model.fzn 
objective = 265;
prices = array1d(1..10, [1, 10, 9, 8, 7, 6, 5, 4, 3, 2]);
----------
objective = 258;
prices = array1d(1..10, [2, 10, 9, 8, 7, 6, 5, 4, 1, 3]);
----------
objective = 253;
prices = array1d(1..10, [3, 10, 9, 8, 7, 6, 5, 2, 1, 4]);
----------
objective = 250;
prices = array1d(1..10, [4, 10, 9, 8, 7, 6, 3, 2, 1, 5]);
----------
objective = 249;
prices = array1d(1..10, [5, 10, 9, 8, 7, 4, 3, 2, 1, 6]);
----------
==========

%%  runtime:       0.027 (27.471000 ms)
%%  solvetime:     0.027 (27.166000 ms)
%%  solutions:     5
%%  variables:     11
%%  propagators:   3
%%  propagations:  136068
%%  nodes:         47341
%%  failures:      23666
%%  peak depth:    33
%%  peak memory:   237 KB

더 큰 문제의 경우 물론 훨씬 느리지 만 일반적으로 모델은 시간이 지남에 따라 연속적으로 더 나은 솔루션을 생성합니다.

---

커뮤니티 위키로 생각을 게시하고 자유롭게 편집하십시오.

이 문제는 모든 노드가 부모의 오른쪽에 있어야 하는 방식으로 위쪽에서 아래쪽 트리 세트를 배치하거나 재 배열해야하는 추가 제약 조건을 고려하면 시각화하기가 더 쉽습니다 (왼쪽의 제품은 더 저렴하고 오른쪽에있는 것이 더 비쌉니다).

Let's say that two products are conflicting if the first has more stock than the second, and yet the first must not be cheaper than the other (so they are being "pulled" in different directions price-wise). Similarly, a conflicting group of products is one where at least two products are conflicting, and none of its products conflicts with any product outside the group.

We can make a few observations:

1. When "placing" (assigning a price tag to) two conflicting products, they will always be next to each other.
2. If you sort all products by quantity disregarding constraints, and then arrange them optimally so they satisfy the constraints, then the final positions of all products in a conflicting group will always be between (inclusively) the leftmost and rightmost initial positions of the products.
3. 따라서 하단 하위 트리에서 제품의 초기 위치 범위와 트리 루트 경로가 겹치지 않도록 트리에서 오른쪽을 가리키는 단일 가장자리를 제거하여 제약 트리를 두 개로 분할 할 수 있다면 안전하게 할 수 있습니다. 두 개의 별개의 제약 트리 (또는 단일 노드)로 취급하고 둘 사이에 종속성이 있음을 잊어 버리십시오. ( 간단한 예 )

알고리즘 아이디어 :

1. 첫째, 제한에 구애받지 않는 모든 제품을 배치하십시오.
2. 각 제약 트리에 대해 :
   1. 오른쪽을 가리키는 모든 가장자리 (충돌하지 않는 제품 사이의 가장자리)에서 하위 트리로 분할합니다. 이제 모든 가장자리가 왼쪽을 가리키는 하위 트리 집합이 있습니다.
   2. 각 하위 트리에 대해 :
      1. 토폴로지별로 정렬 된 목록 가져 오기
      2. Try to insert this list at every position starting from the lowest to highest initial positions of the products in this subtree, settle on the one which yields lowest total price
   3. For each edge removed in step 2.1:
      1. If the new positions for two subtrees are "conflicting":
         1. Concatenate the higher with the lower list (special case of topological sort)
         2. Similarly try to find the optimal position for the concatenated list
         3. For future merging, consider the two examined subtrees as one subtree

The main problem with this algorithm is how to deal with displacement of already-placed constrained pairs. I imagine that simply trying to re-place displaced chains by iterative search might work, but the algorithm already looks too complicated to work right.

In the case that the number of distinct prices is low, you can use a deque (or doubly-linked list) for each distinct price, holding all the items with that price assigned to them. The deques are ordered from lowest to highest price. Inserting an item into a deque shifts the last item into the start of next deque (for the next higher distinct price), and so on for all deques after that.

One thing to note about iterative / bubble-sort-ish algorithms: when you have a conflicting pair of products, it is not enough to greedily walk in either direction by one position until the next one does not yield an improvement. Here is a test case I got by playing around a bit with Mathematica writing a test case generator:

Price, $   1 2 7 9
Qty        3 2 1 4

The constraint is to have the 4-qty item to the right of the 1-qty item. As shown above, the total price is $50. If you move the pair one position to the left (so it's 3 1 4 2), the total goes up to $51, but if you go once further (1 4 3 2) it goes down to $48.

---

This is a follow-up on Gero's answer. The idea is to modify his construction to show strong NP-hardness.

Instead of choosing $t_i=(2b+1)^i$, chose $t_i=i$. Now, you have to modify the argument that a solution with prize $P=2b\sum_{1\leq i \leq k} t_i$ implies that there exists a 3-partition.

Take an arbitrary shelf order. Do the accounting in the following way: distribute $w_i-1$ units of quantity of the root-product to its leaf-products. Then every product has quantity 2. By definition of the constraints, this does not shift to a higher price. After this shifting, the price will be exactly $P$. If the shifting moved some quantity to a lower prize, the original prize was strictly larger than $P$.

Hence, it is only possible to achieve the claimed prize, if all leaf-products have the same prize as their root-product, which means that there exists a 3-partition.

Citing the result from a SWAT 2010 paper this argument shows that even with unary encoding of the numbers and $k$ different price tags, a running time of $f(k)\cdot n^{O(1)}$ would violate "standard complexity assumptions". This makes the hinted at dynamic programming with a running time of $n^{O(k)}$ look not so bad.

---

This is cross-posted from the same answer at cstheory.

---

You could try first solving the simpler case where you simply have to sort labels by price and products by quantity, and match both directly, and then use an evolutionary process on this first approximation: generate random variations of the ordered list of products that you have, shifting a small number of random selected items up or down the list just a few places, calculate the total cost of each variation on the list, keep the best few and make those the basis of your next generation. Iterating this process over a number of generations should eventually, I expect, give you the right answer to your problem, in a fraction of the time it would take to brute force the solution.

---

One way to attack the problem is to express it using 0-1 linear programming and solve it using Balas' Additive Algorithm. Here's how the problem could be encoded:

• Variables: N² binary variables. For the sake of clarity I will index them by two integers: x_ij is 1 if and only if product i is assigned label j.
• Objective function: minimize sum over i and j of S_iP_jx_ij (represents the original objective function).
• Constraint: for each k sum over j of P_jx_Akj – P_jx_Bkj is ≤ 0 (represents the original price constraints).
• Constraints: for each i sum over j of x_ij is 1; for each j sum over i of x_ij is 1 (says that x encodes a permutation).

I'm not an expert in linear programming, probably there exists a more efficient encoding.

---

Generate the permutations of the prices in lexicographic order, and return the first one that fits the constraints.

Assuming products and prices are already sorted (fewest to most, and highest to lowest, respectively),

1. Set l[k] = k+1 for 0 <= k < n and l[n] = 0. Then set k = 1.
2. Set p = 0, q = l[0].
3. Set M[k] = q. If any price constraint specifically involving P[k] fails, go to 5. Otherwise, if k = n, return M[1]...M[n].
4. Set u[k] = p, l[p] = l[q], k = k + 1 and go to 2.
5. Set p = q, q = l[p]. If q != 0 go to 3.
6. Set k = k - 1, and terminate if k = 0. Otherwise, set p = u[k], q = M[k], l[p] = q and go to 5.

This is (a slight modification of) Algorithm X from Knuth's Art of Computer Programming, Volume 4, Fascicle 2, Section 7.2.1.2. As with most of Knuth's algorithms, it uses 1-based indexing. Hacking it to fit the 0-based indexing of your typical programming language I leave as an exercise for the reader.

Edit:

Unfortunately, it turns out that this doesn't guarantee a non-decreasing sequence. I'll have to give it more thought to see if this can be salvaged.

참고URL : https://stackoverflow.com/questions/4898511/problem-bobs-sale