[gnumeric] Solver: store result linearly.
- From: Morten Welinder <mortenw src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gnumeric] Solver: store result linearly.
- Date: Fri, 1 May 2015 22:44:32 +0000 (UTC)
commit 8ca2b54ef1c6363e256b1df423512edfb52fa798
Author: Morten Welinder <terra gnome org>
Date: Fri May 1 18:42:47 2015 -0400
Solver: store result linearly.
Just store results as arrays of gnm_float. This simplifies life
all over the place. (And, who knows, we might one day accept
input variables that are not simply a range.)
plugins/glpk/gnm-glpk.c | 16 +---
plugins/lpsolve/gnm-lpsolve.c | 27 ++----
plugins/nlsolve/gnm-nlsolve.c | 2 +-
src/tools/gnm-solver.c | 188 +++++++++++++++++------------------------
src/tools/gnm-solver.h | 7 +-
5 files changed, 97 insertions(+), 143 deletions(-)
---
diff --git a/plugins/glpk/gnm-glpk.c b/plugins/glpk/gnm-glpk.c
index 0fa13d1..ff5bd53 100644
--- a/plugins/glpk/gnm-glpk.c
+++ b/plugins/glpk/gnm-glpk.c
@@ -22,7 +22,6 @@
typedef struct {
GnmSubSolver *parent;
char *result_filename;
- GnmSheetRange srinput;
} GnmGlpk;
static void
@@ -74,7 +73,6 @@ gnm_glpk_read_solution (GnmGlpk *lp)
int pstat, dstat;
gnm_float val;
GnmSolverResult *result;
- int width, height;
gboolean has_integer;
GSList *l;
@@ -96,10 +94,8 @@ gnm_glpk_read_solution (GnmGlpk *lp)
tl = GSF_INPUT_TEXTLINE (gsf_input_textline_new (input));
g_object_unref (input);
- width = range_width (&lp->srinput.range);
- height = range_height (&lp->srinput.range);
result = g_object_new (GNM_SOLVER_RESULT_TYPE, NULL);
- result->solution = value_new_array_empty (width, height);
+ result->solution = g_new0 (gnm_float, sol->input_cells->len);
if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
goto fail;
@@ -142,7 +138,7 @@ gnm_glpk_read_solution (GnmGlpk *lp)
for (c = 0; c < cols; c++) {
gnm_float pval, dval;
unsigned cstat;
- int x, y;
+ unsigned idx = c;
if ((line = gsf_input_textline_utf8_gets (tl)) == NULL)
goto fail;
@@ -153,10 +149,7 @@ gnm_glpk_read_solution (GnmGlpk *lp)
&cstat, &pval, &dval) != 3)
goto fail;
- x = c % width;
- y = c / width;
- value_array_set (result->solution, x, y,
- value_new_float (pval));
+ result->solution[idx] = pval;
}
gnm_solver_set_status (sol, GNM_SOLVER_STATUS_DONE);
@@ -360,9 +353,6 @@ glpk_solver_factory (GnmSolverFactory *factory, GnmSolverParameters *params)
GnmGlpk *lp = g_new0 (GnmGlpk, 1);
lp->parent = GNM_SUB_SOLVER (res);
- gnm_sheet_range_from_value (&lp->srinput,
- gnm_solver_param_get_input (params));
- if (!lp->srinput.sheet) lp->srinput.sheet = params->sheet;
g_signal_connect (res, "prepare", G_CALLBACK (gnm_glpk_prepare), lp);
g_signal_connect (res, "start", G_CALLBACK (gnm_glpk_start), lp);
diff --git a/plugins/lpsolve/gnm-lpsolve.c b/plugins/lpsolve/gnm-lpsolve.c
index 4e9150e..16f45e8 100644
--- a/plugins/lpsolve/gnm-lpsolve.c
+++ b/plugins/lpsolve/gnm-lpsolve.c
@@ -17,7 +17,6 @@
typedef struct {
GnmSubSolver *parent;
GnmSolverResult *result;
- GnmSheetRange srinput;
enum { SEC_UNKNOWN, SEC_VALUES } section;
} GnmLPSolve;
@@ -61,12 +60,14 @@ write_program (GnmSolver *sol, WorkbookControl *wbc, GError **err)
static GnmSolverResult *
gnm_lpsolve_start_solution (GnmLPSolve *lp)
{
+ int n;
+
g_return_val_if_fail (lp->result == NULL, NULL);
+ n = GNM_SOLVER (lp->parent)->input_cells->len;
+
lp->result = g_object_new (GNM_SOLVER_RESULT_TYPE, NULL);
- lp->result->solution = value_new_array_empty
- (range_width (&lp->srinput.range),
- range_height (&lp->srinput.range));
+ lp->result->solution = g_new0 (gnm_float, n);
return lp->result;
}
@@ -85,6 +86,7 @@ gnm_lpsolve_flush_solution (GnmLPSolve *lp)
static gboolean
cb_read_stdout (GIOChannel *channel, GIOCondition cond, GnmLPSolve *lp)
{
+ GnmSolver *sol = GNM_SOLVER (lp->parent);
const char obj_line_prefix[] = "Value of objective function:";
size_t obj_line_len = sizeof (obj_line_prefix) - 1;
const char val_header_line[] = "Actual values of the variables:";
@@ -117,10 +119,10 @@ cb_read_stdout (GIOChannel *channel, GIOCondition cond, GnmLPSolve *lp)
lp->section = SEC_VALUES;
} else if (lp->section == SEC_VALUES && lp->result) {
GnmSolverResult *r = lp->result;
- int x, y;
double v;
char *space = strchr (line, ' ');
GnmCell *cell;
+ int idx;
if (!space) {
lp->section = SEC_UNKNOWN;
@@ -128,7 +130,8 @@ cb_read_stdout (GIOChannel *channel, GIOCondition cond, GnmLPSolve *lp)
}
*space = 0;
cell = gnm_sub_solver_find_cell (lp->parent, line);
- if (!cell) {
+ idx = gnm_solver_cell_index (sol, cell);
+ if (idx < 0) {
g_printerr ("Strange cell %s in output\n",
line);
lp->section = SEC_UNKNOWN;
@@ -136,14 +139,7 @@ cb_read_stdout (GIOChannel *channel, GIOCondition cond, GnmLPSolve *lp)
}
v = g_ascii_strtod (space + 1, NULL);
- x = cell->pos.col - lp->srinput.range.start.col;
- y = cell->pos.row - lp->srinput.range.start.row;
- if (x >= 0 &&
- x < value_area_get_width (r->solution, NULL) &&
- y >= 0 &&
- y < value_area_get_height (r->solution, NULL))
- value_array_set (r->solution, x, y,
- value_new_float (v));
+ r->solution[idx] = v;
}
g_free (line);
} while (1);
@@ -354,9 +350,6 @@ lpsolve_solver_factory (GnmSolverFactory *factory, GnmSolverParameters *params)
GnmLPSolve *lp = g_new0 (GnmLPSolve, 1);
lp->parent = GNM_SUB_SOLVER (res);
- gnm_sheet_range_from_value (&lp->srinput,
- gnm_solver_param_get_input (params));
- if (!lp->srinput.sheet) lp->srinput.sheet = params->sheet;
g_signal_connect (res, "prepare", G_CALLBACK (gnm_lpsolve_prepare), lp);
g_signal_connect (res, "start", G_CALLBACK (gnm_lpsolve_start), lp);
diff --git a/plugins/nlsolve/gnm-nlsolve.c b/plugins/nlsolve/gnm-nlsolve.c
index ee05b6d..55d55dd 100644
--- a/plugins/nlsolve/gnm-nlsolve.c
+++ b/plugins/nlsolve/gnm-nlsolve.c
@@ -465,7 +465,7 @@ rosenbrock_iter (GnmNlsolve *nl)
nl->smallsteps++;
}
- if (!nl->tentative && nl->smallsteps > 50) {
+ if (0 && !nl->tentative && nl->smallsteps > 50) {
gnm_float yk = isol->yk;
nl->tentative = 10;
diff --git a/src/tools/gnm-solver.c b/src/tools/gnm-solver.c
index 779c70a..26bd3d0 100644
--- a/src/tools/gnm-solver.c
+++ b/src/tools/gnm-solver.c
@@ -818,6 +818,11 @@ gnm_solver_dispose (GObject *obj)
sol->input_cells = NULL;
}
+ if (sol->index_from_cell) {
+ g_hash_table_destroy (sol->index_from_cell);
+ sol->index_from_cell = NULL;
+ }
+
gnm_solver_parent_class->dispose (obj);
}
@@ -826,21 +831,15 @@ gnm_solver_constructed (GObject *obj)
{
GnmSolver *sol = GNM_SOLVER (obj);
GnmSolverParameters *params = sol->params;
- GnmValue const *vinput = gnm_solver_param_get_input (params);
+ unsigned ui;
sol->target = gnm_solver_param_get_target_cell (params);
sol->input_cells = gnm_solver_param_get_input_cells (params);
- if (vinput) {
- GnmCellRef origin;
- GnmEvalPos ep;
-
- eval_pos_init_sheet (&ep, params->sheet);
- gnm_cellref_make_abs (&origin, &vinput->v_range.cell.a, &ep);
- sol->origin.col = origin.col;
- sol->origin.row = origin.row;
- sol->input_width = value_area_get_width (vinput, &ep);
- sol->input_height = value_area_get_height (vinput, &ep);
+ sol->index_from_cell = g_hash_table_new (g_direct_hash, g_direct_equal);
+ for (ui = 0; ui < sol->input_cells->len; ui++) {
+ GnmCell *cell = g_ptr_array_index (sol->input_cells, ui);
+ g_hash_table_insert (sol->index_from_cell, cell, GUINT_TO_POINTER (ui));
}
gnm_solver_parent_class->constructed (obj);
@@ -1055,30 +1054,20 @@ gnm_solver_check_timeout (GnmSolver *solver)
void
gnm_solver_store_result (GnmSolver *sol)
{
- GnmValue const *vinput;
- GnmSheetRange sr;
- GnmValue const *solution;
+ gnm_float const *solution;
unsigned ui, n = sol->input_cells->len;
g_return_if_fail (GNM_IS_SOLVER (sol));
g_return_if_fail (sol->result != NULL);
g_return_if_fail (sol->result->solution);
- vinput = gnm_solver_param_get_input (sol->params);
- gnm_sheet_range_from_value (&sr, vinput);
- if (!sr.sheet) sr.sheet = sol->params->sheet;
-
solution = gnm_solver_has_solution (sol)
? sol->result->solution
: NULL;
for (ui = 0; ui < n; ui++) {
GnmCell *cell = g_ptr_array_index (sol->input_cells, ui);
- int x = cell->pos.col - sol->origin.col;
- int y = cell->pos.row - sol->origin.row;
- GnmValue *v = solution
- ? value_dup (value_area_fetch_x_y (solution, x, y, NULL))
- : value_new_error_NA (NULL);
+ GnmValue *v = solution ? value_new_float (solution[ui]) : value_new_error_NA (NULL);
gnm_cell_set_value (cell, v);
cell_queue_recalc (cell);
}
@@ -1302,15 +1291,29 @@ gnm_solver_saveas (GnmSolver *solver, WorkbookControl *wbc,
return TRUE;
}
-static gboolean
-cell_in_cr (GnmCell const *cell, GnmSheetRange *sr, gboolean follow,
- int *px, int *py)
+int
+gnm_solver_cell_index (GnmSolver *solver, GnmCell const *cell)
+{
+ gpointer idx;
+
+ if (g_hash_table_lookup_extended (solver->index_from_cell,
+ (gpointer)cell,
+ NULL, &idx))
+ return GPOINTER_TO_INT (idx);
+ else
+ return -1;
+}
+
+static int
+cell_in_cr (GnmSolver *sol, GnmCell const *cell, gboolean follow)
{
+ int idx;
+
if (!cell)
- return FALSE;
+ return -1;
- if (sr->sheet != cell->base.sheet ||
- !range_contains (&sr->range, cell->pos.col, cell->pos.row)) {
+ idx = gnm_solver_cell_index (sol, cell);
+ if (idx < 0 && follow) {
/* If the expression is just =X42 then look at X42 instead.
This is because the mps loader uses such a level of
indirection. Note: we follow only one such step. */
@@ -1320,19 +1323,16 @@ cell_in_cr (GnmCell const *cell, GnmSheetRange *sr, gboolean follow,
GnmEvalPos ep;
if (!cr)
- return FALSE;
+ return -1;
eval_pos_init_cell (&ep, cell);
gnm_cellref_make_abs (&cr2, cr, &ep);
new_cell = sheet_cell_get (eval_sheet (cr2.sheet, cell->base.sheet),
cr2.col, cr2.row);
- return cell_in_cr (new_cell, sr, FALSE, px, py);
-
+ return cell_in_cr (sol, new_cell, FALSE);
}
- *px = cell->pos.col - sr->range.start.col;
- *py = cell->pos.row - sr->range.start.row;
- return TRUE;
+ return idx;
}
static gboolean
@@ -1350,14 +1350,14 @@ cell_is_constant (GnmCell *cell, gnm_float *pc)
}
#define SET_LOWER(l_) \
- do { \
- (*pmin)[y * w + x] = MAX ((*pmin)[y * w + x], (l_)); \
- } while (0)
+ do { \
+ (*pmin)[idx] = MAX ((*pmin)[idx], (l_)); \
+ } while (0)
#define SET_UPPER(l_) \
- do { \
- (*pmax)[y * w + x] = MIN ((*pmax)[y * w + x], (l_)); \
- } while (0)
+ do { \
+ (*pmax)[idx] = MIN ((*pmax)[idx], (l_)); \
+ } while (0)
@@ -1366,28 +1366,20 @@ gnm_solver_get_limits (GnmSolver *solver, gnm_float **pmin, gnm_float **pmax)
{
GnmValue const *vinput;
GnmSolverParameters *params = solver->params;
- int x, y, w, h;
- GnmSheetRange sr;
GSList *l;
+ unsigned const n = solver->input_cells->len;
+ unsigned ui;
*pmin = *pmax = NULL;
vinput = gnm_solver_param_get_input (params);
if (!vinput) return;
- gnm_sheet_range_from_value (&sr, vinput);
- if (!sr.sheet) sr.sheet = params->sheet;
- h = range_height (&sr.range);
- w = range_width (&sr.range);
-
- *pmin = g_new (gnm_float, h * w);
- *pmax = g_new (gnm_float, h * w);
-
- for (x = 0; x < w; x++) {
- for (y = 0; y < h; y++) {
- (*pmin)[y * w + x] = params->options.assume_non_negative ? 0 : gnm_ninf;
- (*pmax)[y * w + x] = gnm_pinf;
- }
+ *pmin = g_new (gnm_float, n);
+ *pmax = g_new (gnm_float, n);
+ for (ui = 0; ui < n; ui++) {
+ (*pmin)[ui] = params->options.assume_non_negative ? 0 : gnm_ninf;
+ (*pmax)[ui] = gnm_pinf;
}
for (l = params->constraints; l; l = l->next) {
@@ -1401,7 +1393,9 @@ gnm_solver_get_limits (GnmSolver *solver, gnm_float **pmin, gnm_float **pmax)
&lhs, &cl,
&rhs, &cr);
i++) {
- if (!cell_in_cr (lhs, &sr, TRUE, &x, &y))
+ int idx = cell_in_cr (solver, lhs, TRUE);
+
+ if (idx < 0)
continue;
if (!cell_is_constant (rhs, &cr))
continue;
@@ -1430,7 +1424,6 @@ gnm_solver_get_limits (GnmSolver *solver, gnm_float **pmin, gnm_float **pmax)
}
}
}
-
}
#undef SET_LOWER
@@ -1528,9 +1521,8 @@ gnm_solver_create_report (GnmSolver *solver, const char *name)
vinput = gnm_solver_param_get_input (params);
if (vinput) {
- int x, y, w, h;
- GnmSheetRange sr;
gnm_float *pmin, *pmax;
+ unsigned ui;
ADD_HEADER (_("Variables"));
@@ -1541,47 +1533,35 @@ gnm_solver_create_report (GnmSolver *solver, const char *name)
dao_set_cell (dao, 5, R, _("Slack"));
R++;
- gnm_sheet_range_from_value (&sr, vinput);
- if (!sr.sheet) sr.sheet = params->sheet;
- h = range_height (&sr.range);
- w = range_width (&sr.range);
-
gnm_solver_get_limits (solver, &pmin, &pmax);
- for (x = 0; x < w; x++) {
- for (y = 0; y < h; y++) {
- GnmCell *cell = sheet_cell_fetch
- (sr.sheet,
- sr.range.start.col + x,
- sr.range.start.row + y);
- gnm_float m = pmin[y * w + x];
- gnm_float M = pmax[y * w + x];
- GnmValue const *vs = value_area_fetch_x_y (solver->result->solution, x, y,
NULL);
- gnm_float s = value_get_as_float (vs);
- gnm_float slack = MIN (s - m, M - s);
-
- char *cname = gnm_solver_cell_name (cell, params->sheet);
- dao_set_cell (dao, 1, R, cname);
- g_free (cname);
- dao_set_cell_value (dao, 2, R, value_dup (vs));
- add_value_or_special (dao, 3, R, m);
- add_value_or_special (dao, 4, R, M);
-
- add_value_or_special (dao, 5, R, slack);
- if (slack < 0)
- MARK_BAD (5);
-
- if (AT_LIMIT (s, m) || AT_LIMIT (s, M))
- dao_set_cell (dao, 6, R, _("At limit"));
-
-
- if (s < m || s > M) {
- dao_set_cell (dao, 7, R, _("Outside bounds"));
- MARK_BAD (7);
- }
+ for (ui = 0; ui < solver->input_cells->len; ui++) {
+ GnmCell *cell = g_ptr_array_index (solver->input_cells, ui);
+ gnm_float m = pmin[ui];
+ gnm_float M = pmax[ui];
+ gnm_float s = solver->result->solution[ui];
+ gnm_float slack = MIN (s - m, M - s);
+
+ char *cname = gnm_solver_cell_name (cell, params->sheet);
+ dao_set_cell (dao, 1, R, cname);
+ g_free (cname);
+ dao_set_cell_value (dao, 2, R, value_new_float (s));
+ add_value_or_special (dao, 3, R, m);
+ add_value_or_special (dao, 4, R, M);
- R++;
+ add_value_or_special (dao, 5, R, slack);
+ if (slack < 0)
+ MARK_BAD (5);
+
+ if (AT_LIMIT (s, m) || AT_LIMIT (s, M))
+ dao_set_cell (dao, 6, R, _("At limit"));
+
+ if (s < m || s > M) {
+ dao_set_cell (dao, 7, R, _("Outside bounds"));
+ MARK_BAD (7);
}
+
+ R++;
}
g_free (pmin);
@@ -1875,7 +1855,7 @@ static void
gnm_solver_result_finalize (GObject *obj)
{
GnmSolverResult *r = GNM_SOLVER_RESULT (obj);
- value_release (r->solution);
+ g_free (r->solution);
gnm_solver_result_parent_class->finalize (obj);
}
@@ -2587,20 +2567,10 @@ gnm_iter_solver_set_solution (GnmIterSolver *isol)
GnmSolver *sol = GNM_SOLVER (isol);
GnmSolverResult *result = g_object_new (GNM_SOLVER_RESULT_TYPE, NULL);
const int n = sol->input_cells->len;
- int i;
result->quality = GNM_SOLVER_RESULT_FEASIBLE;
result->value = sol->flip_sign ? 0 - isol->yk : isol->yk;
- result->solution = value_new_array_empty (sol->input_width,
- sol->input_height);
- for (i = 0; i < n; i++) {
- GnmCell *cell = g_ptr_array_index (sol->input_cells, i);
- value_array_set (result->solution,
- cell->pos.col - sol->origin.col,
- cell->pos.row - sol->origin.row,
- value_new_float (isol->xk[i]));
- }
-
+ result->solution = g_memdup (isol->xk, n * sizeof (gnm_float));
g_object_set (sol, "result", result, NULL);
g_object_unref (result);
diff --git a/src/tools/gnm-solver.h b/src/tools/gnm-solver.h
index 564f693..50be250 100644
--- a/src/tools/gnm-solver.h
+++ b/src/tools/gnm-solver.h
@@ -175,7 +175,7 @@ typedef struct {
gnm_float value;
/* Array value of solution, if any */
- GnmValue *solution;
+ gnm_float *solution;
} GnmSolverResult;
typedef struct {
@@ -205,8 +205,7 @@ typedef struct {
/* Derived information */
GnmCell *target;
GPtrArray *input_cells;
- GnmCellPos origin;
- int input_width, input_height;
+ GHashTable *index_from_cell;
} GnmSolver;
typedef struct {
@@ -252,6 +251,8 @@ gboolean gnm_solver_saveas (GnmSolver *solver, WorkbookControl *wbc,
gboolean gnm_solver_debug (void);
+int gnm_solver_cell_index (GnmSolver *solver, GnmCell const *cell);
+
gnm_float gnm_solver_get_target_value (GnmSolver *solver);
void gnm_solver_set_var (GnmSolver *sol, int i, gnm_float x);
void gnm_solver_set_vars (GnmSolver *sol, gnm_float const *xs);
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
