복수 선택 배낭 경매

Question

저는 Java에서 MCKP 솔버를 절실히 찾고 있습니다. 이 경매를 해결하려면 다음과 같이해야합니다. 3 명의 입찰자, 모든 입찰자는 동일한 객체 묶음에 대해 일련의 제안을합니다. 판매 할 항목이 10 개라고 가정 할 때 1, 2, 3, 4 등의 개체를 제공 할 수 있습니다.

분명히 입찰자 당 한 건의 제안 만 수락 할 수 있습니다.

이렇게 분명히 MCKP입니다.

덕분에, 매트

Answer 1

이 자바에 대한 정수 프로그래밍 라이브러리입니다.

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}