Supplement to bug-report:
========================


Problem, mentioned in bug-report:


"every LP-problem with the objective function of the form:

  sum   (c_i * x_i) - K
(i=1..n)

is passed incorrectly to the solver engine (lp_solve or glpk)"


demonstrated itself also with constraints of above-mentioned type.
 
On the other side, such type of problems can be solved correctly in Excel.
 
Below we propose the possible solution,  we had applied to our local
copies of Gnumeric 1.4.3. The big LP-problems which caused CRASH
of Gnumeric before, now run without problems.  

=========================================================================

Proposed solution of bug (with commentaries :-)
-----------------------------------------------



1. Understanding the function

   get_lp_coeff(GnmCell *Target, GnmCell *Change, gnm_float *x0):
-----------------------------------------------------------------

If cell Target contains "affine" combination:

  L(x_1,...,x_n) =    sum    x_i * c_i + K
                    (i=1..n)   

of variables x_i and cell Change contains some variable x_k
AND *x0 is the value 
                      L(0,0, ...,0)=K

then L_1k = L(0,0,...,x_k=1.0,0,...0) = c_k * 1.0 + K.

We can compute the coefficient c_k as:
 
                          c_k = L_1k - K.


2. Why lp_qp_solver_init(...) is wrong:
---------------------------------------


In lp_qp_solver_init(...) the function get_lp_coeff(...)
is used for determining coefficients of linear combinations
of variables x_i in objective function and also in rows    
of matrix of constraints.

The recipe is always the same, for objective function it is:

     A. get Target cell with "affine" combination:

        target = solver_get_target_cell (sheet);

     B. Set all input variables to zero and evaluate target:
        clear_input_vars (param->n_variables, res);
        cell_eval (target);

     C. Store the value K in x0 for use in get_lp_coeff(...,*x0);
        also store it in base (x0 will be overwritten):

        x0 = base = value_get_as_float (target->value);

     D. Get and set up the objective function coefficients,
        using  get_lp_coeff(...,*x0).   

In case of objective function, we do not need to use the value K,
because optimal solution is the same for all "shifted" obj.
functions (....) + K.


Setup of constraints begins on line 386 of solver.c:

  for (i = ind = 0; i < param->n_total_constraints; i++) {
   
          ... visiting rows of constraint matrix ...

         Step A:
         
         target = sheet_cell_get (...);
         
         Step B:     (line 419)
         
         clear_input_vars (param->n_variables, res);
   
         Step C: ???
         
         x0 = base;
         for (n = 0; n < param->n_variables; n++) {
                x = get_lp_coeff (target,
                                  solver_get_input_var (res, n), &x0);

         This is evidently wrong. The value of "base" was set for
         objective function!  
          
         So we should insert after line 419 the following two lines:
           
------->          cell_eval (target);
------->          x0 = base = value_get_as_float (target->value);

         exactly as in processing of objective function above.


The benefit of that fix is also, that if row of constraints was given
in "affine" form with additive constant C:
         
                    sum a_i * x_i + C   (op) Rh_value

where (op) is one of <=, >=, <. >, we have stored the value of C
in variable "base". 


This allows us to transform that row to "canonical form":
         
                    sum a_i * x_i (op) Rh_value - C.
         
So, to be able to solve such class of problems (with additive constant
in LHS - Excel can do it!), we should apply another fix:


In line (now about No. 444)

        x = value_get_as_float (target->value);

the right thing is to write:

        x = value_get_as_float (target->value) - base;

and after next line:
        alg->set_constr_fn (program, ind, c->type, x);
                     
we will set also:    
        res->rhs[i]=x;            (FFF1)

This is needed for generating of program report. If we left this out,
the reported program will be wrong - without additive constants 
in LHS's of constraints, but with unmodified RHS's.
                 
                 
Those were changes in solver.c.

======================================================================

In reports.c:

comment line 282:

   (FFF2)     /*  res->rhs[i] = value_get_as_float (cell->value); */


I am not absolutely sure about fixes (FFF1) and (FFF2) concerning
program report generation. For my testing examples they work.

The only thing that really worries me here is the question of how this could
ever have worked (assuming you are right -- I haven't checked).  Did lp_solve
change calling conventions?

Morten what makes you think this ever worked? The objective function of

  sum   (c_i * x_i) - K
(i=1..n)

is quite unlikely to be used by a lazy typist since maximizing or minimizing it
is equivalent to maximizing or minimizing

  sum   (c_i * x_i)
(i=1..n)

and that works just fine.

Andreas: I am _hoping_ that this was once tested!  If you feel confident in
the suggested fixes, though, do go ahead and apply.

Hi, Morten, Andreas,

   Andreas is right in that things never worked in Gnumeric for the objective
function of the form:

                    sum   (c_i * x_i) - K
                  (i=1..n)

   But I am not sure, what the statement about "lazy typist" means. Why do You
suppose that the (only) way to enter LP problem in Gnumeric is to "type" it?

   My colleague is making "wonders" in quite un-traditonal way in spreadsheets.
He is working now on the real-world problem of local transport optimization.

   The (big) LP-problems are not entered manually, but generated from 
input data he had in Excel - now in Gnumeric, because I made some effort to
persuade him to make this transition. I tried this some time ago, but
then the solver in Gnumeric (1.0, 1.1) was not very good (Jody may remember
one of our early bug report). Now, with a quality solvers, like lp_solve
and GLPK behind the scenes, I was confident, that Gnumeric solver is
ready for serious use.

   But I was unpleasantly surprised, when he had many crashes of Gnumeric,
and in the "critical" moments of their work. I am mathematician,
not programmer (although programming - especially Python at the moment
is my big hobby). I never worked with spreadsheets, nor LP-optimization.
But I felt the duty to make every effort possible to investigate and
possibly fix the problem. The result is this bug report. 

   Maybe, Andreas has the feeling that this is not bug, but
"missing functionality" in some "exotic" area of spreadsheer use.
I can argue like this:

   1. one of highest priorities in Gnumeric is "correctness of code".
Actual solver code is not corect, because it allows to enter LP-problems
of above-mentioned type without warnings and (also without warnings)
presents to the user the incorect results.

   2. Excel can correctly solve this kind of LP-problems, but is not good
for solving big, real-time problems (this opinion a have heard from
my colleague). Gnumeric ambitions should be, to be better like Excel
in this area.  

   3. In present solver code, there is an unused variable "base",
which, like I feel, was intended for such kind of problems; maybe, 
Jukka-Pekka can tell us more about this (if he is still reachable now). 

Hi Michael,

My comment on "lazy typists" was not meant to insult anybody. I was more a
reference to the fact that when one tries out the solver one is likely to type
in the problems and at that stage my use the simpler form rather than the more
complicated one. So the bug is likely to escape attention. So while I would have
hoped )as Morten does= that this was once tested, I am not surprised that it
possibly wasn't.

And I definitely agree that this is a bug to be fixed )but I don't know any of
the code in that part of gnumeric, so am not in a position to really help with
that. Nor can I really assess whether your proposed patch is appropriate. (And
until exams are over in late April I don't have the time to investigate the
code. Hopefully the programmer (Jukka-Pekka) of this part of Gnumeric can have a
look at it before.)

There is really no need to argue that it is a bug. And we defintiely would not
want to call it a feature.

And I hope you meant "better than Excel" rather than "better like Excel". :-)

Andreas,

  thanks for good reply. Certainly, I meant "better than Excel" :-)
My comments above about proposed changes were intended to help someone (like me),
which is not expert in Gnumeric solver code, to test and understand, what was
wrong with code and why the changes will help.

  Sorry, but I have not seen Jukka-Pekka in ChangeLog-s for two or more years.
He makes very good codebase. But now - can he still maintain and expand it?
If not, someone else should take care of that area (it concerns also v. 1.5).
I can sporadically send some suggestions and small chunks of code, 
but have no necesary skills to make more.  
  
   Good luck with exams!

     

Created attachment 47032 [details] [review]
merge the proposed fixes into CVS head.

Michal : nice work.  Having detailed analysis of the problem along with the
poposed changes was a big help.  As you've noticed the solver is not getting
alot of attention.  Any other problems or improvements you think of would be
useful.

Morten : I suspect the problem was two fold.  The missing cell_evals were most
likely a bug introduced when we moved to the new recalc semantics in 1.2. 
Before that we would recalc ranges automaticly rather than on demand.  The
incorrect base value is probably just a bug that no one noticed/reported.

I'll commit the proposed patch this evening.

Fixed in cvs.