Solving Linear Programming Problems Over the Field of Rational Numbers
dbulutog
I understand that AMPL used with a solver solves Linear Programming problems
approximately but not exactly
even if all the elements of the input data for the LP problem are in the
field of rationals.
For one thing, in AMPL rational numbers are represented with their decimal
expansion but not as quotients. Hence precision is always a problem. I was
wondering if there is a software package that can solve LP problems exactly
if each input data element is a rational number. Such a software package
inevitably needs to store every rational number as a quotient and the
solution vector as well as the optimal value need to be computed as
quotients. I understand that numerators and denominators of these quotients
can be huge but I am curious if there is a research effort in this
direction. AMPL can be extended to do such a task.
Dursun Bulutoglu
--
View this message in context: http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-Field-of-Rational-Numbers-tf3167622.html#a8787137
Sent from the AMPL mailing list archive at Nabble.com.
Robert Fourer
See http://neos.mcs.anl.gov/neos/solvers/lp:qsopt_ex/LP.html. Unfortunately
this implementation does not seem to have an AMPL driver. You can use it by
having AMPL write out an MPS-format file:
ampl: model diet2.mod;
ampl: data diet2.dat;
ampl: option relax_integrality 1;
ampl: write mdiet;
ampl:
Then enter the resulting file diet.mps in the form on the above page of the
NEOS Solver, and wait for the output:
mpq_ILLlp_add_logicals ...
Time for SOLVER_READ: 0.00 seconds.
starting mpq_ILLsimplex on scaled_lp...
Problem has 17 rows and 80 cols
starting primal phase I
(0): primal infeas = 5179.8211382 637118/123
starting primal phase II
completed mpq_ILLsimplex
scaled_lp: time = 0.120, pI = 14, pII = 22, dI = 0, dII = 0, opt = 7.798354
starting mpq_ILLsimplex on diet...
Problem has 17 rows and 80 cols
completed mpq_ILLsimplex
diet: time = 0.010, pI = 0, pII = 0, dI = 0, dII = 0, opt = 7.798354
LP Value: 7.798354, status 1
Time for SOLVER: 0.14 seconds.
Solution Values
C0001 = 2
C0002 = 23765960070/22282172849
C0023 = 15198945227/22282172849
C0024 = 15198945227/22282172849
C0030 = 15198945227/22282172849
C0040 = 28898532528/22282172849
C0044 = 7771548482/22282172849
C0048 = 32536163082/22282172849
C0051 = 9060787642/22282172849
C0063 = 25249567823/22282172849
It's up to you to connect these values to the variables in the AMPL model,
though. This solver also accepts "LP format" which can be derived from the
output of the AMPL "expand" command, but only by means of some nontrivial
transformations.
Bob Fourer
4...@ampl.com
dbulutog
This is great!
I have another related question. The parameter values in my problems may be
integers as large as than 10^10. When read such integers into AMPL AMPL
truncates them. For example 1036474564667 can be read as 1036474560000 or
even 1.0364*10^12. Is there a way read such large integers as exactly what
they are from a .dat file. I will use AMPL to create the necessary MPS files
for qsopt to solve. I will be solving integer programming problems but would
like the Branch and Bound algorithm to use the exact solutions to the LP
relaxations on the nodes of the Branch and Bound tree.
Thanks a lot for pointing out this solver.
Dursun.
--
View this message in context: http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-Field-of-Rational-Numbers-tf3167622.html#a8795790
Hans Mittelmann
I have installed QSOPT_EX. For integer input you can use both the MPS
and the LP format provided. But the LP format also allows input of
rational data. AMPL input in the form described can easily be added
but it does not allow rational input and also truncates data when
converting to MPS. Is the LP format not suitable for your purposes?
Hans Mittelmann
On Feb 4, 11:43 am, dbulutog <dursun.buluto...@afit.edu> wrote:
> This is great!
> I have another related question. The parameter values in my problems may be
> integers as large as than 10^10. When read such integers into AMPL AMPL
> truncates them. For example 1036474564667 can be read as 1036474560000 or
> even 1.0364*10^12. Is there a way read such large integers as exactly what
> they are from a .dat file. I will use AMPL to create the necessary MPS files
> for qsopt to solve. I will be solving integer programming problems but would
> like the Branch and Bound algorithm to use the exact solutions to the LP
> relaxations on the nodes of the Branch and Bound tree.
>
> Thanks a lot for pointing out this solver.
>
> Dursun.
>
>
>
> Robert Fourer-2 wrote:
>
> > Seehttp://neos.mcs.anl.gov/neos/solvers/lp:qsopt_ex/LP.html.
> View this message in context:http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-F...
Hans Mittelmann
MILPs exactly. The B&B procedure is time consuming and I have so far
not done it
Hans Mittelmann
On Feb 4, 11:43 am, dbulutog <dursun.buluto...@afit.edu> wrote:
> This is great!
> I have another related question. The parameter values in my problems may be
> integers as large as than 10^10. When read such integers into AMPL AMPL
> truncates them. For example 1036474564667 can be read as 1036474560000 or
> even 1.0364*10^12. Is there a way read such large integers as exactly what
> they are from a .dat file. I will use AMPL to create the necessary MPS files
> for qsopt to solve. I will be solving integer programming problems but would
> like the Branch and Bound algorithm to use the exact solutions to the LP
> relaxations on the nodes of the Branch and Bound tree.
>
> Thanks a lot for pointing out this solver.
>
> Dursun.
>
>
>
> Robert Fourer-2 wrote:
>
> > Seehttp://neos.mcs.anl.gov/neos/solvers/lp:qsopt_ex/LP.html.
> View this message in context:http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-F...
dbulutog
Dear Hans,
Thank you for your response. AMPL has nice features for modelling. That is
why I wanted to use it to create my problem files in the MPS format.
I can write my own code in GAP (Groups Algorithms and Programming) to
generate the problem files in the LP format unless there is another easier
way of creating these files. It would be alot easier to generate the MPS
files using AMPL than using GAP to generate the LP files.
Dursun Bulutoglu.
--
View this message in context: http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-Field-of-Rational-Numbers-tf3167622.html#a8800196
Hans Mittelmann
I do not quite understand what it is you want. Do you have rational
data as your first message suggests or do you have integer data? You
never said that. If you have integer data you can use QSOPT_EXE with
MPS input and I can add the simple AMPL interface to that. If you have
rational data you have to use the LP format.
Hans
> View this message in context:http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-F...
Hans Mittelmann
But, if you have rational data you better write a small program in
Fortran, C, Matlab etc to generate the LP file. I do not know GAP and
if it would be more or less effort.
On Feb 4, 7:34 pm, dbulutog <dursun.buluto...@afit.edu> wrote:
> View this message in context:http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-F...
Robert Fourer
Regarding the handling of large integers by AMPL, you state: "The parameter
values in my problems may be integers as large as than 10^10. When read such
integers into AMPL, AMPL truncates them. For example 1036474564667 can be read
as 1036474560000 or even 1.0364*10^12." If you use "display" on a large
integer, it may appear to be truncated:
ampl: param a = 1036474564667;
ampl: display a;
a = 1.03647e+12
But this is because the default display precision is 6 significant digits. If
you change the option display_precision to zero, it is specially interpreted to
mean that display should show as many significant digits as possible:
ampl: option display_precision 0;
ampl: display a;
a = 1036474564667
So in this case there is not actually any truncation of the value, only of the
way it is chosen to be displayed. (Note also that "print a;" gives maximum
possible precision by default.)
The precision for numbers written by the "expand" statement is similarly given
by expand_precision, whose default is 6 like that of display_precision.
Unfortunately the MPS form standard allows for only 12 characters to represent
each number, so parameter a above cannot be represented any more precisely than
1.036475E+12. There is an unofficial free-format version of MPS form that
allows longer numbers, but not all solvers recognize it.
Bob Fourer
4...@ampl.com
> Programming-Problems--Over-the-Field-of-Rational-Numbers-
> tf3167622.html#a8800196
dbulutog
Professor Fourer and the AMPL forum,
I was wondering how easy it is to use AMPL to generate LP files using the
expand command.
If those non-trivial transformations that you suggested are easy to
implement I will take this course otherwise I may have to program in GAP to
produce my LP files. If there are any references in this regard I would
appreciate them.
Thanks alot again for your responses. They have been very helpful.
Dursun.
Dursun,
ampl: option display_precision 0;
Bob Fourer
4...@ampl.com
--
View this message in context: http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-Field-of-Rational-Numbers-tf3167622.html#a8814361
dbulutog
Professor Mittelmann,
I do have integer data however these integers can be as large as 10^15. I do
not know whether AMPL writes such huge integers into the .MPS file without
truncating them.
Dursun.
--
View this message in context: http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-Field-of-Rational-Numbers-tf3167622.html#a8819014
Alkire, Brien
edition of AMPL for my classes.
I also work as a researcher at RAND. I formulated a problem as a QP
with some binary variables. It is my understanding that CPLEX can solve
these. I want to try a small sample before investing in a full license
for my research project.
I tried using my student edition and I get an error message about a
licensing problem (CPLEX error # 0).
Is it the case that the student edition of CPLEX does not support QP's
with binary variables?
Is there some way that I can test a small problem (maybe using the web
interface)?
If I can show that the small problem can be solved, then I can convince
my project leader to buy me a license so I can use it for my research :)
Thanks in advance,
Brien
--------------------
This email message is for the sole use of the intended recipient(s) and
may contain privileged information. Any unauthorized review, use,
disclosure or distribution is prohibited. If you are not the intended
recipient, please contact the sender by reply email and destroy all copies
of the original message.
Steven Harrod
you the results log file.
I suspect the student edition is an older, much older, version of cplex.
Steven Harrod
--
Steven Harrod
Lexington, KY
859 225 1572
Alkire, Brien
Actually, I apologize for sending that email prematurely. Indeed it
does appear to solve QP's with binary variables. I must have had an
error in my objective function!
Thanks for offering to solve it for me.
Hopefully I can interest my project leader enough to purchase a full
version. That will depend on the size of the problem, and I am
uncertain of that yet. If it is too large (too many binary variables) I
may attempt to use GA.
-Brien
-----Original Message-----
From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of
Steven Harrod
Sent: Monday, February 05, 2007 6:24 PM
To: am...@googlegroups.com
Robert Fourer
A few experiments suggest that the student-version CPLEX solves binary QPs
fine when the (minimized) objective is positive semi-definite, but gives the
message
CPLEX 10.1.0: unrecoverable failure or licensing problem: CPLEX error # 0.
when the objective is not positive semi-definite. If that's the case then
the fault is in the error message, which should be more specific. The
methods in CPLEX are not capable of optimizing over indefinite quadratic
terms.
Bob Fourer
4...@ampl.com
Alkire, Brien
corrected it now, and solved my small example. The (corrected)
objective function is convex quadratic.
Hans Mittelmann
two more things in this original discussion. Unfortunately, someone
interfered with this discussion instead of starting a new one.
(1) I gave QSOPT_EX yesterday the AMPL interface (via generation of
MPS file)
(2) As I have said before but you apparently did net catch: The LP
format can accept integer or rational numbers with many(!) digits
while MPS does not allow that.
Hans
> View this message in context:http://www.nabble.com/Solving-Linear-Programming-Problems--Over-the-F...
Robert Fourer
It's easy enough to use the expand command; it's just "expand;" to get the
expansion before AMPL's presolve, or "solexpand;" to get the expansion of what
would be sent to a solver after AMPL's presolve. The output can be redirected
to a file by use of something like "expand >filename;" or "expand >filename;".
If you try an example you'll see pretty quickly how the output differs from LP
form and what would be involved in the transformation.
Bulutoglu Dursun A Civ AFIT/ENC
I found many different definitions of the lp format on the internet. I
am not sure whether they are all viable definitions for the Qsopt solver
application I am interested. For example can I have a variable named
x[1,3]? Can I keep the "3*x[1,3]" as it is without getting rid of the
"*"? Can I have a constraint name "s.t equalities[1,3]:"? Am I allowed
to have ";" at the end of each line? These are not clearly explained
anywhere...
Dursun.
-----Original Message-----
From: Robert Fourer [mailto:4...@ampl.com]
Hans Mittelmann
I would appreciate if you would look at bit more carefully at the
QSOPT-EX sover webpage. As you know I am the administrator of that
solver and I typically try to make my solver webpages complete. So,
when you go this page, you see that the word "LP" is, in fact, a link
to the description of the LP format.
I HOPE THAT HELPS.
Hans Mittelmann
On Feb 7, 6:09 pm, "Bulutoglu Dursun A Civ AFIT/ENC"
> ...
>
> read more ยป
medvall
- at least it works fine for me.
I think this was introduced for 9.1(10.0?) or something in that range.
They can fix the model when only binary variables to make it run.
Possibly you have variables that are non-binary.
Best wishes, Marcus
Tomlab Optimization Inc.
http://tomopt.com/ampl/
> > of the original message.- Hide quoted text -
>
> - Show quoted text -