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

[Luke L. <luk...@gm...>]

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;
		    }

	}

}