Thread: [ojAlgo-user] Knapsack problem with binary variables
Mathematics, linear algebra and optimisation
Brought to you by:
apete
Menu
▾
▴
ojalgo-user
|
From: Luke L. <luk...@gm...> - 2010-04-11 21:07:58
|
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());
}
}
|
|
From: Anders P. <an...@op...> - 2010-04-12 18:31:49
|
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® 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
>
>
|
|
From: Luke L. <luk...@gm...> - 2010-04-18 21:16:55
|
On 12 April 2010 20:31, Anders Peterson <an...@op...> wrote: > 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 > > Thank you for your reply. I have checked out the latest code from CVS. The test case in my previous email now works as expected. However, when I change the numbers, I still get some unexpected results. For instance, when I set my variable maxWeight = 1.1 or maxWeight = 5, the integer constraints don't hold. I can write a junit test if it would help. Best, Luke |
|
From: Anders P. <an...@op...> - 2010-04-19 06:45:43
|
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 On 18 apr 2010, at 23.16, Luke Lindsay wrote: > On 12 April 2010 20:31, Anders Peterson <an...@op...> wrote: >> 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 >> >> > Thank you for your reply. > > I have checked out the latest code from CVS. The test case in my > previous email now works as expected. However, when I change the > numbers, I still get some unexpected results. For instance, when I > set my variable maxWeight = 1.1 or maxWeight = 5, the integer > constraints don't hold. I can write a junit test if it would help. > > Best, > > Luke > > ------------------------------------------------------------------------------ > Download Intel® 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 > > |
|
From: Luke L. <luk...@gm...> - 2010-04-22 16:55:53
|
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;
}
}
}
|
|
From: Anders P. <an...@op...> - 2010-04-23 20:57:33
|
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
>
>
|
|
From: Luke L. <luk...@gm...> - 2010-04-25 19:01:16
|
On 23 April 2010 22:57, Anders Peterson <an...@op...> wrote:
> 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
>
Thanks Anders. The new code works correctly with all cases I've tried so far.
I was wondering if it would be possible to add a static factory method
for creating binary variables since it would make my code more
readable, e.g.
public static Variable binary(final String aName){
return new Variable(aName).lower(ZERO).upper(ONE).integer(true);
}
Best,
Luke
|
|
From: Anders P. <an...@op...> - 2010-04-25 19:26:38
|
ok, but I think I'll have to call it makeBinary(...) /Anders
On 25 apr 2010, at 21.01, Luke Lindsay wrote:
> On 23 April 2010 22:57, Anders Peterson <an...@op...> wrote:
>> 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
>>
> Thanks Anders. The new code works correctly with all cases I've tried so far.
>
> I was wondering if it would be possible to add a static factory method
> for creating binary variables since it would make my code more
> readable, e.g.
>
> public static Variable binary(final String aName){
> return new Variable(aName).lower(ZERO).upper(ONE).integer(true);
> }
>
>
> Best,
>
> Luke
>
> ------------------------------------------------------------------------------
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
>
|
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X