GAMS FAQ for keyword: SOLVER
CPLEX: Fixed LP of a MIP is infeasible
> I solve a mixed-linear integer problem with CPLEX7.5 and I get
> the following message:
> Final LP did not return an optimal solution.
> Proven optimal solution.
> What is the difference between this solution and the one obtained
> when the message is just:
> Proven optimal solution.
> Is it related with the quality of the solution obtained?.
You can follow what happened in the log. After finding optimal values for
the discrete variables with the Cplex branch and cut algorithm, GAMS wants
us to return a complete solution -- including dual values. So, we fix the
discrete variables at the values returned by the branch and cut algorithm
and solve a final LP. That LP turns out to be infeasible. Having this
happens tells you that the model has numerical problems. We return the
solution so that it can be analyzed. What I'm sure you'll see is that there
are small infeasibilities but otherwise the solution will look pretty good.
You can often make this go away by turning on a more aggressive scaling
(preferred, cplex option: scaind 1) or by specifying a smaller
integrality tolerance (cplex option epint). You could also work on
figuring out why the model is numerically difficult.
Cplex actually performs the same for 7.0 and 7.5 but we changed the link to
not treat this as a failure.
Not enough memory to solve my problem with OSL.
> GAMS/OSL complains that there is not enough memory to solve
> my problem. What do I do ?
The solver reports its memory estimate and availability in both the
listing file and the log as follows:
Work space requested by solver --- 23.45 MB
Work space allocated --- 0.00 MB
Maximum work space available --- 16.31 MB
This indicates that GAMS/OSL estimated that 23.45 MB would be
required to solve the problem, and since only 16.31 MB were
available on the machine, no memory was estimated, and OSL did not
attempt to solve the problem.
Since 23.45 MB is a conservative estimate, the user could force OSL
to try and solve the problem with the memory available. This is done
by adding the following line,
mymodel.workspace = 16 ;
where mymodel is the name of the model as specified by the model
statement. This should appear between the model and solve
statements.
If this causes OSL to crash, then the only option is to run the model
on a machine with more memory.
Why do various MIP solvers give differing answers to my problem ?
> The MIP solver xxx gives an answer different to MIP solver yyy for
> my problem. Why does this happen ?
The default value of the relative optimality tolerance is 0.1. This
means that, unless otherwise specified, the solver will stop when it
finds a feasible integer solution within 10% of the global optimum.
Various solvers can find different solutions that fall in this 10% gap.
The user can override this and force the solver to find the global
optimum by setting the optcr option to 0.0 using the statement,
option optcr = 0.0 ;
before the solve statement.
What do I do if OSL crashes without warning ?
Q: OSL runs my MIP problem for a while. But once the branch and
bound search has gone on for a while, OSL suddenly crashes and
GAMS cannot recover the solution. What can I do ?
A: The most likely cause of the OSL crash is due to its memory
estimate being wrong. In such a case, you will probably find lines in
the log similar to the following:
**** Severe problem in OSL. Check the listing file.
Terminating...
The listing file contains a message similar to,
EKK3010W There is not enough storage to extend buffers for EKKMSLV
EKK7052S There is an I/O error on direct access file 82 at record 846905452
**** Severe problem in OSL. Check the listing file.
Terminating...
The reason for this error is as follows: Fortran based codes like OSL
cannot make multiple memory calls to the system. Instead, they
initially make a very conservative estimate of the amount of memory
needed to solve the problem based on its size. Sometimes, especially
for MIP models where the size of the branch and bound tree becomes
very large, even this conservative estimate is not enough, and OSL
runs out of memory while solving the problem and crashes. OSL
reports its memory estimate both in the listing file and the log. It
looks as follows:
Work space allocated: 0.80 MB
This means that OSL estimated that 0.8 MB of memory was needed
to solve this problem. The user can force OSL to override this
memory estimate with the user's estimate. In the example above, if
0.80 MB made OSL crash, you can force OSL to use more memory
(say 3 MB) by using the following command:
mymodel.workspace = 3 ;
where mymodel is the name of the model as specified by the model
statement. The .workspace assignment should come between the
model and solve statements.
How do I interrupt a solver?
> I want to interrupt my solver and have it return the current status,
> in much the same way as would be done if an iteration or resource
> limit were exceeded. How can I do this?
The Unix and PC systems now support a user interrupt that can be
triggered by the user to stop a solver job at the next convenient point.
Typically, solvers will check for a user interrupt in the same places
where the resource limit is checked. A user might wish to trigger an
interrupt in order to stop a MIP job that has found a good integer
feasible point but does not yet satisfy the convergence tolerances, or
to return an intermediate point for an LP or NLP. The solver will
return the current point and the appropriate model status, with a
solution status of 8 (USER INTERRUPT), and the GAMS run will
continue.
A user interrupt is triggered by sending an interrupt (SIGINT) to the
solver. This can be done in a number of ways, but the easiest is to
enter Control-C from the keyboard. This will send a signal to the
solver that will be caught and eventually cause the solver to
terminate after writing out its current status.
Users accustomed to using Control-C (SIGINT) to terminate the
entire GAMS run should now use the SIGBREAK signal on the PC
(hit Control-Break) and SIGQUIT on a Unix machine (typically
Control-\). Users should be aware that the SIGINT, SIGBREAK, and
SIGQUIT signals can be caught by other processes, so if you are
running GAMS inside a shell that does this, you may have to send
these signals in another way. For example, Emacs users will not be
able to use Control-C to send SIGINT when running GAMS jobs in
an Emacs subshell. Also, these signals can be bound to different
keys on a Unix machine via the stty command: use the stty
all command to find the current settings.
Not all solvers can be interrupted by the user. Currently, those that
can be interrupted include BDMLP, CONOPT, CPLEX, and MINOS,
with more soon to follow.
What is optca/optcr?
All algorithms in GAMS for solving MIPs are LP based branch-and-bound
algorithms. While the algorithm runs it maintains two very important
numbers: "best estimate" and "best integer". The "best integer" is the
best solution that satisfies all integer requirements found so
far. The "best estimate" provides a bound for the optimal integer
solution.
For example, you have a maximization problem and the algorithms found
an integer solution with objective value 10 (hence "best integer =
10). Moreover the algorithm communicates through the "best estimate",
which is e.g. 15, that the upper bound for the optimal solution of
this problem is 15.
Having those two numbers we can calculate the "quality" of the best
integer. The quality of a solution can be measured as the distance
from the optimal solution. Unfortunately, we don't have the optimal
solution, but we have a bound for the optimal solution ("best
estimate"). Hence an upper bound for the distance between best integer
and optimal solution is "best estimate" - "best integer". This value
is called the absolute gap (GAMS notation OPTCA). By providing the
option OPTCA in a GAMS program you allow the solver to stop if the
absolute gap dropps below OPTCA. In our small example: The absolute
gap is 5 = (15 - 10). If OPTCA>=5 we would stop. The GAMS default for
OPTCA is 0.
The absolute gap depends on the magnitude of the numbers "best
estimate" and "best integer". For example, if "best integer" = 10000
and "best estimate" = 15000 the absolute gap is 5000. In relative
terms the quality of that solution is similar that the solution pair
10/15. For that reason there is the "relative gap" (in GAMS notation
OPTCR) which is ("best estimate"-"best integer)/"best estimate". Hence
the "relative gap" for both example would be 0.33. If the relative gap
drops below OPTCR the algorithm terminates. The GAMS default for OPTCR
is 0.1.
Note, for a general gap calculation you have to be careful about the
signs of your number and the direction of optimization (min/max). Some
of our solver (e.g. CPLEX) divide by the "best integer" to derive the
relative gap.
GAMS/CPLEX license transfer with the GAMSIDE
To transfer a GAMS/CPLEX license from one PC to another do the
following.
0) Assume a GAMS/CPLEX is installed on machine A, you want to
transfer it to B
1) Open the GAMSIDE on B an create an initial GAMS/CPLEX license code
by running:
File->Options->Licenses->Cplex->Get initial license code
You will get a 28 character hexcode.
2) Open the GAMSIDE on A an run
File->Options->Licenses->Cplex->Transfer a license
You will be ask to enter a code. Please enter the code you obtained
in step 1. You will get another 28 character hexcode.
3) Go back to machine B and run
File->Options->Licenses->Cplex->Update exisiting license
You will be ask to enter a code. Please enter the code you obtained
in step 2.
That's it.
GAMS/Virus Scanner incompatibility
> My GAMS is slow and sometimes the solver does not write a solution file.
When Dr. Solomon's anti-virus software or the McAfee ant-virus scanner
is running you could run into these problems.
Adding a constraint to a model and do a warm start
> I was wondering if it were possible to solve a model using gams, and
> then to add a single constraint to the model with out rebuilding the
> entire model.
There are two ways to interpret your question: Can one add a
constraint without regenerating the rest of the model? Here the
answer is no; the entire model is regenerated, even if only one
parameter (say, an objective coefficient) changes, or indeed if none
change. "Smart" regeneration has been on our "wish-list" for some
time, but we have not implemented it yet.
However, if you solve a model and add a constraint, the model is
regenerated and the solver starts from the optimum value of the
previous model, so from the solver standpoint, there is likely to be
very little work required in the second solve. For an LP problem, one
can choose to use dual simplex on the second solve so that a feasible
start is guaranteed and the algorithm will take probably very few
pivots before reaching optimality.
Multiple solutions of a MIP
> I was wondering how you would code a Mixed Integer Linear Program,
> so that you would be able to obtain all solutions with an objective
> value less than some predetermined value for a minimisation problem.
Obtaining all solutions (with objective in a particular interval) of a
MIP is not an easy task. If you have continous variables in the MIP
there may be even infinite many optimal solutions. In this case there
is no efficient general way. You may check books on 'sensitivity
analysis' of LPs and MIP.
If your MIP consists of binary/integer variables only, there is a
possible way for your problem: You solve the original problem in order
to get one optimal solution. Then you add a new constraint to 'cut
off' the optimal solution and comes up with the next best
solution. You do this loop until the objective of the solution becomes
to small. An example of this 'cutting plane' method can be found in
the model library (model icut)
From the GAMS IDE choose file->Open in GAMS Model Library->Model icut
and run the model (by pressing F9). From a command line (DOS box or
UNIX shell) call
gamslib icut
gams icut
How to use option files
> I am trying to change GAMS options using option file to solve an LP.
> I made the following option file named chrispar.opt. Then, I
> could not figure out what to do next. Could you please tell me how to link
> this file with GAMS (I am using BDMLP)? What is the statement in my GAMS
> program I should put and/or what else should I change? Thanks very much
> in advance.
Not all solvers accept an option file. BDMLP is one of the few solvers
that does have any options controlled via an option file. The usual
GAMS option like option iterlim=xxx are, of course, processed by all
solvers. For example for the MINOS solver here is what you can do:
1) You need to tell the solver to look for an option file, one way to do
this is to add the following statement to your .gms file.
option lp=minos5;
mymodel.optfile=1;
solve mymodel ...
2) the name of the option file has to be solvername.opt. For example,
for MINOS5 you would use 'minos5.opt'
