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

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

All your test cases (1 + 5) work now.

Fixed a bug with the IntegerSolver related to determining if a branch-solution is an integer solution or not.
Fixed a bug with the ExpressionsBasedModel (that only affected integer models) that resulted in all models being treated as minimization models.
Changed/improved the LinearSolver. It generally seems better now, but there's actually a couple of unit tests that used to work that now fail. Not finished with this yet.

/Anders


On 22 apr 2010, at 18.55, Luke Lindsay wrote:

> On 19 April 2010 08:45, Anders Peterson <an...@op...> wrote:
>> Not finished fixing yet...
>> 
>> Yes, please write a junit test. Most likely the problem is actually with the LP (sub) solver, and not the MIP (master) solver. My guess is that there is one particular MIP-branch that is incorrectly reported as solved by the LP solver. (That was the problem last time.) Write a junit test for that particular LP problem as well.
>> 
>> If you also check out theTestProj module from CVS you'll find your problem/case in
>> 
>> org.ojalgo.optimisation.integer.ReportedProblems
>> 
>> and
>> 
>> org.ojalgo.optimisation.linear.ReportedProblems
>> 
>> 
>> Don't forget to set GenericSolver.DEBUG=true when you debug.
>> 
>> /Anders
>> 
> Here is a junit test.  Currently, tests 1 and 4 fail and the others
> pass.  I don't understand what is causing the problem, but in the test
> cases that fail, the binary variables are being set to values other
> than 0 or 1.
> 
> Luke
> 
> 
> ..........................................................................................................
> package org.ojalgo.optimisation.integer;
> 
> import static org.ojalgo.constant.BigMath.ONE;
> import static org.ojalgo.constant.BigMath.ZERO;
> 
> import java.math.BigDecimal;
> import java.util.ArrayList;
> 
> import junit.framework.TestCase;
> 
> import org.ojalgo.optimisation.Expression;
> import org.ojalgo.optimisation.Variable;
> import org.ojalgo.optimisation.linear.LinearExpressionsModel;
> 
> public class KnapsackTest extends TestCase {
> 	
> 	LinearExpressionsModel model;
> 	
> 	void assertOne(Variable v){
> 		assertEquals(new BigDecimal("1.0"), v.getValue());
> 	}
> 	
> 	void assertZero(Variable v){
> 		assertEquals(new BigDecimal("0.0"), v.getValue());
> 	}
> 	
> 	public void testVaryingMaxWeight0(){
> 		model = new KnapsackProblemBuilder(3d).addItem(20, 2).addItem(30, 4).build();
> 		model.maximise();
> 		//Expected: just first item
> 		assertOne( model.getVariables()[0]);
> 		assertZero( model.getVariables()[1]);
> 						
> 	}
> 	
> 	public void testVaryingMaxWeight1(){
> 		model = new KnapsackProblemBuilder(1.1d).addItem(20, 2).addItem(30,
> 4).build();
> 		model.maximise();
> 		//Expected: nothing
> 		assertZero( model.getVariables()[0]);
> 		assertZero( model.getVariables()[1]);
> 	}
> 	
> 	public void testVaryingMaxWeight2(){
> 		model = new KnapsackProblemBuilder(0d).addItem(20, 2).addItem(30, 4).build();
> 		model.maximise();
> 		//Expected: nothing
> 		assertZero( model.getVariables()[0]);
> 		assertZero( model.getVariables()[1]);
> 	}
> 	
> 	public void testVaryingMaxWeight3(){
> 		model = new KnapsackProblemBuilder(10d).addItem(20, 2).addItem(30, 4).build();
> 		model.maximise();
> 		//Expected: both
> 		assertOne( model.getVariables()[0]);
> 		assertOne( model.getVariables()[1]);
> 	}
> 	
> 	public void testVaryingMaxWeight4(){
> 		model = new KnapsackProblemBuilder(5d).addItem(20, 2).addItem(30, 4).build();
> 		model.maximise();
> 		//Expected: just second item
> 		assertOne( model.getVariables()[1]);
> 		assertZero( model.getVariables()[0]);
> 		
> 	}
> 	
> 	static class  KnapsackProblemBuilder {
> 		
> 		final BigDecimal maxWeight;
> 		
> 		final ArrayList<KnapsackItem> items = new ArrayList<KnapsackItem>();
> 		
> 		 KnapsackProblemBuilder(double maxWeight){
> 			this.maxWeight = new BigDecimal(maxWeight);
> 		}
> 		
> 		KnapsackProblemBuilder addItem(int weight, int value){
> 			items.add(new KnapsackItem(weight, value));
> 			return this;
> 		}
> 		
> 		LinearExpressionsModel build() {	
> 
> 		        final Variable[] tmpVariables = new Variable[items.size()];
> 		        for (int i = 0; i < tmpVariables.length; i++) {
> 		            tmpVariables[i] = new Variable("Var" + String.valueOf(i));
> 		            tmpVariables[i].lower(ZERO).upper(ONE).weight(items.get(i).value).integer(true);
> 		        }
> 
> 		        final LinearExpressionsModel retVal = new
> LinearExpressionsModel(tmpVariables);
> 		        final Expression tmpTotalWeightExpr =
> retVal.addEmptyLinearExpression("Total Weight");
> 		        for (int i = 0; i < items.size(); i++) {
> 		            tmpTotalWeightExpr.setLinearFactor(i, items.get(i).weight);
> 		        }
> 		        tmpTotalWeightExpr.lower(ZERO).upper(maxWeight);
> 
> 		        retVal.setMaximisation(true);
> 
> 		        return retVal;
> 		    }
> 
> 	}
> 
> }
> 
> ------------------------------------------------------------------------------
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> 
>