Re: [ojAlgo-user] Knapsack problem with binary variables

[Anders P. <an...@op...>]

Don't think you've done anything wrong.

I've looked briefly at your test case and can already conclude that the IntegerSolver does not work properly for maximization problems (all the test cases are minimization problems). Immediately fixed one part of the problem, but it still doesn't work...

I'll definitely look into this some more, but I'm a little short on time currently. It may take some time.

You can turn on debugging with

GenericSolver.DEBUG = true;


Once you've called 

 model.maximise();

the problem is already solved, and the solution written back to your variables.

You may simply 

 System.out.println(model);

go "see" the results. This way you don't get access to the OptimisationState.


If you want to solve the problem with explicit access to the Solver and Result you'd do something like this:

 	model.setMaximisation(true);
        final OptimisationSolver solver = model.getDefaultSolver();
        final Result result = solver.solve();


/Anders



On 11 apr 2010, at 23.07, Luke Lindsay wrote:

> I am trying to solve a simple knapsack problem (maximise value given
> weight limit) with ojalgo.  See code below.  The code works as I would
> expected when var[i] are not set to integers.  I.e. the result is
> "OPTIMAL (0) { 1.0, 0.25, 3.0, 0.0, 0.0, 0.75 }" which I interpret as
> meaning "take one unit of item 0 and 0.25 of item 1".
> 
> I want to restrict var[i] to being 0 or 1.  But when I uncomment the
> line "vars[i].setInteger(true);", I get "OPTIMAL (1) { 0.0, 0.0, 0.0,
> 3.0, 0.0, 1.0, 1.0 }".  I was expecting "OPTIMAL (0) { 1.0, 0.0, 0..."
> i.e. "take one unit of item 0 and none of item 1".
> 
> Am I doing something wrong here?
> 
> 
> ...........................................................................................................................................
> package knapsack;
> 
> 
> import static org.ojalgo.constant.BigMath.*;
> 
> import java.math.BigDecimal;
> import org.ojalgo.optimisation.*;
> import org.ojalgo.optimisation.OptimisationSolver.Result;
> import org.ojalgo.optimisation.linear.LinearExpressionsModel;
> 
> public class Knapsack {
> 	
> 	static class Item{
> 		final BigDecimal value;
> 		final BigDecimal weight;
> 		public Item(int value, int weight) {			
> 			this.value = new BigDecimal(value);
> 			this.weight = new BigDecimal(weight);
> 		}		
> 	}
> 
> 	
> 	public static void main(String[] args) {
> 		
> 		BigDecimal maxWeight = new  BigDecimal(3);
> 		Item[] items = {new Item(20, 2), new Item(30, 4)};
> 				
> 		Variable[] vars = new Variable[items.length];
> 		for(int i =0; i < vars.length; i++){			
> 			vars[i] = new Variable(String.valueOf(i));
> 			//vars[i].setInteger(true);
> 			
> 			vars[i].upper(ONE).lower(ZERO);
> 			vars[i].setContributionWeight(items[i].value);			
> 		}
> 		
> 						
> 		LinearExpressionsModel model = new LinearExpressionsModel(vars);		
> 		Expression totalWeight = model.addEmptyLinearExpression("total weight");
> 		
> 		for(int i =0; i < items.length; i++){			
> 			totalWeight.setLinearFactor(i, items[i].weight);
> 		}		
> 		totalWeight.setUpperLimit(maxWeight);
> 		totalWeight.setLowerLimit(ZERO);
> 		
> 		
> 		System.out.println(totalWeight);
> 		
> 		model.maximise();
> 		OptimisationSolver solver  = model.getDefaultSolver();		
> 
> 		Result result = solver.solve();
> 		System.out.println(result);
> 		System.out.println(model.maximise());
> 		System.out.println(model.minimise());
> 	}
> }
> 
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> 
>