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 <gutils.h>
9 #include <gnumeric-conf.h>
10 #include <gsf/gsf-impl-utils.h>
11 #include <gsf/gsf-input-textline.h>
12 #include <gsf/gsf-input-stdio.h>
13 #include <glib/gi18n-lib.h>
14 #include <glib/gstdio.h>
15 #include <string.h>
16 #include <unistd.h>
17
18 #define SOLVER_PROGRAM "glpsol"
19 #define SOLVER_URL "http://www.gnu.org/software/glpk/"
20 #define PRIVATE_KEY "::glpk::"
21
22 typedef struct {
23 GnmSubSolver *parent;
24 char *result_filename;
25 char *ranges_filename;
26 } GnmGlpk;
27
28 static void
gnm_glpk_cleanup(GnmGlpk * lp)29 gnm_glpk_cleanup (GnmGlpk *lp)
30 {
31 gnm_sub_solver_clear (lp->parent);
32 if (lp->result_filename) {
33 g_unlink (lp->result_filename);
34 g_free (lp->result_filename);
35 lp->result_filename = NULL;
36 }
37 if (lp->ranges_filename) {
38 g_unlink (lp->ranges_filename);
39 g_free (lp->ranges_filename);
40 lp->ranges_filename = NULL;
41 }
42 }
43
44 static void
gnm_glpk_final(GnmGlpk * lp)45 gnm_glpk_final (GnmGlpk *lp)
46 {
47 gnm_glpk_cleanup (lp);
48 g_free (lp);
49 }
50
51 static gboolean
write_program(GnmSolver * sol,WorkbookControl * wbc,GError ** err)52 write_program (GnmSolver *sol, WorkbookControl *wbc, GError **err)
53 {
54 GnmSubSolver *subsol = GNM_SUB_SOLVER (sol);
55 GOFileSaver *fs;
56
57 fs = go_file_saver_for_mime_type ("application/glpk");
58 if (!fs) {
59 g_set_error (err, G_FILE_ERROR, 0,
60 _("The GLPK exporter is not available."));
61 return FALSE;
62 }
63
64 return gnm_solver_saveas (sol, wbc, fs,
65 "program-XXXXXX.cplex",
66 &subsol->program_filename,
67 err);
68 }
69
70 static char **
my_strsplit(const char * line)71 my_strsplit (const char *line)
72 {
73 GPtrArray *res = g_ptr_array_new ();
74
75 while (1) {
76 const char *end;
77
78 while (g_ascii_isspace (*line))
79 line++;
80
81 if (!*line)
82 break;
83
84 end = line;
85 while (*end && !g_ascii_isspace (*end))
86 end++;
87
88 g_ptr_array_add (res, g_strndup (line, end - line));
89 line = end;
90 }
91 g_ptr_array_add (res, NULL);
92
93 return (char **)g_ptr_array_free (res, FALSE);
94 }
95
96 static gnm_float
parse_number(const char * s)97 parse_number (const char *s)
98 {
99 if (strcmp (s, ".") == 0)
100 return 0;
101 return g_ascii_strtod (s, NULL);
102 }
103
104 typedef enum { GLPK_457, GLPK_458, GLPK_UNKNOWN } GlpkFileVersion;
105
106 static GlpkFileVersion
gnm_glpk_detect_version(GnmGlpk * lp,GsfInputTextline * tl)107 gnm_glpk_detect_version (GnmGlpk *lp,
108 GsfInputTextline *tl)
109 {
110 GnmSubSolver *subsol = lp->parent;
111 gsf_off_t cur = gsf_input_tell (GSF_INPUT (tl));
112 GlpkFileVersion ver = GLPK_UNKNOWN;
113 const char *line;
114 unsigned cols, rows;
115
116 if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
117 goto out;
118 if (sscanf (line, "%u %u", &rows, &cols) == 2 &&
119 cols == g_hash_table_size (subsol->cell_from_name)) {
120 ver = GLPK_457;
121 if (gnm_solver_debug ())
122 g_printerr ("Detected version 4.57 file format\n");
123 goto out;
124 }
125
126 if ((line[0] == 'c' || line[0] == 's') && line[1] == ' ') {
127 ver = GLPK_458;
128 if (gnm_solver_debug ())
129 g_printerr ("Detected version 4.58 file format\n");
130 goto out;
131 }
132
133 out:
134 // Extra seek due to gsf bug
135 gsf_input_seek (GSF_INPUT (tl), cur + 1, G_SEEK_SET);
136 gsf_input_seek (GSF_INPUT (tl), cur, G_SEEK_SET);
137 return ver;
138 }
139
140 static gboolean
gnm_glpk_read_solution_457(GnmGlpk * lp,GsfInputTextline * tl,GnmSolverResult * result,GnmSolverSensitivity * sensitivity,gboolean has_integer)141 gnm_glpk_read_solution_457 (GnmGlpk *lp,
142 GsfInputTextline *tl,
143 GnmSolverResult *result,
144 GnmSolverSensitivity *sensitivity,
145 gboolean has_integer)
146 {
147 GnmSubSolver *subsol = lp->parent;
148 const char *line;
149 unsigned cols, rows, c, r;
150 int pstat, dstat;
151 gnm_float val;
152
153 if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
154 goto fail;
155 if (sscanf (line, "%u %u", &rows, &cols) != 2 ||
156 cols != g_hash_table_size (subsol->cell_from_name))
157 goto fail;
158
159 if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
160 goto fail;
161
162 if (has_integer
163 ? sscanf (line, "%d %" GNM_SCANF_g, &pstat, &val) != 2
164 : sscanf (line, "%d %d %" GNM_SCANF_g, &pstat, &dstat, &val) != 3)
165 goto fail;
166
167 result->value = val;
168 switch (pstat) {
169 case 2:
170 case 5:
171 result->quality = GNM_SOLVER_RESULT_OPTIMAL;
172 break;
173 case 1: /* "Undefined" -- see #611407 */
174 case 3:
175 case 4:
176 result->quality = GNM_SOLVER_RESULT_INFEASIBLE;
177 break;
178 case 6:
179 result->quality = GNM_SOLVER_RESULT_UNBOUNDED;
180 break;
181 default:
182 goto fail;
183 }
184
185 for (r = 0; r < rows; r++) {
186 gnm_float pval, dval;
187 unsigned rstat;
188 unsigned cidx = r;
189
190 if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
191 goto fail;
192
193 if (has_integer)
194 continue;
195
196 if (sscanf (line, "%u %" GNM_SCANF_g " %" GNM_SCANF_g,
197 &rstat, &pval, &dval) != 3)
198 goto fail;
199
200 sensitivity->constraints[cidx].shadow_price = dval;
201 }
202
203 for (c = 0; c < cols; c++) {
204 gnm_float pval, dval;
205 unsigned cstat;
206 unsigned idx = c;
207
208 if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
209 goto fail;
210
211 if (has_integer
212 ? sscanf (line, "%" GNM_SCANF_g, &pval) != 1
213 : sscanf (line, "%u %" GNM_SCANF_g " %" GNM_SCANF_g,
214 &cstat, &pval, &dval) != 3)
215 goto fail;
216
217 result->solution[idx] = pval;
218 if (!has_integer)
219 sensitivity->vars[idx].reduced_cost = dval;
220 }
221
222 // Success
223 return FALSE;
224
225 fail:
226 return TRUE;
227 }
228
229 #define READ_LINE(tl,line) do { \
230 line = gsf_input_textline_utf8_gets (tl); \
231 if (!line) goto fail; \
232 if (gnm_solver_debug ()) \
233 g_printerr ("%s\n", line); \
234 } while (line[0] == 'c' && (line[1] == 0 || line[1] == ' '))
235
236 static gboolean
gnm_glpk_read_solution_458(GnmGlpk * lp,GsfInputTextline * tl,GnmSolverResult * result,GnmSolverSensitivity * sensitivity,gboolean has_integer)237 gnm_glpk_read_solution_458 (GnmGlpk *lp,
238 GsfInputTextline *tl,
239 GnmSolverResult *result,
240 GnmSolverSensitivity *sensitivity,
241 gboolean has_integer)
242 {
243 GnmSubSolver *subsol = lp->parent;
244 const char *line;
245 unsigned cols, rows, c, r;
246 gnm_float val;
247 char pstat, dstat;
248
249 READ_LINE (tl, line);
250
251 if (has_integer) {
252 if (sscanf (line, "s %*s %u %u %c %" GNM_SCANF_g,
253 &rows, &cols, &pstat, &val) != 4)
254 goto fail;
255 } else {
256 if (sscanf (line, "s %*s %u %u %c %c %" GNM_SCANF_g,
257 &rows, &cols, &pstat, &dstat, &val) != 5)
258 goto fail;
259 }
260 if (cols != g_hash_table_size (subsol->cell_from_name))
261 goto fail;
262
263 result->value = val;
264 switch (pstat) {
265 case 'o':
266 result->quality = GNM_SOLVER_RESULT_OPTIMAL;
267 break;
268 case 'f':
269 result->quality = GNM_SOLVER_RESULT_FEASIBLE;
270 break;
271 case 'u':
272 case 'i':
273 case 'n':
274 result->quality = GNM_SOLVER_RESULT_INFEASIBLE;
275 break;
276 default:
277 goto fail;
278 }
279
280 for (r = 0; r < rows; r++) {
281 gnm_float pval, dval;
282 char rstat;
283 unsigned r1, cidx = r;
284
285 READ_LINE (tl, line);
286
287 if ((has_integer
288 ? sscanf (line, "i %d %" GNM_SCANF_g,
289 &r1, &dval) != 2
290 : sscanf (line, "i %d %c %" GNM_SCANF_g " %" GNM_SCANF_g,
291 &r1, &rstat, &pval, &dval) != 4) ||
292 r1 != cidx + 1)
293 goto fail;
294 // rstat?
295
296 sensitivity->constraints[cidx].shadow_price = dval;
297 }
298
299 for (c = 0; c < cols; c++) {
300 gnm_float pval, dval;
301 char cstat;
302 unsigned c1, cidx = c;
303
304 READ_LINE (tl, line);
305
306 if ((has_integer
307 ? sscanf (line, "j %d %" GNM_SCANF_g,
308 &c1, &pval) != 2
309 : sscanf (line, "j %d %c %" GNM_SCANF_g " %" GNM_SCANF_g,
310 &c1, &cstat, &pval, &dval) != 4) ||
311 c1 != cidx + 1)
312 goto fail;
313 // cstat?
314
315 result->solution[cidx] = pval;
316 }
317
318 // Success
319 return FALSE;
320
321 fail:
322 return TRUE;
323 }
324
325 static void
gnm_glpk_read_solution(GnmGlpk * lp)326 gnm_glpk_read_solution (GnmGlpk *lp)
327 {
328 GnmSubSolver *subsol = lp->parent;
329 GnmSolver *sol = GNM_SOLVER (subsol);
330 GsfInput *input;
331 GsfInputTextline *tl = NULL;
332 const char *line;
333 GnmSolverResult *result = NULL;
334 GnmSolverSensitivity *sensitivity = NULL;
335 enum { SEC_UNKNOWN, SEC_ROWS, SEC_COLUMNS } state;
336 gboolean has_integer;
337 GSList *l;
338
339 input = gsf_input_stdio_new (lp->result_filename, NULL);
340 if (!input)
341 goto fail;
342 tl = GSF_INPUT_TEXTLINE (gsf_input_textline_new (input));
343 g_object_unref (input);
344
345 result = g_object_new (GNM_SOLVER_RESULT_TYPE, NULL);
346 result->solution = g_new0 (gnm_float, sol->input_cells->len);
347
348 sensitivity = gnm_solver_sensitivity_new (sol);
349
350 /*
351 * glpsol's output format is different if there are any integer
352 * constraint. Go figure.
353 */
354 has_integer = sol->params->options.assume_discrete;
355 for (l = sol->params->constraints; !has_integer && l; l = l->next) {
356 GnmSolverConstraint *c = l->data;
357 has_integer = (c->type == GNM_SOLVER_INTEGER ||
358 c->type == GNM_SOLVER_BOOLEAN);
359 }
360
361 switch (gnm_glpk_detect_version (lp, tl)) {
362 case GLPK_457:
363 if (gnm_glpk_read_solution_457 (lp, tl, result, sensitivity,
364 has_integer))
365 goto fail;
366 break;
367 case GLPK_458:
368 if (gnm_glpk_read_solution_458 (lp, tl, result, sensitivity,
369 has_integer))
370 goto fail;
371 break;
372 default:
373 goto fail;
374 }
375
376 g_object_unref (tl);
377 tl = NULL;
378
379 // ----------------------------------------
380
381 if (!lp->ranges_filename)
382 goto done;
383
384 input = gsf_input_stdio_new (lp->ranges_filename, NULL);
385 if (!input)
386 goto fail;
387 tl = GSF_INPUT_TEXTLINE (gsf_input_textline_new (input));
388 g_object_unref (input);
389
390 state = SEC_UNKNOWN;
391 // We are reading a file intended for human consumption.
392 // That is unfortunately because it implies rounding, for example.
393 // The information does not appear to be available elsewhere.
394
395 while ((line = gsf_input_textline_utf8_gets (tl)) != NULL) {
396 gchar **items, **items2 = NULL;
397 int len, len2 = 0;
398
399 if (g_str_has_prefix (line, " No. Row name")) {
400 state = SEC_ROWS;
401 continue;
402 } else if (g_str_has_prefix (line, " No. Column name")) {
403 state = SEC_COLUMNS;
404 continue;
405 } else if (g_ascii_isalpha (line[0])) {
406 state = SEC_UNKNOWN;
407 continue;
408 }
409
410 if (state == SEC_UNKNOWN)
411 continue;
412
413 items = my_strsplit (line);
414 len = g_strv_length (items);
415
416 if (len == 10 && g_ascii_isdigit (items[0][0])) {
417 line = gsf_input_textline_utf8_gets (tl);
418 if (line) {
419 items2 = my_strsplit (line);
420 len2 = g_strv_length (items2);
421 }
422 }
423
424 if (len == 10 && len2 == 6 && state == SEC_COLUMNS) {
425 gnm_float low = parse_number (items[7]);
426 gnm_float high = parse_number (items2[3]);
427 GnmCell const *cell = gnm_sub_solver_find_cell (lp->parent, items[1]);
428 int idx = gnm_solver_cell_index (sol, cell);
429 if (idx >= 0) {
430 sensitivity->vars[idx].low = low;
431 sensitivity->vars[idx].high = high;
432 }
433 }
434
435 if (len == 10 && len2 == 6 && state == SEC_ROWS) {
436 gnm_float low = parse_number (items[6]);
437 gnm_float high = parse_number (items2[2]);
438 int cidx = gnm_sub_solver_find_constraint (lp->parent, items[1]);
439 if (cidx >= 0) {
440 sensitivity->constraints[cidx].low = low;
441 sensitivity->constraints[cidx].high = high;
442 }
443 }
444
445 g_strfreev (items);
446 g_strfreev (items2);
447
448 }
449
450 g_object_unref (tl);
451
452 // ----------------------------------------
453 done:
454 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_DONE);
455 g_object_set (subsol, "result", result, NULL);
456 g_object_unref (result);
457 g_object_set (subsol, "sensitivity", sensitivity, NULL);
458 g_object_unref (sensitivity);
459
460 return;
461
462 fail:
463 if (tl)
464 g_object_unref (tl);
465 if (result)
466 g_object_unref (result);
467 if (sensitivity)
468 g_object_unref (sensitivity);
469 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_ERROR);
470 }
471
472
473 static void
gnm_glpk_child_exit(GnmSubSolver * subsol,gboolean normal,int code,GnmGlpk * lp)474 gnm_glpk_child_exit (GnmSubSolver *subsol, gboolean normal, int code,
475 GnmGlpk *lp)
476 {
477 GnmSolver *sol = GNM_SOLVER (subsol);
478
479 if (sol->status != GNM_SOLVER_STATUS_RUNNING)
480 return;
481
482 if (normal) {
483 switch (code) {
484 case 0: {
485 GnmLocale *locale = gnm_push_C_locale ();
486 gnm_glpk_read_solution (lp);
487 gnm_pop_C_locale (locale);
488 break;
489 }
490 default:
491 break;
492 }
493 }
494
495 if (sol->status == GNM_SOLVER_STATUS_RUNNING)
496 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_ERROR);
497 }
498
499 static void
cb_child_setup(gpointer user)500 cb_child_setup (gpointer user)
501 {
502 const char *lcvars[] = {
503 "LC_ALL",
504 "LC_MESSAGES",
505 "LC_CTYPE",
506 "LC_NUMERIC"
507 };
508 unsigned ui;
509
510 g_unsetenv ("LANG");
511 for (ui = 0; ui < G_N_ELEMENTS (lcvars); ui++) {
512 const char *v = lcvars[ui];
513 if (g_getenv (v))
514 g_setenv (v, "C", TRUE);
515 }
516 }
517
518 static gboolean
gnm_glpk_prepare(GnmSolver * sol,WorkbookControl * wbc,GError ** err,GnmGlpk * lp)519 gnm_glpk_prepare (GnmSolver *sol, WorkbookControl *wbc, GError **err,
520 GnmGlpk *lp)
521 {
522 gboolean ok;
523 int fd;
524
525 g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_READY, FALSE);
526
527 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_PREPARING);
528 ok = write_program (sol, wbc, err);
529 if (!ok)
530 goto fail;
531
532 fd = g_file_open_tmp ("program-XXXXXX.out", &lp->result_filename, err);
533 if (fd == -1) {
534 g_set_error (err, G_FILE_ERROR, 0,
535 _("Failed to create file for solution"));
536 goto fail;
537 }
538 close (fd);
539
540 if (sol->params->options.sensitivity_report) {
541 fd = g_file_open_tmp ("program-XXXXXX.ran", &lp->ranges_filename, err);
542 if (fd == -1) {
543 g_set_error (err, G_FILE_ERROR, 0,
544 _("Failed to create file for sensitivity report"));
545 goto fail;
546 }
547 close (fd);
548 }
549
550 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_PREPARED);
551
552 return TRUE;
553
554 fail:
555 gnm_glpk_cleanup (lp);
556 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_ERROR);
557 return FALSE;
558 }
559
560 static gboolean
gnm_glpk_start(GnmSolver * sol,WorkbookControl * wbc,GError ** err,GnmGlpk * lp)561 gnm_glpk_start (GnmSolver *sol, WorkbookControl *wbc, GError **err,
562 GnmGlpk *lp)
563 {
564 GnmSubSolver *subsol = GNM_SUB_SOLVER (sol);
565 gboolean ok;
566 gchar *argv[9];
567 int argc = 0;
568 GnmSolverParameters *param = sol->params;
569 const char *binary;
570
571 g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_PREPARED, FALSE);
572
573 binary = gnm_conf_get_plugin_glpk_glpsol_path ();
574 if (binary == NULL || *binary == 0)
575 binary = SOLVER_PROGRAM;
576
577 argv[argc++] = (gchar *)binary;
578 argv[argc++] = (gchar *)(param->options.automatic_scaling
579 ? "--scale"
580 : "--noscale");
581 argv[argc++] = (gchar *)"--write";
582 argv[argc++] = lp->result_filename;
583 if (lp->ranges_filename) {
584 argv[argc++] = (gchar *)"--ranges";
585 argv[argc++] = lp->ranges_filename;
586 }
587 argv[argc++] = (gchar *)"--cpxlp";
588 argv[argc++] = subsol->program_filename;
589 argv[argc] = NULL;
590 g_assert (argc < (int)G_N_ELEMENTS (argv));
591
592 ok = gnm_sub_solver_spawn (subsol, argv,
593 cb_child_setup, NULL,
594 NULL, NULL,
595 NULL, NULL,
596 err);
597
598 if (!ok && err &&
599 g_error_matches (*err, G_SPAWN_ERROR, G_SPAWN_ERROR_NOENT)) {
600 g_clear_error (err);
601 g_set_error (err, G_SPAWN_ERROR, G_SPAWN_ERROR_NOENT,
602 _("The %s program was not found. You can either "
603 "install it or use another solver. "
604 "For more information see %s"),
605 SOLVER_PROGRAM,
606 SOLVER_URL);
607 }
608
609 return ok;
610 }
611
612 static gboolean
gnm_glpk_stop(GnmSolver * sol,GError * err,GnmGlpk * lp)613 gnm_glpk_stop (GnmSolver *sol, GError *err, GnmGlpk *lp)
614 {
615 g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_RUNNING, FALSE);
616
617 gnm_glpk_cleanup (lp);
618
619 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_CANCELLED);
620
621 return TRUE;
622 }
623
624 GnmSolver *
glpk_solver_create(GnmSolverParameters * params)625 glpk_solver_create (GnmSolverParameters *params)
626 {
627 GnmSolver *res = g_object_new (GNM_SUB_SOLVER_TYPE,
628 "params", params,
629 NULL);
630 GnmGlpk *lp = g_new0 (GnmGlpk, 1);
631
632 lp->parent = GNM_SUB_SOLVER (res);
633
634 g_signal_connect (res, "prepare", G_CALLBACK (gnm_glpk_prepare), lp);
635 g_signal_connect (res, "start", G_CALLBACK (gnm_glpk_start), lp);
636 g_signal_connect (res, "stop", G_CALLBACK (gnm_glpk_stop), lp);
637 g_signal_connect (res, "child-exit", G_CALLBACK (gnm_glpk_child_exit), lp);
638
639 g_object_set_data_full (G_OBJECT (res), PRIVATE_KEY, lp,
640 (GDestroyNotify)gnm_glpk_final);
641
642 return res;
643 }
644
645 gboolean
glpk_solver_factory_functional(GnmSolverFactory * factory,WBCGtk * wbcg)646 glpk_solver_factory_functional (GnmSolverFactory *factory,
647 WBCGtk *wbcg)
648 {
649 const char *full_path = gnm_conf_get_plugin_glpk_glpsol_path ();
650 char *path;
651
652 if (full_path && *full_path)
653 return g_file_test (full_path, G_FILE_TEST_IS_EXECUTABLE);
654
655 path = g_find_program_in_path (SOLVER_PROGRAM);
656 if (path) {
657 g_free (path);
658 return TRUE;
659 }
660
661 if (!wbcg)
662 return FALSE;
663
664 path = gnm_sub_solver_locate_binary (SOLVER_PROGRAM,
665 "Gnu Linear Programming Kit",
666 SOLVER_URL,
667 wbcg);
668 if (path) {
669 gnm_conf_set_plugin_glpk_glpsol_path (path);
670 g_free (path);
671 return TRUE;
672 }
673
674 return FALSE;
675 }
676
677 GnmSolver *
glpk_solver_factory(GnmSolverFactory * factory,GnmSolverParameters * params)678 glpk_solver_factory (GnmSolverFactory *factory, GnmSolverParameters *params)
679 {
680 return glpk_solver_create (params);
681 }
682