Multiple Choice揹包拍賣

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}