java - 多项选择背包拍卖

Question

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

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

所以这显然是一个 MCKP。

谢谢，垫

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}