1 /*
2 * Copyright (C) 2009 Morten Welinder (terra@gnome.org)
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see <https://www.gnu.org/licenses/>.
16 */
17
18 #include <gnumeric-config.h>
19 #include <boot.h>
20 #include <numbers.h>
21 #include <workbook-view.h>
22 #include <sheet.h>
23 #include <workbook.h>
24 #include <application.h>
25 #include <value.h>
26 #include <cell.h>
27 #include <expr.h>
28 #include <tools/gnm-solver.h>
29 #include <ranges.h>
30 #include <parse-util.h>
31 #include <gutils.h>
32 #include <goffice/goffice.h>
33 #include <glib/gi18n-lib.h>
34
35 #include <string.h>
36
37
38 static const char *
glpk_var_name(GnmSubSolver * ssol,GnmCell const * cell)39 glpk_var_name (GnmSubSolver *ssol, GnmCell const *cell)
40 {
41 if (ssol)
42 return gnm_sub_solver_get_cell_name (ssol, cell);
43 return cell_name (cell);
44 }
45
46 static gboolean
glpk_affine_func(GString * dst,GnmCell * target,GnmSubSolver * ssol,gnm_float const * x1,gnm_float const * x2,gboolean zero_too,gnm_float cst,GError ** err)47 glpk_affine_func (GString *dst, GnmCell *target, GnmSubSolver *ssol,
48 gnm_float const *x1, gnm_float const *x2,
49 gboolean zero_too,
50 gnm_float cst, GError **err)
51 {
52 GnmSolver *sol = GNM_SOLVER (ssol);
53 unsigned ui;
54 gboolean any = FALSE;
55 gnm_float y;
56 gboolean ok = TRUE;
57 GPtrArray *input_cells = sol->input_cells;
58 gnm_float *cs;
59
60 if (!target) {
61 gnm_string_add_number (dst, cst);
62 return TRUE;
63 }
64
65 gnm_solver_set_vars (sol, x1);
66 gnm_cell_eval (target);
67 y = cst + value_get_as_float (target->value);
68
69 cs = gnm_solver_get_lp_coeffs (sol, target, x1, x2, err);
70 if (!cs)
71 goto fail;
72
73 /* Adjust constant for choice of x1. */
74 for (ui = 0; ui < input_cells->len; ui++)
75 y -= x1[ui] * cs[ui];
76
77 for (ui = 0; ui < input_cells->len; ui++) {
78 GnmCell *cell = g_ptr_array_index (input_cells, ui);
79 gnm_float x = cs[ui];
80 if (x == 0 && !zero_too)
81 continue;
82
83 if (any) {
84 if (x < 0)
85 g_string_append (dst, " - ");
86 else
87 g_string_append (dst, " + ");
88 } else {
89 if (x < 0)
90 g_string_append_c (dst, '-');
91 }
92 x = gnm_abs (x);
93
94 if (x != 1) {
95 gnm_string_add_number (dst, x);
96 g_string_append_c (dst, ' ');
97 }
98
99 g_string_append (dst, glpk_var_name (ssol, cell));
100
101 any = TRUE;
102 }
103
104 if (!any || y) {
105 if (any) {
106 g_string_append_c (dst, ' ');
107 if (y > 0)
108 g_string_append_c (dst, '+');
109 }
110 gnm_string_add_number (dst, y);
111 }
112
113 fail:
114 g_free (cs);
115
116 return ok;
117 }
118
119 static GString *
glpk_create_program(GnmSubSolver * ssol,GOIOContext * io_context,GError ** err)120 glpk_create_program (GnmSubSolver *ssol, GOIOContext *io_context, GError **err)
121 {
122 GnmSolver *sol = GNM_SOLVER (ssol);
123 GnmSolverParameters *sp = sol->params;
124 GString *prg = NULL;
125 GString *constraints = g_string_new (NULL);
126 GString *bounds = g_string_new (NULL);
127 GString *binaries = g_string_new (NULL);
128 GString *integers = g_string_new (NULL);
129 GString *objfunc = g_string_new (NULL);
130 GSList *l;
131 GnmCell *target_cell = gnm_solver_param_get_target_cell (sp);
132 GPtrArray *input_cells = sol->input_cells;
133 gsize progress;
134 GPtrArray *old = NULL;
135 gnm_float *x1 = NULL, *x2 = NULL;
136 int cidx = 0;
137
138 /* ---------------------------------------- */
139
140 if (sp->options.model_type != GNM_SOLVER_LP) {
141 g_set_error (err,
142 go_error_invalid (),
143 0,
144 _("Only linear programs are handled."));
145 goto fail;
146 }
147
148 /* ---------------------------------------- */
149
150 if (ssol) {
151 unsigned ui;
152
153 for (ui = 0; ui < input_cells->len; ui++) {
154 GnmCell *cell = g_ptr_array_index (input_cells, ui);
155 char *name = g_strdup_printf ("X_%u", ui + 1);
156 gnm_sub_solver_name_cell (ssol, cell, name);
157 g_free (name);
158 }
159 }
160
161 /* ---------------------------------------- */
162
163 progress = 3;
164 /* assume_non_negative */ progress++;
165 if (sp->options.assume_discrete) progress++;
166 progress += g_slist_length (sp->constraints);
167
168 go_io_count_progress_set (io_context, progress, 1);
169
170 /* ---------------------------------------- */
171
172 old = gnm_solver_save_vars (sol);
173
174 gnm_solver_pick_lp_coords (sol, &x1, &x2);
175 go_io_count_progress_update (io_context, 1);
176
177 /* ---------------------------------------- */
178
179 switch (sp->problem_type) {
180 case GNM_SOLVER_MINIMIZE:
181 g_string_append (objfunc, "Minimize\n");
182 break;
183 case GNM_SOLVER_MAXIMIZE:
184 g_string_append (objfunc, "Maximize\n");
185 break;
186 default:
187 g_assert_not_reached ();
188 }
189 go_io_count_progress_update (io_context, 1);
190
191 g_string_append (objfunc, " obj: ");
192 if (!glpk_affine_func (objfunc, target_cell, ssol, x1, x2,
193 TRUE, 0, err))
194 goto fail;
195 g_string_append (objfunc, "\n");
196 go_io_count_progress_update (io_context, 1);
197
198 /* ---------------------------------------- */
199
200 {
201 unsigned ui;
202 for (ui = 0; ui < input_cells->len; ui++) {
203 GnmCell *cell = g_ptr_array_index (input_cells, ui);
204 const char *name = glpk_var_name (ssol, cell);
205 if (sp->options.assume_non_negative)
206 g_string_append_printf (bounds, " %s >= 0\n", name);
207 else
208 g_string_append_printf (bounds, " %s free\n", name);
209 }
210 go_io_count_progress_update (io_context, 1);
211 }
212
213 if (sp->options.assume_discrete) {
214 unsigned ui;
215 for (ui = 0; ui < input_cells->len; ui++) {
216 GnmCell *cell = g_ptr_array_index (input_cells, ui);
217 g_string_append_printf (integers, " %s\n",
218 glpk_var_name (ssol, cell));
219 }
220 go_io_count_progress_update (io_context, 1);
221 }
222
223 for (l = sp->constraints; l; l = l->next) {
224 GnmSolverConstraint *c = l->data;
225 const char *op = NULL;
226 int i;
227 gnm_float cl, cr;
228 GnmCell *lhs, *rhs;
229 GString *type = NULL;
230
231 switch (c->type) {
232 case GNM_SOLVER_LE:
233 op = "<=";
234 break;
235 case GNM_SOLVER_GE:
236 op = ">=";
237 break;
238 case GNM_SOLVER_EQ:
239 op = "=";
240 break;
241 case GNM_SOLVER_INTEGER:
242 type = integers;
243 break;
244 case GNM_SOLVER_BOOLEAN:
245 type = binaries;
246 break;
247 default:
248 g_assert_not_reached ();
249 }
250
251 for (i = 0;
252 gnm_solver_constraint_get_part (c, sp, i,
253 &lhs, &cl,
254 &rhs, &cr);
255 i++, cidx++) {
256 if (type) {
257 g_string_append_printf
258 (type, " %s\n",
259 glpk_var_name (ssol, lhs));
260 } else {
261 gboolean ok;
262 char *name;
263
264 g_string_append_c (constraints, ' ');
265
266 name = g_strdup_printf ("C_%d", cidx);
267 gnm_sub_solver_name_constraint (ssol, cidx, name);
268 g_string_append (constraints, name);
269 g_string_append (constraints, ": ");
270 g_free (name);
271
272 ok = glpk_affine_func
273 (constraints, lhs, ssol,
274 x1, x2,
275 FALSE, cl, err);
276 if (!ok)
277 goto fail;
278
279 g_string_append_c (constraints, ' ');
280 g_string_append (constraints, op);
281 g_string_append_c (constraints, ' ');
282
283 ok = glpk_affine_func
284 (constraints, rhs, ssol,
285 x1, x2,
286 FALSE, cr, err);
287 if (!ok)
288 goto fail;
289
290 g_string_append (constraints, "\n");
291 }
292 }
293
294 go_io_count_progress_update (io_context, 1);
295 }
296
297 /* ---------------------------------------- */
298
299 prg = g_string_new (NULL);
300 g_string_append_printf (prg,
301 "\\ Created by Gnumeric %s\n\n",
302 GNM_VERSION_FULL);
303 go_string_append_gstring (prg, objfunc);
304
305 g_string_append (prg, "\nSubject to\n");
306 go_string_append_gstring (prg, constraints);
307
308 g_string_append (prg, "\nBounds\n");
309 go_string_append_gstring (prg, bounds);
310
311 if (integers->len > 0) {
312 g_string_append (prg, "\nGeneral\n");
313 go_string_append_gstring (prg, integers);
314 }
315 if (binaries->len > 0) {
316 g_string_append (prg, "\nBinary\n");
317 go_string_append_gstring (prg, binaries);
318 }
319 g_string_append (prg, "\nEnd\n");
320
321 fail:
322 g_string_free (objfunc, TRUE);
323 g_string_free (constraints, TRUE);
324 g_string_free (bounds, TRUE);
325 g_string_free (integers, TRUE);
326 g_string_free (binaries, TRUE);
327 g_free (x1);
328 g_free (x2);
329
330 if (old)
331 gnm_solver_restore_vars (sol, old);
332
333 return prg;
334 }
335
336 void
glpk_file_save(GOFileSaver const * fs,GOIOContext * io_context,WorkbookView const * wb_view,GsfOutput * output)337 glpk_file_save (GOFileSaver const *fs, GOIOContext *io_context,
338 WorkbookView const *wb_view, GsfOutput *output)
339 {
340 GError *err = NULL;
341 GString *prg;
342 GnmLocale *locale;
343 GnmSolver *sol = NULL;
344 GnmSubSolver *ssol = g_object_get_data (G_OBJECT (fs), "solver");
345
346 if (!ssol) {
347 // Create a temporary solver just functional enough to
348 // write the program
349 Sheet *sheet = wb_view_cur_sheet (wb_view);
350 sol = glpk_solver_create (sheet->solver_parameters);
351 ssol = GNM_SUB_SOLVER (sol);
352 }
353
354 go_io_progress_message (io_context,
355 _("Writing glpk file..."));
356
357 locale = gnm_push_C_locale ();
358 prg = glpk_create_program (ssol, io_context, &err);
359 gnm_pop_C_locale (locale);
360
361 gnm_app_recalc ();
362
363 if (!prg) {
364 go_cmd_context_error_import (GO_CMD_CONTEXT (io_context),
365 err ? err->message : "?");
366 goto fail;
367 }
368
369 gsf_output_write (output, prg->len, prg->str);
370 g_string_free (prg, TRUE);
371
372 fail:
373 go_io_progress_unset (io_context);
374 if (err)
375 g_error_free (err);
376
377 if (sol)
378 g_object_unref (sol);
379 }
380