# commons-issues mailing list archives

##### Site index · List index
Message view
Top
From "Luc Maisonobe (JIRA)" <j...@apache.org>
Subject [jira] Commented: (MATH-299) SimplexSolver returns no feasible solution
Date Tue, 22 Sep 2009 18:44:17 GMT
```
[ https://issues.apache.org/jira/browse/MATH-299?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12758353#action_12758353
]

Luc Maisonobe commented on MATH-299:
------------------------------------

I have tried to solve your problem with lp_solve to check whether it find a solution. Here
is what I have set up using lp_solve lp format:
{noformat:title=math-299.lp}
max: v;

-v + 1.7316145027890766 p1 +   1.3584341412980305 p2 + 0.9305633063383639 p3 + 1.687117394945513
p4 >= 0;
-v + 0.6617060079461883 p1 +   1.4862459822191323 p2 + 0.7692647272328988 p3 + 0.7329140944025636
p4 >= 0;
-v + 1.3255966888982322 p1 + 286.21607948837584   p2 + 1.135907611434458  p3 + 0.9803367440299271
p4 >= 0;
-v + 0.5428682596573682 p1 +   1.5745685116536952 p2 + 1.4834419186882808 p3 + 1.2884923232048968
p4 >= 0;

p1 + p2 + p3 + p4 = 1;

free p1, p2, p3, p4;

{noformat}

Running lp_solve on this file returns the following error message:
{noformat}
%  lp_solve < math-299.lp
This problem is unbounded
{noformat}

Could you check the constants and check if the problem really has a feasible finite solution
?

> SimplexSolver returns no feasible solution
> ------------------------------------------
>
>                 Key: MATH-299
>                 URL: https://issues.apache.org/jira/browse/MATH-299
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.0
>         Environment: Windows XP commons Math 2.0 jre 1.6.0.16
>            Reporter: David
>   Original Estimate: 8h
>  Remaining Estimate: 8h
>
> I am trying to optimize this:
> maximize: v
> v <= a1*p1 + a2*p2 + a3*p3 + a4*p4
> v <= b1*p1 + b2*p2 + b3*p3 + b4*p4
> v <= c1*p1 + c2*p2 + c3*p3 + c4*p4
> v <= d1*p1 + d2*p2 + d3*p3 + d4*p4
> p1 + p2 + p3 + p4 = 1
> where a1-d4 are constant specified below by the code (i didn't want to copy and paste
them up here. you can look below to see what they are in the objective function).
> 		LinearObjectiveFunction f = new LinearObjectiveFunction(
> 				new double[] { 1,
> 						0,
> 						0, 0, 0}, 0 );
> 		Collection<LinearConstraint>  constraints = new ArrayList<LinearConstraint>
();
> 		constraints.add(new LinearConstraint(new double[] { -1,
> 				1.7316145027890766,
> 				 1.3584341412980305,
> 				 0.9305633063383639,
> 				 1.687117394945513
> 		},
> 		Relationship.GEQ, 0));
> 		constraints.add(new LinearConstraint(new double[] { -1,
> 				0.6617060079461883,
> 				 1.4862459822191323,
> 				 0.7692647272328988,
> 				 0.7329140944025636
> 		},
> 		Relationship.GEQ, 0));
> 		constraints.add(new LinearConstraint(new double[] { -1,
> 				1.3255966888982322,
> 				286.21607948837584,
> 				1.135907611434458,
> 				0.9803367440299271
> 		},
> 		Relationship.GEQ, 0));
> 		constraints.add(new LinearConstraint(new double[] { -1,
> 				0.5428682596573682,
> 				1.5745685116536952,
> 				1.4834419186882808,
> 				1.2884923232048968
> 		},
> 		Relationship.GEQ, 0));
> 		constraints.add(new LinearConstraint(new double[] {0, 1, 1, 1, 1},
> 				Relationship.EQ, 1));
> 		RealPointValuePair solution = null;
> 		try {
>
> 			solution = new SimplexSolver().optimize(f, constraints,
> 					GoalType.MAXIMIZE, true);
> 		}
> 		catch (OptimizationException e) {
> 			e.printStackTrace();
> 		}
> I get this error back from the SimplexSolver.
> org.apache.commons.math.optimization.linear.NoFeasibleSolutionException: no feasible
solution
> 	at org.apache.commons.math.optimization.linear.SimplexSolver.solvePhase1(SimplexSolver.java:177)
> 	at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:187)
> 	at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106)
> 	at Runner.main(Runner.java:101)
> One interesting thing to note is that if you round all the numbers to the nearest 100's
place, it works. If you keep it with the floating point precision shown here, it doesn't.
>

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.

```
Mime
View raw message