Re: [ojAlgo-user] bug report: ILP problem
Mathematics, linear algebra and optimisation
Brought to you by:
apete
Menu
▾
▴
Re: [ojAlgo-user] bug report: ILP problem
|
From: Jeff S. <jef...@gm...> - 2013-04-11 15:33:26
|
So is it the case that for some setting of
model.options.problem
you'd expect the solver to find an optimal solution if one exists?
You demonstrated that when this value is set to 8, the solver fails.
Should the logic be "if fail then increase model.options.problem and run
again". I guess I dont understand the relationship between
model.options.problem
and successfully solving the problem.
On Thu, Apr 11, 2013 at 10:31 AM, Anders Peterson <an...@op...>wrote:
> I just check the state the way you do...
>
> model.options.problem = NumberContext.getGeneral(8);
> ==>>
> FAILED Infinity @ { 0.0, 0.0, 0.0, 0.0 }
>
> model.options.problem = NumberContext.getGeneral(9);
> ==>>
> OPTIMAL 4849.999999999305 @ { 4849.999999999305, 1244.9999999999998,
> 1269.0000000000002, 1307.0 }
>
> model.options.problem = NumberContext.getGeneral(12);
> ==>>
> FEASIBLE 4849.999999999305 @ { 4849.999999999305, 1244.9999999999998,
> 1269.0000000000002, 1307.0 }
>
>
> Changing from 9 to 12 causes some LP subproblem to fail. The MIP solver
> detects this, and therefore is not certain if the feasible solution it did
> find is optimal or not. Thus it marks it feasible rather than optimal.
>
>
> I don't consider the fact that you have to adjust some options to get the
> solver to function properly in some cases a bug. The way the LP fails with
> the "12" - it actually returns an infeasible solution - is a bug.
>
>
> /Anders
>
>
> On 11 apr 2013, at 15:47, Jeff Sherman <jef...@gm...> wrote:
>
> > Thanks for looking into this. I dont require anywhere near 16 digit
> accuracy on x1. In fact, I'm really only interested in the values of the
> integral variables. On the test case i sent you, I added the following:
> >
> > model.options.problem = NumberContext.getGeneral(9);
> >
> > and I get this output which is "correct".
> >
> > Obj val: 4849.999999999305
> > Optimal: true
> > All vars:
> > x1 = 4.85E+3
> > x2013 = 1245
> > x2014 = 1269
> > x2015 = 1307
> >
> > The "Optimal: true" output comes from:
> > res.getState().isOptimal()
> >
> > which doesn't seem to coincide with your results...how are you
> determining that you get a FEASIBLE, rather than OPTIMAL result?
> >
> >
> >
> > On Thu, Apr 11, 2013 at 5:57 AM, Anders Peterson <an...@op...>
> wrote:
> > I've run this test case, and I've created another using the model
> description from your first message.
> >
> > By setting
> >
> > tmpModel.options.problem = NumberContext.getGeneral(12);
> >
> > I can get correct (but maybe not accurate enough) solutions to both
> models:
> >
> > OPTIMAL 4199.999999999861 @ { 4199.999999999861, 1891.9999999999998,
> 1929.0 }
> > FEASIBLE 4849.999999999305 @ { 4849.999999999305, 1244.9999999999998,
> 1269.0000000000002, 1307.0 }
> >
> >
> > With the first model description you sent in you stated the correct
> solution to be:
> > x1 = 4200.000000000075
> > x2013 = 1892
> > x2014 = 1929
> >
> > Do you really require full 16 digit accuracy on x1?
> >
> >
> > With the second model something does go wrong with the linear solver in
> one of the integer solver's nodes (subproblems). That's why the result has
> state FEASIBLE rather than OPTIMAL. The fact that the returned feasible
> solution actually happens to be the correct/optimal solution is a
> coincidence. That problem with the linear solver is a bug - it somehow
> returns an infeasible solution. I'll look in to this further.
> >
> >
> > Using NumberContext.getGeneral(12); as the default value for
> tmpModel.options.problem breaks a number of other test cases...
> >
> >
> > /Anders
> >
> >
> > On 8 apr 2013, at 18:02, Jeff Sherman <jef...@gm...> wrote:
> >
> > > Anders,
> > > Please disregard the previous attachment and run this one. Also, on
> one run i got these results:
> > > Obj val: 5250.000000000088
> > > Optimal: true
> > > All vars:
> > > x1 = 5.25E+3
> > > x2013 = 1244
> > > x2014 = 1269
> > > x2015 = 1308
> > >
> > >
> > > On Mon, Apr 8, 2013 at 11:52 AM, Jeff Sherman <jef...@gm...>
> wrote:
> > > Andres,
> > > Thanks for your response. The attached code produces the following
> results:
> > > x1 = 0
> > > x2013 = 1245
> > > x2014 = 1269.9
> > > x2015 = 1306.1
> > >
> > > Note that x2014 and x2015 are set as integral variables.
> > >
> > > If in the calls to model.addExpression, i change the strings that are
> passed in, I can also obtain the following results:
> > > x1 = 2890.64039409
> > > x2013 = 1244
> > > x2014 = 1269.45812808
> > > x2015 = 1307.54187192
> > >
> > > I did some looking into the code and I noticed in the
> ExpressionsBasedModel class you have:
> > >
> > > private final HashMap<String, Expression> myExpressions = new
> HashMap<String, Expression>();
> > >
> > > and at points, you get a collection of myExpression.values(), the
> order of which is not guaranteed. I'm not sure if you care about this
> ordering but i thought id point it out in case.
> > >
> > > The correct results for the problem are:
> > > x1 = 4849.999999997941
> > > x2013 = 1245
> > > x2014 = 1269
> > > x2015 = 1307
> > >
> > > Please let me know if I can provide any additional information or
> clarification.
> > >
> > > Best,
> > > Jeff
> > >
> > >
> > >
> > > On Mon, Apr 8, 2013 at 5:22 AM, Anders Peterson <an...@op...>
> wrote:
> > > ...and please experiment with different values on the various
> model/solver options - in particular tmpYourModel.options..problem
> > >
> > > /Anders
> > >
> > >
> > > On 8 apr 2013, at 08:58, Anders Peterson <an...@op...> wrote:
> > >
> > > > It's better you send me source code that I can execute and use as a
> test case. /Anders
> > > >
> > > > On 8 apr 2013, at 01:25, Jeff Sherman <jef...@gm...>
> wrote:
> > > >
> > > >> When I execute the following program:
> > > >> Minimize
> > > >> 1*x1
> > > >> Subject To
> > > >> 1*x2013 >= 0
> > > >> 1*x2014 >= 0
> > > >> 1*x1 >= 0
> > > >> -5000.0*x2014 + 5100.0*x2013 + -1.0*x1 <= 0
> > > >> -5000.0*x2014 + 5100.0*x2013 + 1.0*x1 >= 0
> > > >> 5000*x2013 + 5000*x2014 = 19105000
> > > >> Bounds
> > > >> Variables
> > > >> x2014 integer
> > > >> x2013 integer
> > > >> x1 continuous
> > > >>
> > > >> I get these results which are suboptimal:
> > > >> x1 = 5899.999999996906
> > > >> x2013 = 1891
> > > >> x2014 = 1930
> > > >>
> > > >> Or these results (which seem to occur at random):
> > > >> x1 = Infinity
> > > >> x2013 = 0
> > > >> x2014 = 0
> > > >>
> > > >> Using another solver, I obtain:
> > > >> x1 = 4200.000000000075
> > > >> x2013 = 1892
> > > >> x2014 = 1929
> > > >>
> ------------------------------------------------------------------------------
> > > >> Minimize network downtime and maximize team effectiveness.
> > > >> Reduce network management and security costs.Learn how to hire
> > > >> the most talented Cisco Certified professionals. Visit the
> > > >> Employer Resources Portal
> > > >>
> http://www.cisco.com/web/learning/employer_resources/index.html_______________________________________________
> > > >> ojAlgo-user mailing list
> > > >> ojA...@li...
> > > >> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> > > >
> > > >
> > > >
> ------------------------------------------------------------------------------
> > > > Minimize network downtime and maximize team effectiveness.
> > > > Reduce network management and security costs.Learn how to hire
> > > > the most talented Cisco Certified professionals. Visit the
> > > > Employer Resources Portal
> > > > http://www.cisco.com/web/learning/employer_resources/index.html
> > > > _______________________________________________
> > > > ojAlgo-user mailing list
> > > > ojA...@li...
> > > > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> > > >
> > > >
> > >
> > >
> > >
> ------------------------------------------------------------------------------
> > > Minimize network downtime and maximize team effectiveness.
> > > Reduce network management and security costs.Learn how to hire
> > > the most talented Cisco Certified professionals. Visit the
> > > Employer Resources Portal
> > > http://www.cisco.com/web/learning/employer_resources/index.html
> > > _______________________________________________
> > > ojAlgo-user mailing list
> > > ojAlgo-user@lists..sourceforge.net
> > > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> > >
> > >
> > >
> <TestILP.java>------------------------------------------------------------------------------
> > > Minimize network downtime and maximize team effectiveness.
> > > Reduce network management and security costs.Learn how to hire
> > > the most talented Cisco Certified professionals. Visit the
> > > Employer Resources Portal
> > >
> http://www.cisco.com/web/learning/employer_resources/index.html_______________________________________________
> > > ojAlgo-user mailing list
> > > ojAlgo-user@lists..sourceforge.net
> > > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> >
> >
> >
> ------------------------------------------------------------------------------
> > Precog is a next-generation analytics platform capable of advanced
> > analytics on semi-structured data. The platform includes APIs for
> building
> > apps and a phenomenal toolset for data science. Developers can use
> > our toolset for easy data analysis & visualization. Get a free account!
> > http://www2.precog.com/precogplatform/slashdotnewsletter
> > _______________________________________________
> > ojAlgo-user mailing list
> > ojA...@li...
> > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
> >
> >
> ------------------------------------------------------------------------------
> > Precog is a next-generation analytics platform capable of advanced
> > analytics on semi-structured data. The platform includes APIs for
> building
> > apps and a phenomenal toolset for data science. Developers can use
> > our toolset for easy data analysis & visualization. Get a free account!
> >
> http://www2.precog.com/precogplatform/slashdotnewsletter_______________________________________________
> > ojAlgo-user mailing list
> > ojA...@li...
> > https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
|
