plugins/lpsolve/gnm-lpsolve.c

   1 #include <gnumeric-config.h>
   2 #include "gnumeric.h"
   3 #include "boot.h"
   4 #include "cell.h"
   5 #include "sheet.h"
   6 #include "value.h"
   7 #include "ranges.h"
   8 #include "gnumeric-conf.h"
   9 #include <gsf/gsf-impl-utils.h>
  10 #include <glib/gi18n-lib.h>
  11 #include <string.h>
  12
  13 #define SOLVER_PROGRAM "lp_solve"
  14 #define SOLVER_URL "http://sourceforge.net/projects/lpsolve/"
  15 #define PRIVATE_KEY "::lpsolve::"
  16 #define SOLVER_INF 1e30
  17
  18 typedef struct {
  19         GnmSubSolver *parent;
  20         GnmSolverResult *result;
  21         GnmSolverSensitivity *sensitivity;
  22         enum { SEC_UNKNOWN, SEC_VALUES,
  23                SEC_LIMITS, SEC_DUAL_LIMITS } section;
  24 } GnmLPSolve;
  25
  26 static void
  27 gnm_lpsolve_cleanup (GnmLPSolve *lp)
  28 {
  29         gnm_sub_solver_clear (lp->parent);
  30
  31         if (lp->result) {
  32                 g_object_unref (lp->result);
  33                 lp->result = NULL;
  34         }
  35
  36         if (lp->sensitivity) {
  37                 g_object_unref (lp->sensitivity);
  38                 lp->sensitivity = NULL;
  39         }
  40 }
  41
  42 static void
  43 gnm_lpsolve_final (GnmLPSolve *lp)
  44 {
  45         gnm_lpsolve_cleanup (lp);
  46         g_free (lp);
  47 }
  48
  49 static gboolean
  50 write_program (GnmSolver *sol, WorkbookControl *wbc, GError **err)
  51 {
  52         GnmSubSolver *subsol = GNM_SUB_SOLVER (sol);
  53         GOFileSaver *fs;
  54
  55         fs = go_file_saver_for_mime_type ("application/lpsolve");
  56         if (!fs) {
  57                 g_set_error (err, G_FILE_ERROR, 0,
  58                              _("The LPSolve exporter is not available."));
  59                 return FALSE;
  60         }
  61
  62         return gnm_solver_saveas (sol, wbc, fs,
  63                                   "program-XXXXXX.lp",
  64                                   &subsol->program_filename,
  65                                   err);
  66 }
  67
  68 static GnmSolverResult *
  69 gnm_lpsolve_start_solution (GnmLPSolve *lp)
  70 {
  71         int n;
  72         GnmSolver *sol;
  73
  74         g_return_val_if_fail (lp->result == NULL, NULL);
  75
  76         sol = GNM_SOLVER (lp->parent);
  77         n = sol->input_cells->len;
  78
  79         lp->result = g_object_new (GNM_SOLVER_RESULT_TYPE, NULL);
  80         lp->result->solution = g_new0 (gnm_float, n);
  81
  82         lp->sensitivity = gnm_solver_sensitivity_new (sol);
  83
  84         return lp->result;
  85 }
  86
  87 static void
  88 gnm_lpsolve_flush_solution (GnmLPSolve *lp)
  89 {
  90         if (lp->result) {
  91                 g_object_set (lp->parent, "result", lp->result, NULL);
  92                 g_object_unref (lp->result);
  93                 lp->result = NULL;
  94         }
  95         g_clear_object (&lp->sensitivity);
  96 }
  97
  98
  99 static char **
 100 my_strsplit (const char *line)
 101 {
 102         GPtrArray *res = g_ptr_array_new ();
 103
 104         while (1) {
 105                 const char *end;
 106
 107                 while (g_ascii_isspace (*line))
 108                         line++;
 109
 110                 if (!*line)
 111                         break;
 112
 113                 end = line;
 114                 while (*end && !g_ascii_isspace (*end))
 115                         end++;
 116
 117                 g_ptr_array_add (res, g_strndup (line, end - line));
 118                 line = end;
 119         }
 120         g_ptr_array_add (res, NULL);
 121
 122         return (char **)g_ptr_array_free (res, FALSE);
 123 }
 124
 125 static double
 126 fixup_inf (double v)
 127 {
 128         if (v <= -SOLVER_INF)
 129                 return go_ninf;
 130         if (v >= +SOLVER_INF)
 131                 return go_pinf;
 132         return v;
 133 }
 134
 135
 136 static gboolean
 137 cb_read_stdout (GIOChannel *channel, GIOCondition cond, GnmLPSolve *lp)
 138 {
 139         GnmSolver *sol = GNM_SOLVER (lp->parent);
 140         const char obj_line_prefix[] = "Value of objective function:";
 141         size_t obj_line_len = sizeof (obj_line_prefix) - 1;
 142         const char val_header_line[] = "Actual values of the variables:";
 143         size_t val_header_len = sizeof (val_header_line) - 1;
 144         const char limit_header_line[] = "Objective function limits:";
 145         size_t limit_header_len = sizeof (limit_header_line) - 1;
 146         const char dual_limit_header_line[] = "Dual values with from - till limits:";
 147         size_t dual_limit_header_len = sizeof (dual_limit_header_line) - 1;
 148         gchar *line = NULL;
 149
 150         do {
 151                 GIOStatus status;
 152                 gsize tpos;
 153
 154                 g_free (line);
 155                 line = NULL;
 156
 157                 status = g_io_channel_read_line (channel,
 158                                                  &line, NULL, &tpos,
 159                                                  NULL);
 160                 if (status != G_IO_STATUS_NORMAL)
 161                         break;
 162
 163                 line[tpos] = 0;
 164
 165                 if (line[0] == 0)
 166                         lp->section = SEC_UNKNOWN;
 167                 else if (lp->section == SEC_UNKNOWN &&
 168                          !strncmp (line, obj_line_prefix, obj_line_len)) {
 169                         GnmSolverResult *r;
 170                         gnm_lpsolve_flush_solution (lp);
 171                         r = gnm_lpsolve_start_solution (lp);
 172                         r->quality = GNM_SOLVER_RESULT_FEASIBLE;
 173                         r->value = g_ascii_strtod (line + obj_line_len, NULL);
 174                 } else if (lp->section == SEC_UNKNOWN &&
 175                            !strncmp (line, val_header_line, val_header_len)) {
 176                         lp->section = SEC_VALUES;
 177                 } else if (lp->section == SEC_UNKNOWN &&
 178                            !strncmp (line, limit_header_line, limit_header_len)) {
 179                         lp->section = SEC_LIMITS;
 180                 } else if (lp->section == SEC_UNKNOWN &&
 181                            !strncmp (line, dual_limit_header_line, dual_limit_header_len)) {
 182                         lp->section = SEC_DUAL_LIMITS;
 183                 } else if (lp->section == SEC_VALUES && lp->result) {
 184                         GnmSolverResult *r = lp->result;
 185                         double v;
 186                         char *space = strchr (line, ' ');
 187                         GnmCell *cell;
 188                         int idx;
 189
 190                         if (!space) {
 191                                 lp->section = SEC_UNKNOWN;
 192                                 continue;
 193                         }
 194                         *space = 0;
 195                         cell = gnm_sub_solver_find_cell (lp->parent, line);
 196                         idx = gnm_solver_cell_index (sol, cell);
 197                         if (idx < 0) {
 198                                 g_printerr ("Strange cell %s in output\n",
 199                                             line);
 200                                 lp->section = SEC_UNKNOWN;
 201                                 continue;
 202                         }
 203
 204                         v = g_ascii_strtod (space + 1, NULL);
 205                         r->solution[idx] = v;
 206                 } else if (lp->section == SEC_LIMITS) {
 207                         double low, high;
 208                         GnmCell *cell;
 209                         int idx;
 210                         gchar **items;
 211
 212                         if (g_ascii_isspace (line[0]))
 213                                 continue;
 214
 215                         items = my_strsplit (line);
 216
 217                         if (g_strv_length (items) != 4)
 218                                 goto bad_limit;
 219
 220                         cell = gnm_sub_solver_find_cell (lp->parent, items[0]);
 221                         idx = gnm_solver_cell_index (sol, cell);
 222                         if (idx < 0)
 223                                 goto bad_limit;
 224
 225                         low = fixup_inf (g_ascii_strtod (items[1], NULL));
 226                         high = fixup_inf (g_ascii_strtod (items[2], NULL));
 227
 228                         lp->sensitivity->vars[idx].low = low;
 229                         lp->sensitivity->vars[idx].high = high;
 230
 231                         g_strfreev (items);
 232
 233                         continue;
 234
 235                 bad_limit:
 236                         g_printerr ("Strange limit line in output: %s\n",
 237                                     line);
 238                         lp->section = SEC_UNKNOWN;
 239                         g_strfreev (items);
 240                 } else if (lp->section == SEC_DUAL_LIMITS) {
 241                         double dual, low, high;
 242                         GnmCell *cell;
 243                         int idx, cidx;
 244                         gchar **items;
 245
 246                         if (g_ascii_isspace (line[0]))
 247                                 continue;
 248
 249                         items = my_strsplit (line);
 250
 251                         if (g_strv_length (items) != 4)
 252                                 goto bad_dual;
 253
 254                         cell = gnm_sub_solver_find_cell (lp->parent, items[0]);
 255                         idx = gnm_solver_cell_index (sol, cell);
 256
 257                         cidx = (idx == -1)
 258                                 ? gnm_sub_solver_find_constraint (lp->parent, items[0])
 259                                 : -1;
 260
 261                         dual = fixup_inf (g_ascii_strtod (items[1], NULL));
 262                         low = fixup_inf (g_ascii_strtod (items[2], NULL));
 263                         high = fixup_inf (g_ascii_strtod (items[3], NULL));
 264
 265                         if (idx >= 0) {
 266                                 lp->sensitivity->vars[idx].reduced_cost = dual;
 267                         } else if (cidx >= 0) {
 268                                 lp->sensitivity->constraints[cidx].low = low;
 269                                 lp->sensitivity->constraints[cidx].high = high;
 270                                 lp->sensitivity->constraints[cidx].shadow_price = dual;
 271                         } else {
 272                                 // Ignore
 273                         }
 274
 275                         g_strfreev (items);
 276                         continue;
 277
 278                 bad_dual:
 279                         g_printerr ("Strange dual limit line in output: %s\n",
 280                                     line);
 281                         lp->section = SEC_UNKNOWN;
 282                         g_strfreev (items);
 283                 }
 284         } while (1);
 285
 286         g_free (line);
 287
 288         return TRUE;
 289 }
 290
 291
 292 static void
 293 gnm_lpsolve_child_exit (GnmSubSolver *subsol, gboolean normal, int code,
 294                         GnmLPSolve *lp)
 295 {
 296         GnmSolver *sol = GNM_SOLVER (subsol);
 297         GnmSolverStatus new_status = GNM_SOLVER_STATUS_DONE;
 298
 299         if (sol->status != GNM_SOLVER_STATUS_RUNNING)
 300                 return;
 301
 302         if (normal) {
 303                 GnmSolverResult *r;
 304
 305                 switch (code) {
 306                 case 0: /* Optimal */
 307                         gnm_sub_solver_flush (subsol);
 308                         if (lp->result)
 309                                 lp->result->quality = GNM_SOLVER_RESULT_OPTIMAL;
 310                         g_object_set (lp->parent,
 311                                       "sensitivity", lp->sensitivity,
 312                                       NULL);
 313                         gnm_lpsolve_flush_solution (lp);
 314                         break;
 315
 316                 case 2: /* Infeasible */
 317                         r = gnm_lpsolve_start_solution (lp);
 318                         r->quality = GNM_SOLVER_RESULT_INFEASIBLE;
 319                         gnm_lpsolve_flush_solution (lp);
 320                         break;
 321
 322                 case 3: /* Unbounded */
 323                         r = gnm_lpsolve_start_solution (lp);
 324                         r->quality = GNM_SOLVER_RESULT_UNBOUNDED;
 325                         gnm_lpsolve_flush_solution (lp);
 326                         break;
 327
 328                 case 1: /* Suboptimal */
 329                 case 4: /* Degenerate */
 330                         gnm_sub_solver_flush (subsol);
 331                         gnm_lpsolve_flush_solution (lp);
 332                         break;
 333
 334                 default:
 335                 case 5: /* Numfailure */
 336                 case 6: /* Userabort */
 337                 case 7: /* Timeout */
 338                 case 8: /* Running (eh?) */
 339                 case 9: /* Presolved (eh?) */
 340                         new_status = GNM_SOLVER_STATUS_ERROR;
 341                         break;
 342                 }
 343         } else {
 344                 /* Something bad.  */
 345                 new_status = GNM_SOLVER_STATUS_ERROR;
 346         }
 347
 348         gnm_solver_set_status (sol, new_status);
 349 }
 350
 351 static void
 352 cb_child_setup (gpointer user)
 353 {
 354         const char *lcvars[] = {
 355                 "LC_ALL",
 356                 "LC_MESSAGES",
 357                 "LC_CTYPE",
 358                 "LC_NUMERIC"
 359         };
 360         unsigned ui;
 361
 362         g_unsetenv ("LANG");
 363         for (ui = 0; ui < G_N_ELEMENTS (lcvars); ui++) {
 364                 const char *v = lcvars[ui];
 365                 if (g_getenv (v))
 366                         g_setenv (v, "C", TRUE);
 367         }
 368 }
 369
 370 static gboolean
 371 gnm_lpsolve_prepare (GnmSolver *sol, WorkbookControl *wbc, GError **err,
 372                      GnmLPSolve *lp)
 373 {
 374         gboolean ok;
 375
 376         g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_READY, FALSE);
 377
 378         gnm_solver_set_status (sol, GNM_SOLVER_STATUS_PREPARING);
 379         ok = write_program (sol, wbc, err);
 380         if (ok)
 381                 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_PREPARED);
 382         else {
 383                 gnm_lpsolve_cleanup (lp);
 384                 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_ERROR);
 385         }
 386
 387         return ok;
 388 }
 389
 390 static gboolean
 391 gnm_lpsolve_start (GnmSolver *sol, WorkbookControl *wbc, GError **err,
 392                    GnmLPSolve *lp)
 393 {
 394         GnmSubSolver *subsol = GNM_SUB_SOLVER (sol);
 395         gboolean ok;
 396         gchar *argv[6];
 397         int argc = 0;
 398         GnmSolverParameters *param = sol->params;
 399         const char *binary;
 400
 401         g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_PREPARED, FALSE);
 402
 403         binary = gnm_conf_get_plugin_lpsolve_lpsolve_path ();
 404         if (binary == NULL || *binary == 0)
 405                 binary = SOLVER_PROGRAM;
 406
 407         argv[argc++] = (gchar *)binary;
 408         argv[argc++] = (gchar *)"-i";
 409         argv[argc++] = (gchar *)(param->options.automatic_scaling
 410                                  ? "-s1"
 411                                  : "-s0");
 412         argv[argc++] = (gchar *)"-S6";
 413         argv[argc++] = subsol->program_filename;
 414         argv[argc] = NULL;
 415         g_assert (argc < (int)G_N_ELEMENTS (argv));
 416
 417         ok = gnm_sub_solver_spawn (subsol, argv,
 418                                    cb_child_setup, NULL,
 419                                    (GIOFunc)cb_read_stdout, lp,
 420                                    NULL, NULL,
 421                                    err);
 422
 423         if (!ok && err &&
 424             g_error_matches (*err, G_SPAWN_ERROR, G_SPAWN_ERROR_NOENT)) {
 425                 g_clear_error (err);
 426                 g_set_error (err, G_SPAWN_ERROR, G_SPAWN_ERROR_NOENT,
 427                              _("The %s program was not found.  You can either "
 428                                "install it or use another solver. "
 429                                "For more information see %s"),
 430                              SOLVER_PROGRAM,
 431                              SOLVER_URL);
 432         }
 433
 434         return ok;
 435 }
 436
 437 static gboolean
 438 gnm_lpsolve_stop (GnmSolver *sol, GError *err, GnmLPSolve *lp)
 439 {
 440         g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_RUNNING, FALSE);
 441
 442         gnm_lpsolve_cleanup (lp);
 443
 444         gnm_solver_set_status (sol, GNM_SOLVER_STATUS_CANCELLED);
 445
 446         return TRUE;
 447 }
 448
 449 GnmSolver *
 450 lpsolve_solver_create (GnmSolverParameters *params)
 451 {
 452         GnmSolver *res = g_object_new (GNM_SUB_SOLVER_TYPE,
 453                                        "params", params,
 454                                        NULL);
 455         GnmLPSolve *lp = g_new0 (GnmLPSolve, 1);
 456
 457         lp->parent = GNM_SUB_SOLVER (res);
 458
 459         g_signal_connect (res, "prepare", G_CALLBACK (gnm_lpsolve_prepare), lp);
 460         g_signal_connect (res, "start", G_CALLBACK (gnm_lpsolve_start), lp);
 461         g_signal_connect (res, "stop", G_CALLBACK (gnm_lpsolve_stop), lp);
 462         g_signal_connect (res, "child-exit", G_CALLBACK (gnm_lpsolve_child_exit), lp);
 463
 464         g_object_set_data_full (G_OBJECT (res), PRIVATE_KEY, lp,
 465                                 (GDestroyNotify)gnm_lpsolve_final);
 466
 467         return res;
 468 }
 469
 470
 471 gboolean
 472 lpsolve_solver_factory_functional (GnmSolverFactory *factory,
 473                                    WBCGtk *wbcg)
 474 {
 475         const char *full_path = gnm_conf_get_plugin_lpsolve_lpsolve_path ();
 476         char *path;
 477
 478         if (full_path && *full_path)
 479                 return g_file_test (full_path, G_FILE_TEST_IS_EXECUTABLE);
 480
 481         path = g_find_program_in_path (SOLVER_PROGRAM);
 482         if (path) {
 483                 g_free (path);
 484                 return TRUE;
 485         }
 486
 487         if (!wbcg)
 488                 return FALSE;
 489
 490         path = gnm_sub_solver_locate_binary (SOLVER_PROGRAM,
 491                                              "LP Solve",
 492                                              SOLVER_URL,
 493                                              wbcg);
 494         if (path) {
 495                 gnm_conf_set_plugin_lpsolve_lpsolve_path (path);
 496                 g_free (path);
 497                 return TRUE;
 498         }
 499
 500         return FALSE;
 501 }
 502
 503 GnmSolver *
 504 lpsolve_solver_factory (GnmSolverFactory *factory, GnmSolverParameters *params)
 505 {
 506         return lpsolve_solver_create (params);
 507 }