1 #include <gnumeric-config.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>
18 #define SOLVER_PROGRAM "glpsol"
19 #define SOLVER_URL "http://www.gnu.org/software/glpk/"
20 #define PRIVATE_KEY "::glpk::"
24 char *result_filename
;
25 char *ranges_filename
;
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
;
45 gnm_glpk_final (GnmGlpk
*lp
)
47 gnm_glpk_cleanup (lp
);
52 write_program (GnmSolver
*sol
, WorkbookControl
*wbc
, GError
**err
)
54 GnmSubSolver
*subsol
= GNM_SUB_SOLVER (sol
);
57 fs
= go_file_saver_for_mime_type ("application/glpk");
59 g_set_error (err
, G_FILE_ERROR
, 0,
60 _("The GLPK exporter is not available."));
64 return gnm_solver_saveas (sol
, wbc
, fs
,
65 "program-XXXXXX.cplex",
66 &subsol
->program_filename
,
71 my_strsplit (const char *line
)
73 GPtrArray
*res
= g_ptr_array_new ();
78 while (g_ascii_isspace (*line
))
85 while (*end
&& !g_ascii_isspace (*end
))
88 g_ptr_array_add (res
, g_strndup (line
, end
- line
));
91 g_ptr_array_add (res
, NULL
);
93 return (char **)g_ptr_array_free (res
, FALSE
);
97 parse_number (const char *s
)
99 if (strcmp (s
, ".") == 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
;
116 if ((line
= gsf_input_textline_utf8_gets (tl
)) == NULL
)
118 if (sscanf (line
, "%u %u", &rows
, &cols
) == 2 &&
119 cols
== g_hash_table_size (subsol
->cell_from_name
)) {
121 if (gnm_solver_debug ())
122 g_printerr ("Detected version 4.57 file format\n");
126 if ((line
[0] == 'c' || line
[0] == 's') && line
[1] == ' ') {
128 if (gnm_solver_debug ())
129 g_printerr ("Detected version 4.58 file format\n");
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
);
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
;
149 unsigned cols
, rows
, c
, r
;
153 if ((line
= gsf_input_textline_utf8_gets (tl
)) == NULL
)
155 if (sscanf (line
, "%u %u", &rows
, &cols
) != 2 ||
156 cols
!= g_hash_table_size (subsol
->cell_from_name
))
159 if ((line
= gsf_input_textline_utf8_gets (tl
)) == NULL
)
163 ? sscanf (line
, "%d %" GNM_SCANF_g
, &pstat
, &val
) != 2
164 : sscanf (line
, "%d %d %" GNM_SCANF_g
, &pstat
, &dstat
, &val
) != 3)
171 result
->quality
= GNM_SOLVER_RESULT_OPTIMAL
;
173 case 1: /* "Undefined" -- see #611407 */
176 result
->quality
= GNM_SOLVER_RESULT_INFEASIBLE
;
179 result
->quality
= GNM_SOLVER_RESULT_UNBOUNDED
;
185 for (r
= 0; r
< rows
; r
++) {
186 gnm_float pval
, dval
;
190 if ((line
= gsf_input_textline_utf8_gets (tl
)) == NULL
)
196 if (sscanf (line
, "%u %" GNM_SCANF_g
" %" GNM_SCANF_g
,
197 &rstat
, &pval
, &dval
) != 3)
200 sensitivity
->constraints
[cidx
].shadow_price
= dval
;
203 for (c
= 0; c
< cols
; c
++) {
204 gnm_float pval
, dval
;
208 if ((line
= gsf_input_textline_utf8_gets (tl
)) == NULL
)
212 ? sscanf (line
, "%" GNM_SCANF_g
, &pval
) != 1
213 : sscanf (line
, "%u %" GNM_SCANF_g
" %" GNM_SCANF_g
,
214 &cstat
, &pval
, &dval
) != 3)
217 result
->solution
[idx
] = pval
;
219 sensitivity
->vars
[idx
].reduced_cost
= dval
;
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] == ' '))
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
;
245 unsigned cols
, rows
, c
, r
;
249 READ_LINE (tl
, line
);
252 if (sscanf (line
, "s %*s %u %u %c %" GNM_SCANF_g
,
253 &rows
, &cols
, &pstat
, &val
) != 4)
256 if (sscanf (line
, "s %*s %u %u %c %c %" GNM_SCANF_g
,
257 &rows
, &cols
, &pstat
, &dstat
, &val
) != 5)
260 if (cols
!= g_hash_table_size (subsol
->cell_from_name
))
266 result
->quality
= GNM_SOLVER_RESULT_OPTIMAL
;
269 result
->quality
= GNM_SOLVER_RESULT_FEASIBLE
;
274 result
->quality
= GNM_SOLVER_RESULT_INFEASIBLE
;
280 for (r
= 0; r
< rows
; r
++) {
281 gnm_float pval
, dval
;
283 unsigned r1
, cidx
= r
;
285 READ_LINE (tl
, line
);
288 ? sscanf (line
, "i %d %" GNM_SCANF_g
,
290 : sscanf (line
, "i %d %c %" GNM_SCANF_g
" %" GNM_SCANF_g
,
291 &r1
, &rstat
, &pval
, &dval
) != 4) ||
296 sensitivity
->constraints
[cidx
].shadow_price
= dval
;
299 for (c
= 0; c
< cols
; c
++) {
300 gnm_float pval
, dval
;
302 unsigned c1
, cidx
= c
;
304 READ_LINE (tl
, line
);
307 ? sscanf (line
, "j %d %" GNM_SCANF_g
,
309 : sscanf (line
, "j %d %c %" GNM_SCANF_g
" %" GNM_SCANF_g
,
310 &c1
, &cstat
, &pval
, &dval
) != 4) ||
315 result
->solution
[cidx
] = pval
;
326 gnm_glpk_read_solution (GnmGlpk
*lp
)
328 GnmSubSolver
*subsol
= lp
->parent
;
329 GnmSolver
*sol
= GNM_SOLVER (subsol
);
331 GsfInputTextline
*tl
= NULL
;
333 GnmSolverResult
*result
= NULL
;
334 GnmSolverSensitivity
*sensitivity
= NULL
;
335 enum { SEC_UNKNOWN
, SEC_ROWS
, SEC_COLUMNS
} state
;
336 gboolean has_integer
;
339 input
= gsf_input_stdio_new (lp
->result_filename
, NULL
);
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
)) {
363 if (gnm_glpk_read_solution_457 (lp
, tl
, result
, sensitivity
,
368 if (gnm_glpk_read_solution_458 (lp
, tl
, result
, sensitivity
,
379 // ----------------------------------------
381 if (!lp
->ranges_filename
)
384 input
= gsf_input_stdio_new (lp
->ranges_filename
, NULL
);
387 tl
= GSF_INPUT_TEXTLINE (gsf_input_textline_new (input
));
388 g_object_unref (input
);
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
;
399 if (g_str_has_prefix (line
, " No. Row name")) {
402 } else if (g_str_has_prefix (line
, " No. Column name")) {
405 } else if (g_ascii_isalpha (line
[0])) {
410 if (state
== SEC_UNKNOWN
)
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
);
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
);
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]);
440 sensitivity
->constraints
[cidx
].low
= low
;
441 sensitivity
->constraints
[cidx
].high
= high
;
452 // ----------------------------------------
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
);
466 g_object_unref (result
);
468 g_object_unref (sensitivity
);
469 gnm_solver_set_status (sol
, GNM_SOLVER_STATUS_ERROR
);
474 gnm_glpk_child_exit (GnmSubSolver
*subsol
, gboolean normal
, int code
,
477 GnmSolver
*sol
= GNM_SOLVER (subsol
);
479 if (sol
->status
!= GNM_SOLVER_STATUS_RUNNING
)
485 GnmLocale
*locale
= gnm_push_C_locale ();
486 gnm_glpk_read_solution (lp
);
487 gnm_pop_C_locale (locale
);
495 if (sol
->status
== GNM_SOLVER_STATUS_RUNNING
)
496 gnm_solver_set_status (sol
, GNM_SOLVER_STATUS_ERROR
);
500 cb_child_setup (gpointer user
)
502 const char *lcvars
[] = {
511 for (ui
= 0; ui
< G_N_ELEMENTS (lcvars
); ui
++) {
512 const char *v
= lcvars
[ui
];
514 g_setenv (v
, "C", TRUE
);
519 gnm_glpk_prepare (GnmSolver
*sol
, WorkbookControl
*wbc
, GError
**err
,
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
);
532 fd
= g_file_open_tmp ("program-XXXXXX.out", &lp
->result_filename
, err
);
534 g_set_error (err
, G_FILE_ERROR
, 0,
535 _("Failed to create file for solution"));
540 if (sol
->params
->options
.sensitivity_report
) {
541 fd
= g_file_open_tmp ("program-XXXXXX.ran", &lp
->ranges_filename
, err
);
543 g_set_error (err
, G_FILE_ERROR
, 0,
544 _("Failed to create file for sensitivity report"));
550 gnm_solver_set_status (sol
, GNM_SOLVER_STATUS_PREPARED
);
555 gnm_glpk_cleanup (lp
);
556 gnm_solver_set_status (sol
, GNM_SOLVER_STATUS_ERROR
);
561 gnm_glpk_start (GnmSolver
*sol
, WorkbookControl
*wbc
, GError
**err
,
564 GnmSubSolver
*subsol
= GNM_SUB_SOLVER (sol
);
568 GnmSolverParameters
*param
= sol
->params
;
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
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
;
590 g_assert (argc
< (int)G_N_ELEMENTS (argv
));
592 ok
= gnm_sub_solver_spawn (subsol
, argv
,
593 cb_child_setup
, NULL
,
599 g_error_matches (*err
, G_SPAWN_ERROR
, G_SPAWN_ERROR_NOENT
)) {
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"),
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
);
625 glpk_solver_create (GnmSolverParameters
*params
)
627 GnmSolver
*res
= g_object_new (GNM_SUB_SOLVER_TYPE
,
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
);
646 glpk_solver_factory_functional (GnmSolverFactory
*factory
,
649 const char *full_path
= gnm_conf_get_plugin_glpk_glpsol_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
);
664 path
= gnm_sub_solver_locate_binary (SOLVER_PROGRAM
,
665 "Gnu Linear Programming Kit",
669 gnm_conf_set_plugin_glpk_glpsol_path (path
);
678 glpk_solver_factory (GnmSolverFactory
*factory
, GnmSolverParameters
*params
)
680 return glpk_solver_create (params
);