Undo: fix problem with col widths after paste undo.
[gnumeric.git] / plugins / glpk / gnm-glpk.c
blob32326e6aada91bd43570ab8aea88d38663bba52f
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>
18 #define SOLVER_PROGRAM "glpsol"
19 #define SOLVER_URL "http://www.gnu.org/software/glpk/"
20 #define PRIVATE_KEY "::glpk::"
22 typedef struct {
23 GnmSubSolver *parent;
24 char *result_filename;
25 char *ranges_filename;
26 } GnmGlpk;
28 static void
29 gnm_glpk_cleanup (GnmGlpk *lp)
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;
37 if (lp->ranges_filename) {
38 g_unlink (lp->ranges_filename);
39 g_free (lp->ranges_filename);
40 lp->ranges_filename = NULL;
44 static void
45 gnm_glpk_final (GnmGlpk *lp)
47 gnm_glpk_cleanup (lp);
48 g_free (lp);
51 static gboolean
52 write_program (GnmSolver *sol, WorkbookControl *wbc, GError **err)
54 GnmSubSolver *subsol = GNM_SUB_SOLVER (sol);
55 GOFileSaver *fs;
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;
64 return gnm_solver_saveas (sol, wbc, fs,
65 "program-XXXXXX.cplex",
66 &subsol->program_filename,
67 err);
70 static char **
71 my_strsplit (const char *line)
73 GPtrArray *res = g_ptr_array_new ();
75 while (1) {
76 const char *end;
78 while (g_ascii_isspace (*line))
79 line++;
81 if (!*line)
82 break;
84 end = line;
85 while (*end && !g_ascii_isspace (*end))
86 end++;
88 g_ptr_array_add (res, g_strndup (line, end - line));
89 line = end;
91 g_ptr_array_add (res, NULL);
93 return (char **)g_ptr_array_free (res, FALSE);
96 static gnm_float
97 parse_number (const char *s)
99 if (strcmp (s, ".") == 0)
100 return 0;
101 return g_ascii_strtod (s, NULL);
104 typedef enum { GLPK_457, GLPK_458, GLPK_UNKNOWN } GlpkFileVersion;
106 static GlpkFileVersion
107 gnm_glpk_detect_version (GnmGlpk *lp,
108 GsfInputTextline *tl)
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;
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;
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;
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;
140 static gboolean
141 gnm_glpk_read_solution_457 (GnmGlpk *lp,
142 GsfInputTextline *tl,
143 GnmSolverResult *result,
144 GnmSolverSensitivity *sensitivity,
145 gboolean has_integer)
147 GnmSubSolver *subsol = lp->parent;
148 const char *line;
149 unsigned cols, rows, c, r;
150 int pstat, dstat;
151 gnm_float val;
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;
159 if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
160 goto fail;
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;
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;
185 for (r = 0; r < rows; r++) {
186 gnm_float pval, dval;
187 unsigned rstat;
188 unsigned cidx = r;
190 if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
191 goto fail;
193 if (has_integer)
194 continue;
196 if (sscanf (line, "%u %" GNM_SCANF_g " %" GNM_SCANF_g,
197 &rstat, &pval, &dval) != 3)
198 goto fail;
200 sensitivity->constraints[cidx].shadow_price = dval;
203 for (c = 0; c < cols; c++) {
204 gnm_float pval, dval;
205 unsigned cstat;
206 unsigned idx = c;
208 if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
209 goto fail;
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;
217 result->solution[idx] = pval;
218 if (!has_integer)
219 sensitivity->vars[idx].reduced_cost = dval;
222 // Success
223 return FALSE;
225 fail:
226 return TRUE;
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] == ' '))
236 static gboolean
237 gnm_glpk_read_solution_458 (GnmGlpk *lp,
238 GsfInputTextline *tl,
239 GnmSolverResult *result,
240 GnmSolverSensitivity *sensitivity,
241 gboolean has_integer)
243 GnmSubSolver *subsol = lp->parent;
244 const char *line;
245 unsigned cols, rows, c, r;
246 gnm_float val;
247 char pstat, dstat;
249 READ_LINE (tl, line);
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;
260 if (cols != g_hash_table_size (subsol->cell_from_name))
261 goto fail;
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;
280 for (r = 0; r < rows; r++) {
281 gnm_float pval, dval;
282 char rstat;
283 unsigned r1, cidx = r;
285 READ_LINE (tl, line);
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?
296 sensitivity->constraints[cidx].shadow_price = dval;
299 for (c = 0; c < cols; c++) {
300 gnm_float pval, dval;
301 char cstat;
302 unsigned c1, cidx = c;
304 READ_LINE (tl, line);
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?
315 result->solution[cidx] = pval;
318 // Success
319 return FALSE;
321 fail:
322 return TRUE;
325 static void
326 gnm_glpk_read_solution (GnmGlpk *lp)
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;
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);
345 result = g_object_new (GNM_SOLVER_RESULT_TYPE, NULL);
346 result->solution = g_new0 (gnm_float, sol->input_cells->len);
348 sensitivity = gnm_solver_sensitivity_new (sol);
351 * glpsol's output format is different if there are any integer
352 * constraint. Go figure.
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);
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;
376 g_object_unref (tl);
377 tl = NULL;
379 // ----------------------------------------
381 if (!lp->ranges_filename)
382 goto done;
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);
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.
395 while ((line = gsf_input_textline_utf8_gets (tl)) != NULL) {
396 gchar **items, **items2 = NULL;
397 int len, len2 = 0;
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;
410 if (state == SEC_UNKNOWN)
411 continue;
413 items = my_strsplit (line);
414 len = g_strv_length (items);
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);
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;
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;
445 g_strfreev (items);
446 g_strfreev (items2);
450 g_object_unref (tl);
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);
460 return;
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);
473 static void
474 gnm_glpk_child_exit (GnmSubSolver *subsol, gboolean normal, int code,
475 GnmGlpk *lp)
477 GnmSolver *sol = GNM_SOLVER (subsol);
479 if (sol->status != GNM_SOLVER_STATUS_RUNNING)
480 return;
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;
490 default:
491 break;
495 if (sol->status == GNM_SOLVER_STATUS_RUNNING)
496 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_ERROR);
499 static void
500 cb_child_setup (gpointer user)
502 const char *lcvars[] = {
503 "LC_ALL",
504 "LC_MESSAGES",
505 "LC_CTYPE",
506 "LC_NUMERIC"
508 unsigned ui;
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);
518 static gboolean
519 gnm_glpk_prepare (GnmSolver *sol, WorkbookControl *wbc, GError **err,
520 GnmGlpk *lp)
522 gboolean ok;
523 int fd;
525 g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_READY, FALSE);
527 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_PREPARING);
528 ok = write_program (sol, wbc, err);
529 if (!ok)
530 goto fail;
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;
538 close (fd);
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;
547 close (fd);
550 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_PREPARED);
552 return TRUE;
554 fail:
555 gnm_glpk_cleanup (lp);
556 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_ERROR);
557 return FALSE;
560 static gboolean
561 gnm_glpk_start (GnmSolver *sol, WorkbookControl *wbc, GError **err,
562 GnmGlpk *lp)
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;
571 g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_PREPARED, FALSE);
573 binary = gnm_conf_get_plugin_glpk_glpsol_path ();
574 if (binary == NULL || *binary == 0)
575 binary = SOLVER_PROGRAM;
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;
587 argv[argc++] = (gchar *)"--cpxlp";
588 argv[argc++] = subsol->program_filename;
589 argv[argc] = NULL;
590 g_assert (argc < (int)G_N_ELEMENTS (argv));
592 ok = gnm_sub_solver_spawn (subsol, argv,
593 cb_child_setup, NULL,
594 NULL, NULL,
595 NULL, NULL,
596 err);
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);
609 return ok;
612 static gboolean
613 gnm_glpk_stop (GnmSolver *sol, GError *err, GnmGlpk *lp)
615 g_return_val_if_fail (sol->status == GNM_SOLVER_STATUS_RUNNING, FALSE);
617 gnm_glpk_cleanup (lp);
619 gnm_solver_set_status (sol, GNM_SOLVER_STATUS_CANCELLED);
621 return TRUE;
624 GnmSolver *
625 glpk_solver_create (GnmSolverParameters *params)
627 GnmSolver *res = g_object_new (GNM_SUB_SOLVER_TYPE,
628 "params", params,
629 NULL);
630 GnmGlpk *lp = g_new0 (GnmGlpk, 1);
632 lp->parent = GNM_SUB_SOLVER (res);
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);
639 g_object_set_data_full (G_OBJECT (res), PRIVATE_KEY, lp,
640 (GDestroyNotify)gnm_glpk_final);
642 return res;
645 gboolean
646 glpk_solver_factory_functional (GnmSolverFactory *factory,
647 WBCGtk *wbcg)
649 const char *full_path = gnm_conf_get_plugin_glpk_glpsol_path ();
650 char *path;
652 if (full_path && *full_path)
653 return g_file_test (full_path, G_FILE_TEST_IS_EXECUTABLE);
655 path = g_find_program_in_path (SOLVER_PROGRAM);
656 if (path) {
657 g_free (path);
658 return TRUE;
661 if (!wbcg)
662 return FALSE;
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;
674 return FALSE;
677 GnmSolver *
678 glpk_solver_factory (GnmSolverFactory *factory, GnmSolverParameters *params)
680 return glpk_solver_create (params);