使用Gecode：多维多背包问题（MMKP） [英] using Gecode :Multiple Multidimensional Knapsack Problem (MMKP)
问题描述
嗨每一个人！
我很抱歉这么烦心但我真的不知道如何解决我的问题问题在于：
数学上，测试者进入正确节点的位置问题）可以通过合并两个引入的背包变体来建模：多维和多背包问题。获得的模型称为多维多背包问题（MMKP）。我们假设
执行环境由m个节点组成，我们有n个测试组件可以分配
给他们。我们试图找到一个最佳的测试解决方案，即不违反资源和连接限制，以及最大限度地提高其贴装利润。我们可以使用MMKP变体来表达这个问题
下面的文件中有更多详细信息： https://mail-attachment.googleusercontent.com/attachment/u/0/?ui=2&ik=e9e0b6ad61&view=att&th=13fd8fcb61aef21a& attid = 0.2& disp = inline& realattid = f_hj31zxla1& safe = 1& zw& saduie = AG9B_P-HIb12PHeml5gD0_j1sv2y& sadet = 1375672530928& sads = 9HbAXH6Ttd8AfIy4N0TgOkJdSwk& sadssc = 1 [ ^ ]
提供的m个节点的资源通过三个向量给出：C
包含提供的CPU，R提供可用的RAM和B
包含每个节点的电池电量（参见C，R，B表示）
https://mail-attachment.googleusercontent.com/attachment/u/0/?ui=2&ik=e9e0b6ad61&view=att&th=13fd8fcb61aef21a&attid=0.3&disp=inline&realattid=f_hj325dy92& ;安全= 1&安培; ZW&安培; saduie = AG9B_P-HIb12PHeml5gD0_j1sv2y&安培; sadet = 1375672532660&安培; SADS = 6OqxMT_45DbFbIk 7P7i5TX6SgUk [ ^ ]
此外，每个测试组件所需的资源都说明了
三个向量：Dcthat包含所需的CPU，Drthat包含所需的
RAM和Dbthat包含每个测试人员所需的电池。（参见Dc，Dr，Db表示）
https://mail-attachment.googleusercontent.com/attachment/u/0/?ui=2&ik=e9e0b6ad61&view=att&th=13fd8fcb61aef21a&attid=0.4&disp=inline&realattid=f_hj3285jr3& ; safe = 1& zw& saduie = AG9B_P-HIb12PHeml5gD0_j1sv2y& sadet = 1375672534176& sads = hF2e3VpBApkG8p9j9jKf4O_G78Y [ ^ ]
i有错误，我不知道该死的，我也会发布我的代码文件MMKP.cpp
hi every one !
i'm sorry to be so bothering but i really don't know how to solve my problem here:
Mathematically, the placement problem of testers into the right nodes) can be modeled by merging the two introduced knapsack variants: multidimensional and multiple knapsack problems. The obtained model is called Multiple Multidimensional Knapsack Problem (MMKP).. We assume that the
execution environment consists of m nodes and we have n test components that
may be assigned to them. We attempt to find an optimal solution of test com-
ponent placement not violating resource and connectivity constraints and also
maximizing their placement profit. We can formulate this problem using the MMKP variant
there is more details in a file below :https://mail-attachment.googleusercontent.com/attachment/u/0/?ui=2&ik=e9e0b6ad61&view=att&th=13fd8fcb61aef21a&attid=0.2&disp=inline&realattid=f_hj31zxla1&safe=1&zw&saduie=AG9B_P-HIb12PHeml5gD0_j1sv2y&sadet=1375672530928&sads=9HbAXH6Ttd8AfIy4N0TgOkJdSwk&sadssc=1[^]
The provided resources by the m nodes are given through three vectors: C
that contains the provided CPU, R that provides the available RAM and B that
contains the battery level of each node( see the C,R,B representations)
https://mail-attachment.googleusercontent.com/attachment/u/0/?ui=2&ik=e9e0b6ad61&view=att&th=13fd8fcb61aef21a&attid=0.3&disp=inline&realattid=f_hj325dy92&safe=1&zw&saduie=AG9B_P-HIb12PHeml5gD0_j1sv2y&sadet=1375672532660&sads=6OqxMT_45DbFbIk7P7i5TX6SgUk[^]
In addition, the required resources for each test component are illustrated over
three vectors: Dcthat carries the required CPU, Drthat contains the required
RAM and Dbthat contains the required Battery by each tester.( see the Dc,Dr,Db representations)
https://mail-attachment.googleusercontent.com/attachment/u/0/?ui=2&ik=e9e0b6ad61&view=att&th=13fd8fcb61aef21a&attid=0.4&disp=inline&realattid=f_hj3285jr3&safe=1&zw&saduie=AG9B_P-HIb12PHeml5gD0_j1sv2y&sadet=1375672534176&sads=hF2e3VpBApkG8p9j9jKf4O_G78Y[^]
i have got an error that i dont know the sorce , i will post also my code file MMKP.cpp
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/search.hh>
#include <gecode/minimodel.hh>
using namespace Gecode;
class MMKP : public Script{
protected:
static const int n=4 ;//number of testers
static const int m=5;// number of nodes
IntArgs R;
IntArgs C;
IntArgs B;
IntArgs Dr;
IntArgs Dc;
IntArgs Db;
IntArgs g;
IntVarArray a;
IntVarArray k;
IntVar l;
public :
enum {
find_Optimal_Solution, find_realizable_solution
};
MMKP (const Options& opt) : a(*this,n*m, 0,1){
R=IntArgs(4,10,15,20,40);
C=IntArgs(4,20,25,30,40);
B=IntArgs(4,20,30,35,40);
Dr=IntArgs(4,5,10,15,25);
Dc=IntArgs(4,15,20,35,37);
Db=IntArgs(4,10,15,20,35);
k=IntVarArray(*this,n*m ,0,100000);
Matrix <IntVarArray> results(k, n,m);
//creation variables
//IntVarArray a(*this,n*m,0,1); // Array of n*m boolean variables
Matrix <IntVarArray> X (a,n,m);// Matrix "view" of the array a
// objectiv variable
IntVar gain (*this, 1,1000000);
//creation of constraints
// ... over rows
for ( int j=0; j<n;j++)
{
linear(*this , X.row(j),IRT_EQ,1);
}
//... over columns
// first, get the columns, we will use an intermidiare matrix XDual
IntVarArray b(*this, m*n,0,1);
Matrix <IntVarArray> XDual (b, m, n);
for (int i=0; i<m;i++)
{
for ( int j =0; j<n ; j++)
{
XDual(i,j)=X(j,i);
}
}
for (int j = 0; j < m; j++) {
linear(*this, Dr,XDual.row(j),IRT_NQ, R[j]);
}
for (int j = 0; j < m; j++) {
linear (*this, Dc, XDual.row(j), IRT_NQ,C[j]);
}
for (int j = 0; j < m; j++) {
linear (*this, Db, XDual.row(j), IRT_NQ,B[j]);
}
switch (opt.model()) {
case find_Optimal_Solution:
g=IntArgs(4,20,30,40,50);
//Objective function
for (int i = 0; i < n; i++)
{
linear(*this, g,X.row(i), IRT_EQ, gain);
}
for ( int i=0; i<n;i++){
for ( int j =0; j<m;j++)
{
results(i,j)=X(i,j);
}
}
break;
case find_realizable_solution:
for ( int i=0; i<n;i++){
for ( int j =0; j<m;j++)
{
results(i,j)=X(i,j);
}
}
break;
// post branching
branch(*this, a, INT_VAR_SIZE_MAX(), INT_VAL_MAX());
}
}
// search support
MMKP(bool share, MMKP& s) : Script(share, s){
a.update(*this, share, s.a);
}
virtual Space* copy(bool share) {
return new MMKP(share,*this);
}
// print solution
void print(std::ostream& os) const {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
os << std::setw(4) << a[i * n + j];
os << std::endl;
}
}
};
// main function
int main(int argc, char* argv[]) {
Options opt("MMKP");
opt.model(MMKP::find_Optimal_Solution);
opt.model(MMKP::find_realizable_solution);
opt.parse(argc,argv);
Script::run<MMKP,DFS,Options>(opt);
return 0;
}
eroor是：
the eroor is :
exeption Int::linear :size of arguments mismatch
感谢您的帮助，非常抱歉再次打扰您
Thanks for evry help and very sorry to bother you again
推荐答案
清理后，这是你的'班级'：
Here is your 'class' after clean up:
#ifdef _AFX_ENABLE_INLINES
#define _AFX_INLINE AFX_INLINE
#if !defined(_AFX_CORE_IMPL) || !defined(_AFXDLL) || defined(_DEBUG)
#define _AFX_PUBLIC_INLINE AFX_INLINE
#else
#define _AFX_PUBLIC_INLINE
#endif
#endif
public enum Options{find_Optimal_Solution, find_realizable_solution};
typedef CArray<bool,bool> CTruthArray;
typedef CPtrArray<uint*,uint*>CResultArray;
struct NODE // Declare NODE structure
{
UINT* R; //TESTED RAM VALUES
UINT* C; //TESTED CPU VALUES
UINT* B; //TESTED BAT VALUES
}
struct TEST //Declare TEST structure
{
UINT* Dr; //Desired TEST Value for RAM
UINT* Dc; //Desired TEST Value for CPU
UINT* Db; //Desired TEST Value for BAT
}
struct MATRIX // row first, column second, as a 2D structure
{
UINT* row;
UINT* col;
}
class CMMKP : public Script, CObject
{
DECLARE_DYNACREATE(CMMKP)
public:
// Construction
CMMKP();
protected:
int n;//number of testers
int m;// number of nodes
UINT* Gain; // objective variable
UINT* R, C, B, Dr, Dc, Db, Gn, Lr;
NODE node1, node2, node3;
TEST test1, test2, test3;
MATRIX matATruths;
MATRIX matBTruths;
MATRIX matResults;
CTruthArray* Atruths;
CTruthArray* Btruths;
CUintArray* Kvalues;
void Linear(MMKP* pMMKP, UINT index, UINT mode, UINT type);
void GetSolution(Option& opt);
void ApplyConstrains();
void InitTruthArray();
MATRIX GetMatrix(UINT** results);
public:
~CMMKP();
void Serialize(CArchive&);
#ifdef _DEBUG
void Dump(CDumpContext&) const;
void AssertValid() const;
#endif
}
IntArgs，IntVarArray和IntVar不是C ++预定义类型。此外，IRT_NQ也是一个未在C ++中定义的#define，除非你在某个地方定义它，或者它是在Gecode包含中定义的。假设：
IRT_NQ ='整数返回类型不等于';
IntArgs ='整数值类型参数';
IntVar ='整数类型变量';
IntVarArray ='整数变量类型数组';
虽然我我不确定'线性'应该做什么，上面是一个'原型'，它声明它是类CMMKP的函数。那么下面你将在* .cpp匹配文件中或在类定义之外的同一文件中实现它。
然后在下面的类定义之外，你可以实现它：
IntArgs, IntVarArray, and IntVar are not C++ predefined types. Also IRT_NQ is also a #define that is not defined in C++, unless you do define it someplace, or it is defined within the Gecode includes. Presuming:
IRT_NQ is = 'Integer Return Type of Not Equal';
IntArgs is = 'Integer Value Type Arguments';
IntVar is = 'Integer Type Variable';
IntVarArray = 'Integer Variable Type Array';
While I am not sure about what 'linear' is supposed to do, the above is a 'prototype' that declares it as a function of class CMMKP. So then below you would implement this in a *.cpp matching file, or outside the class definition, in the same file.
Then here below out of the class definition, you can implement it:
CMMKP::CMMKP()
{
Atruths = new CTruthArray();//Array of Boolean variables (0 or 1) or (FALSE or TRUE)
Btruths = new CTruthArray();//Array of Boolean variables (0 or 1) or (FALSE or TRUE)
Kvalues = new CUintArray();// Array of unsigned integers, values from 0 to 2^16 - 1
}
CMMKP::~CMMKP()
{
if(Atruths != NULL)
delete Atruths;
if(Btruths != NULL)
delete Btruths;
if(Kvalues != NULL)
delete Kvalues ;
}
void CMMKP::GetSolution(Option& opt)
{
//You will need to rewrite the code below to match what I've done so far
switch (opt.model())
{
case find_Optimal_Solution:
Gn = {4,20,30,40,50};
//Objective function
for (int i = 0; i < n; i++)
{
linear(*this, Gn, X.row(i), IRT_EQ, Gain);
}
for ( int i=0; i<n;i++)>
{
for ( int j =0; j<m;j++)>
{
Results(i,j)=X(i,j);
}
}
break;
case find_realizable_solution:
for ( int i=0; i<n;i++)>
{
for ( int j =0; j<m;j++)>
{
Results(i,j)=X(i,j);
}
}
break;
}
void CMMKP::Linear(MMKP* pMMKP, UINT index, UINT mode, UINT type)
{
//This is where you put the code for the linear function.
}
void MMKP::InitArrays()
{
UINT num = n*m;
Atruths->SetSize(num,-1);
// IntVarArray a(*this,n*m,0,1); // Array of n*m boolean variables
matATruths = GetMatrix(Atruths);// Matrix "view" of the array a
Kvalues->SetSize(num,-1);
// k=IntVarArray(*this,n*m ,0,100000);
matResults = GetMatrix(Kvalues);// Matrix "view" of array k
Btruths->SetSize(num,-1);
// IntVarArray b(*this, m*n,0,1);
matBTruths = GetMatrix(Btruths);// Matrix "view" of array b
node1.R = {4,10,15,20,40};
node1.C = {4,20,25,30,40};
node1.B = {4,20,30,35,40};
test1.Dr = {4,5,10,15,25};
test1.Dc = {4,15,20,35,37};
test1.Db = {4,10,15,20,35};
}
//creation of constraints
// ... over rows
void CMMKP::ApplyConstrains()
{
for ( int j=0; j<n;j++)>
{
linear(*this , X.row(j),IRT_EQ,1);
}
//... over columns
// first, get the columns, we will use an intermidiare matrix XDual
for (int i=0; i<m;i++)>
{
for ( int j =0; j<n mode="hold" /> {
XDual(i,j)=X(j,i);
}
}
for (int j = 0; j < m; j++)
{
linear(*this, Dr,XDual.row(j),IRT_NQ, R[j]);
}
for (int j = 0; j < m; j++)
{
linear (*this, Dc, XDual.row(j), IRT_NQ,C[j]);
}
for (int j = 0; j < m; j++)
{
linear (*this, Db, XDual.row(j), IRT_NQ,B[j]);
}
}
/*
// post branching
// branch(*this, a, INT_VAR_SIZE_MAX(), INT_VAL_MAX());
// search support
BOOL CMMKP::Share(MMKP& s, BOOL share):Script(share, s)
{
a.update(*this, share, s.a);
}
virtual Space* CMMKP::Copy(BOOL share)
{
return new MMKP(share,*this);
}
// print solution there is a better one available
// ON_COMMAND(ID_FILE_PRINT, &CEditView::OnFilePrint) as an example.
// You will need a 'view' to your data for this to work.
void print(std::ostream& os) const {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
os << std::setw(4) << a[i * n + j];
os << std::endl;
}
}
};
*/
所以这应该有所帮助......
So that should help a little ...
这篇关于使用Gecode：多维多背包问题（MMKP）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
