Integer Programing in Maple 11

Hi all,

I'm trying to solve linear programs on Maple 11, but it is not giving me an answer. Have I made a mistake? The comand I used is:

with(Optimization):

LPSolve(40*a + 60*b, {40*a + 60*b <= 150}, assume=nonnegint, maximize)

and maple returns:

"Warning, problem appears to be unbounded".

 

But in Maple 10, this same comand works perfect. Does someone know why Maple 11 doesn't??

Mario

alec's picture

depthlimit

In Maple 12, it works with increased depthlimit. For example,

with(Optimization):
Maximize(40*a + 60*b, {40*a + 60*b <= 150}, 
    assume=nonnegint, depthlimit=10);

                        [140, [a = 2, b = 1]]

Alec

Thanks for answering, but I

Thanks for answering, but I tried in Maple 11 increasing depthlimit, but it still doesn't work. Could it be something from my computer? Because I use Maple 11 here, and Maple 10 in the university, and there the comand works, here it doesn't.

 

(I copied the comand on Maple, and I'm putting here what happened when I tried)

> with(Optimization);

Maximize(40*a+60*b, {40*a+60*b <= 150}, assume = nonnegint, depthlimit = 10);

Warning, problem appears to be unbounded
                             [0, [a = 0, b = 0]]
 

 

Mario

alec's picture

Upgrade

I guess you don't have any other choice as to upgrade to Maple 12.

_______________
Alec Mihailovs
Maplesoft Member

acer's picture

On Linux

Using either the 32 or 64 bit Linux versions of either Maple 11.02 or 10.06 it worked OK for me.

I also saw this,

> Digits:=17:
> with(Optimization):
> Maximize(40*a+60*b, {40*a+60*b <= 150},
>          assume = nonnegint, depthlimit = 10);
maple: fatal error, lost connection to kernel

The same thing happened with Digits set to 14 and UseHardwareFloats set to false.

acer

That is not a perfect

That is not a perfect solution, but maybe it's the only one. But a asked a friend to do it in Maple 11, he runs Maple on Ubuntu 8.04. And there it worked.

So it likes that the problem is with my computer configuration, I don't know. Is that possible?

 

Mario

acer's picture

so...

What is your platform (operating system), and exact Maple version (11.00, 11.01, 11.02)?

acer

My computer info.

Windows XP SP2, Maple 11.02.

And all other specifications are above the recomended for Maple 11.

Mario

 

Integer program

I am unable to reproduce the error you are getting. Instead, I get the expected solution by increasing depthlimit.

However, I wouldn't assume right away that the problem is with your computer, although using a different system can have an effect. Most of the algorithms in the Optimization package are sensitive to floating-point errors and to the choice of initial point. That is just a fact of life with many numerical local optimization solvers. Occasionally, you'll get an unexpected error with these routines but more frequently, you might get a local minimum different from what you expect.

For this particular example, try using a different initial point and see if that helps to avoid the error. Indeed, with routines in the Optimization package, one should always provide an initial point if at all possible. You can also set infolevel[Optimization] to a value of 3 or higher to get some information about what is happening.

Paulina Chin
Maplesoft

 

Infolevel

I tried again. With different initial points. And Maple stils don't give me the answer.

Using infolevel I got this:

> with(Optimization);
> infolevel[Optimization] := 3;
                                      3
Maximize(40*a+60*b, {40*a+60*b <= 150}, assume = nonnegint, initialpoint = [a = 1, b = 1], depthlimit = 10);

LPSolve: calling ILP solver
SolveInteger: number of problem variables 2
SolveInteger: number of general linear constraints 1
PrintSettings: feasibility tolerance set to 0.1053671213e-7
PrintSettings: integer tolerance set to 0.10e-4
PrintSettings: infinite bound set to 0.10e21
PrintSettings: iteration limit set to 50
PrintSettings: depth limit set to 10
PrintSettings: node limit set to 0
Warning, problem appears to be unbounded
                            [100, [a = 1, b = 1]]
 

I modified all parameters, and nothing helps. Any other ideia?

Really Thanks!

Mario

alec's picture

Bounds

You could try adding bounds instead of initial points. For example,

with(Optimization):
Maximize(40*a+60*b, {40*a+60*b <= 150}, a=0..3, b=0..2, 
    assume = nonnegint, depthlimit=10);

                        [140, [a = 2, b = 1]]

Alec

Error with higher Digits setting

Acer, I can reproduce that error on Linux. I'll record this bug in our database and we'll investigate. Thanks for catching this.

Paulina

alec's picture

Some comments

This problem has only 8 feasible points: (0,0), (0,1), (0,2), (1,0), (1,1), (2,0), (2,1), (3,0) - in such cases the simplest solution would be to evaluate the function in all the feasible points, and then choose the maximum. It is strange that such a simple thing was not implemented.

Alec

Cannot reproduce

Mario, I tried running your problem on several platforms and with several versions of Maple and I can't reproduce the result you're seeing. That doesn't mean I don't believe you are indeed seeing that result. It just means that I can't investigate further to find the cause and suggest a workaround. At this point, I'd suggest you alter the problem, perhaps as Alec suggests by putting in explicit bounds, and trying some other initial points. If nothing works, then you can submit this issue to Maplesoft Support, giving full details of the system you're using. They might be able to reproduce the problem on the machines they use.

Paulina

Nothing yet

I tried every thing you said, but it still doesn't work. So I will submit it to Maplesoft Support.

Thanks for all your help.

Mario

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}