如何在 opl 整数程序中模拟连续位置？

Question

有人可以为这个 MIP 问题建模吗？我想不出一种方法来模拟约束“所有相同颜色的球必须位于连续的位置”

问题描述：

There are 10 locations: 1 to 10, loc 1 worth , loc 2 worth  ... loc 10 worth 
There are 10 balls: b1 to b10
There are 3 colors: red, green, blue. red worth , green worth , blue worth 

assign each ball to a color and a distinctive location so that:

all balls of the same color are next to each other in consecutive locations. for example, all red balls take location 4,5,6 is ok, but not 4,5,8
no color can be assigned to more than 4 balls
each color has to be assigned to at least 1 ball

ball in a location is worth $color * $loc, for example, red ball in loc 5 =  *  = 

maximize total worth of the assignment

很明显解是：蓝，蓝，绿，绿，绿，绿，红，红，红，红

这是一个说明性问题，用于了解如何在 mip 中对连续约束进行建模。

我下面的opl程序连邻接约束都没有，耗时很长，这么小的问题，我做错了什么？

range locations = 1..10;
int nbcolors=3;
int reward[l in locations]=l;
range colors=1..nbcolors;
string colorNames[colors]=["blue","green","red"];

dvar boolean assign[colors][locations];

dexpr int color[l in locations] = sum(c in colors) assign[c][l] * c;
dexpr int totalworth=sum(l in locations) color[l]*reward[l];
maximize totalworth;
subject to
{
  //each location assigned once
  forall(l in locations) sum(c in colors) assign[c][l] == 1;
  // no color can be assigned to more than 4 balls
  forall(c in colors) sum(l in locations) assign[c][l] <= 4;
  //each color has to be assigned to at least 1 ball
  forall(c in colors) sum(l in locations) assign[c][l] >= 1;
}

感谢您的帮助。

Answer 1

我会写

using CP;
range locations = 1..10;
int nbcolors=3;
int reward[l in locations]=l;
range colors=1..nbcolors;
string colorNames[colors]=["blue","green","red"];

dvar int color[locations] in colors;

dexpr int totalworth=sum(l in locations) color[l]*reward[l];
maximize totalworth;
subject to
{
  // no color can be assigned to more than 4 balls
   //each color has to be assigned to at least 1 ball
  forall(c in colors) 1<=count(color,c)<=4;
  
  // consecutive locations
  sum(l in locations:l!=1) (color[l]!=color[l-1])==nbcolors-1;
}

string colorSolution[l in locations]=colorNames[color[l]];

execute
{
  writeln(colorSolution," ==> ",totalworth);
}

这给了

["blue" "blue" "green" "green" "green" "green" "red" "red" "red" "red"] ==> 141

您也可以重写为 MIP：

range locations = 1..10;
int nbcolors=3;
int reward[l in locations]=l;
range colors=1..nbcolors;
string colorNames[colors]=["blue","green","red"];

dvar int color[locations] in colors;
dvar boolean colorb[locations][colors];

dexpr int totalworth=sum(l in locations) color[l]*reward[l];
maximize totalworth;
subject to
{
  forall(l in locations) color[l]==sum(c in colors) c*colorb[l][c];
  forall(l in locations) sum(c in colors) colorb[l][c]==1;
  
  // no color can be assigned to more than 4 balls
   //each color has to be assigned to at least 1 ball
  forall(c in colors) 1<=sum(l in locations) colorb[l][c]<=4;
  
  // consecutive locations
  sum(l in locations:l!=1) (color[l]!=color[l-1])==nbcolors-1;
}

string colorSolution[l in locations]=colorNames[color[l]];

execute
{
  writeln(colorSolution," ==> ",totalworth);
}

如何在 opl 整数程序中模拟连续位置？

How to model consecutive location in opl integer programs?

cplex

opl