Minizinc 分段线性函数

Question

我有一个成本最小化 problem.In 我们有 3 个供应商的问题。它们是 S1、S2 和 S3，其中成本计算为价格 x 购买数量。

3个供应商的价格值如下。

price=[10,15,20]

如果我有一个决策变量 array[1..3] of var int:purchase，我将从其中获得优化问题的答案，我需要从哪个供应商那里购买多少单位。

示例代码如下

enum suppliers={s1,s2,s3};
int: len_sup=length(suppliers);
set of int:range_sup=1..len_sup;

array[range_sup] of int:price=[10,15,20];
int:demand=40;

array[range_sup] of int:moq=[5,0,5];
array[range_sup] of int:maxoq=[8,20,30];

array[range_sup] of var 0..100:purchase;

constraint sum(i in range_sup)(
purchase[i])=demand
;

constraint forall(i in range_sup)(
purchase[i]>=moq[i] \/ purchase[i]=0
);

constraint forall(i in range_sup)(
purchase[i] <= maxoq[i]
);

var int:cost;

constraint sum(i in range_sup)(
purchase[i]*price[i])=cost;

solve minimize cost;

现在我有一个新要求嵌入价格折扣 this.This 价格折扣肯定会因我们购买的数量而异。

对于这个例子，想象一下，如果我们从任何供应商处购买数量为 1 到 5，那么我们将获得 5% 的价格折扣（价格将从 5% 降低）。如果我们购买 6 到 10 件，我们将获得 10% 的价格折扣。如果我们购买超过 11 个，我们将获得 15% 的价格折扣。

你如何通过分段线性函数将这个东西合并到 model.Is 这个中（因为看起来问题变成了非线性）？有人可以展示如何使用分段线性函数吗？

Answer 1

也许这并不能真正回答您的问题，但对于某些求解器（例如 Gecode、JaCoP 和 OptiMathSAT），您可以为此使用查找 table。

您可以添加一个简单的折扣table:

array[1..3,1..3] of float: discount = array2d(1..3,1..3,
[
 1,5,0.05,  % between 1 and 5: 5% discount
 6,10,0.10, % between 6 and 10: 10% discount
 11,1000,0.15, % 11.. 5: 15% discount
]);

并将成本约束更改为

constraint
cost >= 0 /\
cost =
sum(i in range_sup) (
   purchase[i]*price[i]
    % lookup the discount 
    - purchase[i]*price[i]*sum(r in 1..3) (
          discount[r,3]*(purchase[i] >=  discount[r,1] /\
          purchase[i] <= discount[r,2]
      )
 ;

最优解将是

purchase = array1d(1..3, [8, 20, 12]);
cost = 531;

如前所述，这仅适用于支持 var float 变量和非线性 float_times.

的求解器

更新：suresh_chinthy 询问 piecewise_linear。这是一个如何使用它的例子。请注意，它适用于 Gecode、JaCoP、OptiMathSAT，但不适用于 CBC 等线性求解器，因为 piecewise_linear returns a var float 乘以决策变量 purchase[i]（这是 var inte)，这在 CBC 中是不允许的。

用这两个数组更改上面代码中的 discount table。这里我们假设可以购买 0 到 40 件商品。

% the amount of purchase
array[0..40] of float: discount_base = array1d(0..40,[i | i in 0..40]);
% the discounts for each purchase
array[0..40] of float: discount =
   array1d(0..40,
           [0.0, % 0
            0.05, 0.05, 0.05, 0.05, 0.05, % 1-5
            0.10,0.10,0.10,0.10,0.10, % 6-10,
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 11-20
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 21-30
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 31-40                        
            ]);

并且 cost 约束更改为

constraints
  cost > 0 /\
  cost = 
       sum(i in range_sup) (
       purchase[i]*price[i] - purchase[i]*price[i]* piecewise_linear(1.0*purchase[i], discount_base, discount)
  );

结果同上：

purchase = array1d(1..3, [8, 20, 12]);
cost = 531;

Minizinc 分段线性函数

Minizinc piecewise linear function

minizinc