多选择背包拍卖

Question

我正在拼命寻找一个用Java编写的MCKP求解器。我需要它来解决这样的拍卖:3个投标人，每个投标人提出了一组相同的对象捆绑的报价。假设有10件物品可供出售，他们可以提供1，2，3，4等对象。

显然，每个投标人只能接受一个报价。

所以这显然是一个MCKP。

谢谢，Mat

Answer 1

这是一个用于Java的整数编程库。

http://javailp.sourceforge.net/

SolverFactory factory = new SolverFactoryLpSolve(); // use lp_solve
factory.setParameter(Solver.VERBOSE, 0); 
factory.setParameter(Solver.TIMEOUT, 100); // set timeout to 100 seconds

/**
* Constructing a Problem: 
* Maximize: 143x+60y 
* Subject to: 
* 120x+210y <= 15000 
* 110x+30y <= 4000 
* x+y <= 75
* 
* With x,y being integers
* 
*/
Problem problem = new Problem();

Linear linear = new Linear();
linear.add(143, "x");
linear.add(60, "y");

problem.setObjective(linear, OptType.MAX);

linear = new Linear();
linear.add(120, "x");
linear.add(210, "y");

problem.add(linear, "<=", 15000);

linear = new Linear();
linear.add(110, "x");
linear.add(30, "y");

problem.add(linear, "<=", 4000);

linear = new Linear();
linear.add(1, "x");
linear.add(1, "y");

problem.add(linear, "<=", 75);

problem.setVarType("x", Integer.class);
problem.setVarType("y", Integer.class);

Solver solver = factory.get(); // you should use this solver only once for one problem
Result result = solver.solve(problem);

System.out.println(result);

/**
* Extend the problem with x <= 16 and solve it again
*/
problem.setVarUpperBound("x", 16);

solver = factory.get();
result = solver.solve(problem);

System.out.println(result);
// Results in the following output:

// Objective: 6266.0 {y=52, x=22}
// Objective: 5828.0 {y=59, x=16}