[gnumeric] Solver: code cleanup.
- From: Morten Welinder <mortenw src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gnumeric] Solver: code cleanup.
- Date: Mon, 27 Apr 2015 02:57:06 +0000 (UTC)
commit edd097dccbbaebce458d22c398ffd5e83d6ace3b
Author: Morten Welinder <terra gnome org>
Date: Sun Apr 26 22:55:54 2015 -0400
Solver: code cleanup.
This creates object types for solver iterations and moves more
generic iterative stuff into GnmIterSolver.
NEWS | 1 +
plugins/nlsolve/gnm-nlsolve.c | 281 ++++++++++++---------------------
src/tools/gnm-solver.c | 347 +++++++++++++++++++++++++++++++++++++----
src/tools/gnm-solver.h | 80 +++++++++-
4 files changed, 495 insertions(+), 214 deletions(-)
---
diff --git a/NEWS b/NEWS
index 5a69b7e..006b596 100644
--- a/NEWS
+++ b/NEWS
@@ -8,6 +8,7 @@ Morten:
* Fix export of unlabelled axes.
* Fix export of rotated axis labels.
* Fix xlsx save crash related to shared strings. [#748477]
+ * Solver code refactoring.
--------------------------------------------------------------------------
Gnumeric 1.12.22
diff --git a/plugins/nlsolve/gnm-nlsolve.c b/plugins/nlsolve/gnm-nlsolve.c
index 97ba2fc..4d7d0b6 100644
--- a/plugins/nlsolve/gnm-nlsolve.c
+++ b/plugins/nlsolve/gnm-nlsolve.c
@@ -35,24 +35,17 @@
/*
* Note: the solver code assumes the problem is a minimization problem.
* When used for a maximization problem, we flip the objective function
- * sign. This is done in functions get_value and gnm_nlsolve_set_solution.
+ * sign.
*/
typedef struct {
- GnmIterSolver *parent;
+ /* The solver object in two forms. */
+ GnmSolver *sol;
+ GnmIterSolver *isol;
- /* Input/output cells. */
- GPtrArray *vars;
- GnmCellPos origin;
- int input_width, input_height;
- gboolean maximize; /* See note above */
-
- /* Initial point. */
- gnm_float *x0;
-
- /* Current point. */
- gnm_float *xk, yk;
+ /* Number of vars. */
+ int n;
/* Rosenbrock state */
gnm_float **xi;
@@ -65,26 +58,6 @@ typedef struct {
gnm_float min_factor;
} GnmNlsolve;
-static void free_matrix (gnm_float **m, int n);
-static void rosenbrock_tentative_end (GnmNlsolve *nl, gboolean accept);
-
-static void
-gnm_nlsolve_final (GnmNlsolve *nl)
-{
- const int n = nl->vars->len;
-
- rosenbrock_tentative_end (nl, FALSE);
-
- g_free (nl->xk);
- g_free (nl->x0);
- if (nl->xi) {
- free_matrix (nl->xi, n);
- nl->xi = NULL;
- }
-
- g_free (nl);
-}
-
static gboolean
check_program (const GnmSolverParameters *params, GError **err)
{
@@ -125,32 +98,21 @@ print_vector (const char *name, const gnm_float *v, int n)
static void
set_value (GnmNlsolve *nl, int i, gnm_float x)
{
- GnmCell *cell = g_ptr_array_index (nl->vars, i);
- if (cell->value &&
- VALUE_IS_FLOAT (cell->value) &&
- value_get_as_float (cell->value) == x)
- return;
-
- gnm_cell_set_value (cell, value_new_float (x));
- cell_queue_recalc (cell);
+ gnm_solver_set_var (nl->sol, i, x);
}
static void
set_vector (GnmNlsolve *nl, const gnm_float *xs)
{
- const int n = nl->vars->len;
- int i;
-
- for (i = 0; i < n; i++)
- set_value (nl, i, xs[i]);
+ gnm_solver_set_vars (nl->sol, xs);
}
/* Get the target value as-if we were minimizing. */
static gnm_float
get_value (GnmNlsolve *nl)
{
- gnm_float y = gnm_solver_get_target_value (GNM_SOLVER (nl->parent));
- return nl->maximize ? 0 - y : y;
+ /* nl->isol has been taught to flip sign if needed. */
+ return gnm_iter_solver_get_target_value (nl->isol);
}
static void
@@ -163,60 +125,10 @@ free_matrix (gnm_float **m, int n)
}
static void
-gnm_nlsolve_set_solution (GnmNlsolve *nl)
+set_solution (GnmNlsolve *nl)
{
- GnmSolver *sol = GNM_SOLVER (nl->parent);
- GnmSolverResult *result = g_object_new (GNM_SOLVER_RESULT_TYPE, NULL);
- const int n = nl->vars->len;
- int i;
-
- result->quality = GNM_SOLVER_RESULT_FEASIBLE;
- result->value = nl->maximize ? 0 - nl->yk : nl->yk;
- result->solution = value_new_array_empty (nl->input_width,
- nl->input_height);
- for (i = 0; i < n; i++) {
- GnmCell *cell = g_ptr_array_index (nl->vars, i);
- value_array_set (result->solution,
- cell->pos.col - nl->origin.col,
- cell->pos.row - nl->origin.row,
- value_new_float (nl->xk[i]));
- }
-
- g_object_set (sol, "result", result, NULL);
- g_object_unref (result);
-
- if (!gnm_solver_check_constraints (sol)) {
- g_printerr ("Infeasible solution set\n");
- }
-}
-
-static gboolean
-gnm_nlsolve_get_initial_solution (GnmNlsolve *nl, GError **err)
-{
- GnmSolver *sol = GNM_SOLVER (nl->parent);
- const int n = nl->vars->len;
- int i;
-
- if (gnm_solver_check_constraints (sol))
- goto got_it;
-
- /* More? */
-
- g_set_error (err,
- go_error_invalid (),
- 0,
- _("The initial values do not satisfy the constraints."));
- return FALSE;
-
-got_it:
- for (i = 0; i < n; i++) {
- GnmCell *cell = g_ptr_array_index (nl->vars, i);
- nl->xk[i] = nl->x0[i] = value_get_as_float (cell->value);
- }
- nl->yk = get_value (nl);
- gnm_nlsolve_set_solution (nl);
-
- return TRUE;
+ /* nl->isol has been taught to flip sign if needed. */
+ gnm_iter_solver_set_solution (nl->isol);
}
static gboolean
@@ -231,7 +143,7 @@ gnm_nlsolve_prepare (GnmSolver *sol, WorkbookControl *wbc, GError **err,
ok = check_program (sol->params, err);
if (ok)
- ok = gnm_nlsolve_get_initial_solution (nl, err);
+ ok = gnm_iter_solver_get_initial_solution (nl->isol, err);
if (ok) {
gnm_solver_set_status (sol, GNM_SOLVER_STATUS_PREPARED);
@@ -247,7 +159,7 @@ compute_gradient (GnmNlsolve *nl, const gnm_float *xs)
{
gnm_float *g;
gnm_float y0;
- const int n = nl->vars->len;
+ const int n = nl->n;
int i;
set_vector (nl, xs);
@@ -279,7 +191,7 @@ static gnm_float **
compute_hessian (GnmNlsolve *nl, const gnm_float *xs, const gnm_float *g0)
{
gnm_float **H, *xs2;
- const int n = nl->vars->len;
+ const int n = nl->n;
int i, j;
H = g_new (gnm_float *, n);
@@ -321,8 +233,8 @@ compute_hessian (GnmNlsolve *nl, const gnm_float *xs, const gnm_float *g0)
static gboolean
newton_improve (GnmNlsolve *nl, gnm_float *xs, gnm_float *y, gnm_float ymax)
{
- GnmSolver *sol = GNM_SOLVER (nl->parent);
- const int n = nl->vars->len;
+ GnmSolver *sol = nl->sol;
+ const int n = nl->n;
gnm_float *g, **H, *d;
gboolean ok;
@@ -379,7 +291,7 @@ newton_improve (GnmNlsolve *nl, gnm_float *xs, gnm_float *y, gnm_float ymax)
static void
rosenbrock_init (GnmNlsolve *nl)
{
- const int n = nl->vars->len;
+ const int n = nl->n;
int i, j;
nl->xi = g_new (gnm_float *, n);
@@ -398,11 +310,12 @@ rosenbrock_init (GnmNlsolve *nl)
static void
rosenbrock_tentative_end (GnmNlsolve *nl, gboolean accept)
{
- const int n = nl->vars->len;
+ const int n = nl->n;
+ GnmIterSolver *isol = nl->isol;
if (!accept && nl->tentative_xk) {
- nl->yk = nl->tentative_yk;
- memcpy (nl->xk, nl->tentative_xk, n * sizeof (gnm_float));
+ nl->isol->yk = nl->tentative_yk;
+ memcpy (isol->xk, nl->tentative_xk, n * sizeof (gnm_float));
}
nl->tentative = 0;
@@ -415,9 +328,9 @@ rosenbrock_tentative_end (GnmNlsolve *nl, gboolean accept)
static gboolean
rosenbrock_iter (GnmNlsolve *nl)
{
- GnmSolver *sol = GNM_SOLVER (nl->parent);
- GnmIterSolver *isol = GNM_ITER_SOLVER (sol);
- const int n = nl->vars->len;
+ GnmSolver *sol = nl->sol;
+ GnmIterSolver *isol = nl->isol;
+ const int n = nl->n;
int i, j;
const gnm_float alpha = 3;
const gnm_float beta = 0.5;
@@ -425,7 +338,7 @@ rosenbrock_iter (GnmNlsolve *nl)
gnm_float *d, **A, *x, *dx, *t;
char *state;
int dones = 0;
- gnm_float ykm1 = nl->yk, *xkm1;
+ gnm_float ykm1 = isol->yk, *xkm1;
gnm_float eps = gnm_pow2 (-16);
int safety = 0;
@@ -457,12 +370,12 @@ rosenbrock_iter (GnmNlsolve *nl)
d = g_new (gnm_float, n);
for (i = 0; i < n; i++) {
- d[i] = (nl->xk[i] == 0)
+ d[i] = (isol->xk[i] == 0)
? eps
- : gnm_abs (nl->xk[i]) * eps;
+ : gnm_abs (isol->xk[i]) * eps;
}
- xkm1 = g_memdup (nl->xk, n * sizeof (gnm_float));
+ xkm1 = g_memdup (isol->xk, n * sizeof (gnm_float));
state = g_new0 (char, n);
@@ -482,15 +395,15 @@ rosenbrock_iter (GnmNlsolve *nl)
/* x = xk + (d[i] * xi[i]) */
for (j = 0; j < n; j++)
- x[j] = nl->xk[j] + d[i] * nl->xi[i][j];
+ x[j] = isol->xk[j] + d[i] * nl->xi[i][j];
set_vector (nl, x);
y = get_value (nl);
- if (y <= nl->yk && gnm_solver_check_constraints (sol)) {
- if (y < nl->yk) {
- nl->yk = y;
- memcpy (nl->xk, x, n * sizeof (gnm_float));
+ if (y <= isol->yk && gnm_solver_check_constraints (sol)) {
+ if (y < isol->yk) {
+ isol->yk = y;
+ memcpy (isol->xk, x, n * sizeof (gnm_float));
dx[i] += d[i];
any_at_all = TRUE;
}
@@ -562,17 +475,17 @@ rosenbrock_iter (GnmNlsolve *nl)
/* ---------------------------------------- */
if (!nl->tentative) {
- set_vector (nl, nl->xk);
- gnm_nlsolve_set_solution (nl);
+ set_vector (nl, isol->xk);
+ set_solution (nl);
}
if (nl->tentative) {
- if (nl->yk < nl->tentative_yk) {
+ if (isol->yk < nl->tentative_yk) {
if (nl->debug)
g_printerr ("Tentative move accepted!\n");
rosenbrock_tentative_end (nl, TRUE);
}
- } else if (gnm_abs (nl->yk - ykm1) > gnm_abs (ykm1) * 0.01) {
+ } else if (gnm_abs (isol->yk - ykm1) > gnm_abs (ykm1) * 0.01) {
/* A big step. */
nl->smallsteps = 0;
} else {
@@ -580,23 +493,23 @@ rosenbrock_iter (GnmNlsolve *nl)
}
if (!nl->tentative && nl->smallsteps > 50) {
- gnm_float yk = nl->yk;
+ gnm_float yk = isol->yk;
nl->tentative = 10;
- nl->tentative_xk = g_memdup (nl->xk, n * sizeof (gnm_float));
+ nl->tentative_xk = g_memdup (isol->xk, n * sizeof (gnm_float));
nl->tentative_yk = yk;
for (i = 0; i < 4; i++) {
gnm_float ymax = yk +
gnm_abs (yk) * (0.10 / (i + 1));
if (i > 0)
- ymax = MIN (ymax, nl->yk);
- if (!newton_improve (nl, nl->xk, &nl->yk, ymax))
+ ymax = MIN (ymax, isol->yk);
+ if (!newton_improve (nl, isol->xk, &isol->yk, ymax))
break;
}
if (nl->debug)
- print_vector ("Tentative move to", nl->xk, n);
+ print_vector ("Tentative move to", isol->xk, n);
}
}
@@ -614,8 +527,9 @@ rosenbrock_iter (GnmNlsolve *nl)
static gboolean
polish_iter (GnmNlsolve *nl)
{
- GnmSolver *sol = GNM_SOLVER (nl->parent);
- const int n = nl->vars->len;
+ GnmSolver *sol = nl->sol;
+ GnmIterSolver *isol = nl->isol;
+ const int n = nl->n;
gnm_float *x;
gnm_float step;
gboolean any_at_all = FALSE;
@@ -627,19 +541,19 @@ polish_iter (GnmNlsolve *nl)
for (c = 0; c < n; c++) {
for (s = 0; s <= 1; s++) {
gnm_float y;
- gnm_float dx = step * gnm_abs (nl->xk[c]);
+ gnm_float dx = step * gnm_abs (isol->xk[c]);
if (dx == 0) dx = step;
if (s) dx = -dx;
- memcpy (x, nl->xk, n * sizeof (gnm_float));
+ memcpy (x, isol->xk, n * sizeof (gnm_float));
x[c] += dx;
set_vector (nl, x);
y = get_value (nl);
- if (y < nl->yk && gnm_solver_check_constraints (sol)) {
- nl->yk = y;
- memcpy (nl->xk, x, n * sizeof (gnm_float));
+ if (y < isol->yk && gnm_solver_check_constraints (sol)) {
+ isol->yk = y;
+ memcpy (isol->xk, x, n * sizeof (gnm_float));
any_at_all = TRUE;
if (nl->debug)
g_printerr ("Polish step %.15" GNM_FORMAT_g
@@ -654,37 +568,56 @@ polish_iter (GnmNlsolve *nl)
g_free (x);
if (any_at_all)
- gnm_nlsolve_set_solution (nl);
+ set_solution (nl);
return any_at_all;
}
static gboolean
-gnm_nlsolve_iterate (GnmIterSolver *isol, GnmNlsolve *nl)
+gnm_nlsolve_iterate (GnmSolverIterator *iter, GnmNlsolve *nl)
{
- const int n = nl->vars->len;
- gboolean progress;
+ GnmIterSolver *isol = nl->isol;
+ const int n = nl->n;
if (isol->iterations == 0)
rosenbrock_init (nl);
if (nl->debug) {
g_printerr ("Iteration %ld at %.15" GNM_FORMAT_g "\n",
- (long)(isol->iterations), nl->yk);
- print_vector ("Current point", nl->xk, n);
+ (long)(isol->iterations), isol->yk);
+ print_vector ("Current point", isol->xk, n);
}
- progress = rosenbrock_iter (nl);
+ return rosenbrock_iter (nl);
+}
+
+static gboolean
+gnm_nlsolve_polish (GnmSolverIterator *iter, GnmNlsolve *nl)
+{
+ return !nl->tentative && polish_iter (nl);
+}
+
+static void
+gnm_nlsolve_final (GnmNlsolve *nl)
+{
+ const int n = nl->n;
- if (!progress && !nl->tentative) {
- progress = polish_iter (nl);
+ /* Accept, i.e., don't try to restore. */
+ rosenbrock_tentative_end (nl, TRUE);
+
+ if (nl->xi) {
+ free_matrix (nl->xi, n);
+ nl->xi = NULL;
}
- return progress;
+ g_free (nl);
}
-gboolean
-nlsolve_solver_factory_functional (GnmSolverFactory *factory);
+/* ------------------------------------------------------------------------- */
+/* Plug-in interface. */
+
+gboolean nlsolve_solver_factory_functional (GnmSolverFactory *factory);
+GnmSolver *nlsolve_solver_factory (GnmSolverFactory *factory, GnmSolverParameters *params);
gboolean
nlsolve_solver_factory_functional (GnmSolverFactory *factory)
@@ -692,49 +625,41 @@ nlsolve_solver_factory_functional (GnmSolverFactory *factory)
return TRUE;
}
-
-GnmSolver *
-nlsolve_solver_factory (GnmSolverFactory *factory, GnmSolverParameters *params);
-
GnmSolver *
nlsolve_solver_factory (GnmSolverFactory *factory, GnmSolverParameters *params)
{
- GnmIterSolver *res = g_object_new (GNM_ITER_SOLVER_TYPE,
- "params", params,
- NULL);
+ GnmIterSolver *res = g_object_new
+ (GNM_ITER_SOLVER_TYPE,
+ "params", params,
+ "flip-sign", (params->problem_type == GNM_SOLVER_MAXIMIZE),
+ NULL);
GnmNlsolve *nl = g_new0 (GnmNlsolve, 1);
- int n;
- GnmValue const *vinput = gnm_solver_param_get_input (params);
- GnmEvalPos ep;
- GnmCellRef origin;
+ GnmSolverIteratorCompound *citer;
+ GnmSolverIterator *iter;
- nl->parent = res;
+ citer = g_object_new (GNM_SOLVER_ITERATOR_COMPOUND_TYPE, NULL);
- nl->maximize = (params->problem_type == GNM_SOLVER_MAXIMIZE);
+ iter = gnm_solver_iterator_new_func (G_CALLBACK (gnm_nlsolve_iterate), nl);
+ gnm_solver_iterator_compound_add (citer, iter, 1);
- eval_pos_init_sheet (&ep, params->sheet);
- if (vinput) {
- gnm_cellref_make_abs (&origin, &vinput->v_range.cell.a, &ep);
- nl->origin.col = origin.col;
- nl->origin.row = origin.row;
- nl->input_width = value_area_get_width (vinput, &ep);
- nl->input_height = value_area_get_height (vinput, &ep);
- }
+ iter = gnm_solver_iterator_new_func (G_CALLBACK (gnm_nlsolve_polish), nl);
+ gnm_solver_iterator_compound_add (citer, iter, 0);
- nl->debug = gnm_solver_debug ();
- nl->min_factor = 1e-10;
+ res->iterator = GNM_SOLVER_ITERATOR (citer);
- nl->vars = GNM_SOLVER (res)->input_cells;
- n = nl->vars->len;
+ nl->sol = GNM_SOLVER (res);
+ nl->isol = res;
- nl->x0 = g_new (gnm_float, n);
- nl->xk = g_new (gnm_float, n);
+ nl->debug = gnm_solver_debug ();
+ nl->min_factor = 1e-10;
+ nl->n = nl->sol->input_cells->len;
g_signal_connect (res, "prepare", G_CALLBACK (gnm_nlsolve_prepare), nl);
- g_signal_connect (res, "iterate", G_CALLBACK (gnm_nlsolve_iterate), nl);
g_object_set_data_full (G_OBJECT (res), PRIVATE_KEY, nl,
(GDestroyNotify)gnm_nlsolve_final);
return GNM_SOLVER (res);
}
+
+/* ------------------------------------------------------------------------- */
diff --git a/src/tools/gnm-solver.c b/src/tools/gnm-solver.c
index 21cb8dd..70504fc 100644
--- a/src/tools/gnm-solver.c
+++ b/src/tools/gnm-solver.c
@@ -824,9 +824,22 @@ gnm_solver_constructed (GObject *obj)
{
GnmSolver *sol = GNM_SOLVER (obj);
GnmSolverParameters *params = sol->params;
+ GnmValue const *vinput = gnm_solver_param_get_input (params);
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);
+ }
gnm_solver_parent_class->constructed (obj);
}
@@ -1034,8 +1047,8 @@ gnm_solver_store_result (GnmSolver *sol)
{
GnmValue const *vinput;
GnmSheetRange sr;
- int h, w, x, y;
GnmValue const *solution;
+ unsigned ui, n = sol->input_cells->len;
g_return_if_fail (GNM_IS_SOLVER (sol));
g_return_if_fail (sol->result != NULL);
@@ -1044,25 +1057,20 @@ gnm_solver_store_result (GnmSolver *sol)
vinput = gnm_solver_param_get_input (sol->params);
gnm_sheet_range_from_value (&sr, vinput);
if (!sr.sheet) sr.sheet = sol->params->sheet;
- h = range_height (&sr.range);
- w = range_width (&sr.range);
solution = gnm_solver_has_solution (sol)
? sol->result->solution
: NULL;
- for (x = 0; x < w; x++) {
- for (y = 0; y < h; y++) {
- GnmValue *v = solution
- ? value_dup (value_area_fetch_x_y (solution, x, y, NULL))
- : value_new_error_NA (NULL);
- GnmCell *cell =
- sheet_cell_fetch (sr.sheet,
- sr.range.start.col + x,
- sr.range.start.row + y);
- gnm_cell_set_value (cell, v);
- cell_queue_recalc (cell);
- }
+ 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);
+ gnm_cell_set_value (cell, v);
+ cell_queue_recalc (cell);
}
}
@@ -1293,7 +1301,7 @@ cell_in_cr (GnmCell const *cell, GnmSheetRange *sr, gboolean follow,
if (sr->sheet != cell->base.sheet ||
!range_contains (&sr->range, cell->pos.col, cell->pos.row)) {
- /* If the expression is just =X42 thenm look at X42 instead.
+ /* 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. */
GnmCellRef const *cr = gnm_expr_top_get_cellref (cell->base.texpr);
@@ -1671,6 +1679,30 @@ gnm_solver_get_target_value (GnmSolver *solver)
return gnm_nan;
}
+void
+gnm_solver_set_var (GnmSolver *sol, int i, gnm_float x)
+{
+ GnmCell *cell = g_ptr_array_index (sol->input_cells, i);
+
+ if (cell->value &&
+ VALUE_IS_FLOAT (cell->value) &&
+ value_get_as_float (cell->value) == x)
+ return;
+
+ gnm_cell_set_value (cell, value_new_float (x));
+ cell_queue_recalc (cell);
+}
+
+void
+gnm_solver_set_vars (GnmSolver *sol, gnm_float const *xs)
+{
+ const int n = sol->input_cells->len;
+ int i;
+
+ for (i = 0; i < n; i++)
+ gnm_solver_set_var (sol, i, xs[i]);
+}
+
static void
gnm_solver_class_init (GObjectClass *object_class)
{
@@ -2157,14 +2189,222 @@ GSF_CLASS (GnmSubSolver, gnm_sub_solver,
/* ------------------------------------------------------------------------- */
+enum {
+ SOL_ITER_SIG_ITERATE,
+ SOL_ITER_SIG_LAST
+};
+
+static guint solver_iterator_signals[SOL_ITER_SIG_LAST] = { 0 };
+
+static void
+gnm_solver_iterator_class_init (GObjectClass *object_class)
+{
+ solver_iterator_signals[SOL_ITER_SIG_ITERATE] =
+ g_signal_new ("iterate",
+ G_OBJECT_CLASS_TYPE (object_class),
+ G_SIGNAL_RUN_LAST,
+ G_STRUCT_OFFSET (GnmSolverIteratorClass, iterate),
+ NULL, NULL,
+ gnm__BOOLEAN__VOID,
+ G_TYPE_BOOLEAN, 0);
+}
+
+gboolean
+gnm_solver_iterator_iterate (GnmSolverIterator *iter)
+{
+ gboolean progress = FALSE;
+ g_signal_emit (iter, solver_iterator_signals[SOL_ITER_SIG_ITERATE], 0, &progress);
+ return progress;
+}
+
+GnmSolverIterator *
+gnm_solver_iterator_new_func (GCallback iterate, gpointer user)
+{
+ GnmSolverIterator *iter;
+
+ iter = g_object_new (GNM_SOLVER_ITERATOR_TYPE, NULL);
+ g_signal_connect (iter, "iterate", G_CALLBACK (iterate), user);
+ return iter;
+}
+
+GSF_CLASS (GnmSolverIterator, gnm_solver_iterator,
+ gnm_solver_iterator_class_init, NULL, G_TYPE_OBJECT)
+
+/* ------------------------------------------------------------------------- */
+
+static GObjectClass *gnm_solver_iterator_compound_parent_class;
+
+/**
+ * gnm_solver_iterator_compound_add:
+ * @ic: Compound iterator
+ * @iter: (transfer full): sub-iterator
+ * @count: repeat count
+ *
+ * Add an iterator to a compound iterator with a given repeat count. As a
+ * special case, a repeat count of zero means to try the iterator once
+ * in a cycle, but only if no other sub-iterator has shown any progress so far.
+ */
+void
+gnm_solver_iterator_compound_add (GnmSolverIteratorCompound *ic,
+ GnmSolverIterator *iter,
+ unsigned count)
+{
+ g_ptr_array_add (ic->iterators, iter);
+ ic->counts = g_renew (unsigned, ic->counts, ic->iterators->len);
+ ic->counts[ic->iterators->len - 1] = count;
+}
+
+static gboolean
+gnm_solver_iterator_compound_iterate (GnmSolverIterator *iter)
+{
+ GnmSolverIteratorCompound *ic = (GnmSolverIteratorCompound *)iter;
+ gboolean progress;
+
+ while (TRUE) {
+ if (ic->cycle >= ic->cycles)
+ return FALSE;
+
+ if (ic->next >= ic->iterators->len) {
+ /* We've been through all iterators. */
+ if (!ic->cycle_progress)
+ return FALSE;
+ ic->cycle_progress = FALSE;
+ ic->next = 0;
+ ic->next_counter = 0;
+ ic->cycle++;
+ continue;
+ }
+
+ if (ic->next_counter < ic->counts[ic->next])
+ break;
+
+ /* Special case: when count==0, use only if no progress. */
+ if (!ic->cycle_progress && ic->next_counter == 0)
+ break;
+
+ ic->next++;
+ ic->next_counter = 0;
+ }
+
+ progress = gnm_solver_iterator_iterate (g_ptr_array_index (ic->iterators, ic->next));
+ if (progress) {
+ ic->cycle_progress = TRUE;
+ ic->next_counter++;
+ } else {
+ /* No progress, so don't retry. */
+ ic->next++;
+ ic->next_counter = 0;
+ }
+
+ /* Report progress as long as we have stuff to try. */
+ return TRUE;
+}
+
+static void
+gnm_solver_iterator_compound_init (GnmSolverIteratorCompound *ic)
+{
+ ic->iterators = g_ptr_array_new ();
+ ic->cycles = G_MAXUINT;
+}
+
+static void
+gnm_solver_iterator_compound_finalize (GObject *obj)
+{
+ GnmSolverIteratorCompound *ic = (GnmSolverIteratorCompound *)obj;
+ g_ptr_array_foreach (ic->iterators, (GFunc)g_object_unref, NULL);
+ g_ptr_array_free (ic->iterators, TRUE);
+ g_free (ic->counts);
+ gnm_solver_iterator_compound_parent_class->finalize (obj);
+}
+
+static void
+gnm_solver_iterator_compound_class_init (GObjectClass *object_class)
+{
+ GnmSolverIteratorClass *iclass = (GnmSolverIteratorClass *)object_class;
+
+ gnm_solver_iterator_compound_parent_class = g_type_class_peek_parent (object_class);
+
+ object_class->finalize = gnm_solver_iterator_compound_finalize;
+ iclass->iterate = gnm_solver_iterator_compound_iterate;
+}
+
+GSF_CLASS (GnmSolverIteratorCompound, gnm_solver_iterator_compound,
+ gnm_solver_iterator_compound_class_init, gnm_solver_iterator_compound_init,
GNM_SOLVER_ITERATOR_TYPE)
+
+/* ------------------------------------------------------------------------- */
+
static GObjectClass *gnm_iter_solver_parent_class;
enum {
- ITER_SOL_SIG_ITERATE,
- ITER_SOL_SIG_LAST
+ ISOL_PROP_0,
+ ISOL_PROP_FLIP_SIGN
};
-static guint iter_solver_signals[ITER_SOL_SIG_LAST] = { 0 };
+gnm_float
+gnm_iter_solver_get_target_value (GnmIterSolver *isol)
+{
+ GnmSolver *sol = GNM_SOLVER (isol);
+ gnm_float y = gnm_solver_get_target_value (sol);
+ return isol->flip_sign ? 0 - y : y;
+}
+
+gboolean
+gnm_iter_solver_get_initial_solution (GnmIterSolver *isol, GError **err)
+{
+ GnmSolver *sol = GNM_SOLVER (isol);
+ const int n = sol->input_cells->len;
+ int i;
+
+ if (gnm_solver_check_constraints (sol))
+ goto got_it;
+
+ /* More? */
+
+ g_set_error (err,
+ go_error_invalid (),
+ 0,
+ _("The initial values do not satisfy the constraints."));
+ return FALSE;
+
+got_it:
+ for (i = 0; i < n; i++) {
+ GnmCell *cell = g_ptr_array_index (sol->input_cells, i);
+ isol->xk[i] = value_get_as_float (cell->value);
+ }
+ isol->yk = gnm_iter_solver_get_target_value (isol);
+
+ gnm_iter_solver_set_solution (isol);
+
+ return TRUE;
+}
+
+void
+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 = isol->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]));
+ }
+
+ g_object_set (sol, "result", result, NULL);
+ g_object_unref (result);
+
+ if (!gnm_solver_check_constraints (sol)) {
+ g_printerr ("Infeasible solution set\n");
+ }
+}
static void
gnm_iter_solver_clear (GnmIterSolver *isol)
@@ -2187,15 +2427,61 @@ static void
gnm_iter_solver_finalize (GObject *obj)
{
GnmIterSolver *isol = GNM_ITER_SOLVER (obj);
- (void)isol;
+ g_free (isol->xk);
gnm_iter_solver_parent_class->finalize (obj);
}
static void
+gnm_iter_solver_constructed (GObject *obj)
+{
+ GnmIterSolver *isol = GNM_ITER_SOLVER (obj);
+ GnmSolver *sol = GNM_SOLVER (obj);
+
+ /* Chain to parent first */
+ gnm_iter_solver_parent_class->constructed (obj);
+
+ isol->xk = g_new0 (gnm_float, sol->input_cells->len);
+}
+
+static void
gnm_iter_solver_init (GnmIterSolver *isol)
{
}
+static void
+gnm_iter_solver_get_property (GObject *object, guint property_id,
+ GValue *value, GParamSpec *pspec)
+{
+ GnmIterSolver *isol = (GnmIterSolver *)object;
+
+ switch (property_id) {
+ case ISOL_PROP_FLIP_SIGN:
+ g_value_set_boolean (value, isol->flip_sign);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
+ break;
+ }
+}
+
+static void
+gnm_iter_solver_set_property (GObject *object, guint property_id,
+ GValue const *value, GParamSpec *pspec)
+{
+ GnmIterSolver *isol = (GnmIterSolver *)object;
+
+ switch (property_id) {
+ case ISOL_PROP_FLIP_SIGN:
+ isol->flip_sign = g_value_get_boolean (value);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
+ break;
+ }
+}
+
static gint
gnm_iter_solver_idle (gpointer data)
{
@@ -2204,7 +2490,7 @@ gnm_iter_solver_idle (gpointer data)
GnmSolverParameters *params = sol->params;
gboolean progress;
- g_signal_emit (isol, iter_solver_signals[ITER_SOL_SIG_ITERATE], 0, &progress);
+ progress = isol->iterator && gnm_solver_iterator_iterate (isol->iterator);
isol->iterations++;
if (!gnm_solver_finished (sol) &&
@@ -2244,6 +2530,8 @@ gnm_iter_solver_stop (GnmSolver *solver, GError **err)
gnm_iter_solver_clear (isol);
+ g_clear_object (&isol->iterator);
+
gnm_solver_set_status (sol, GNM_SOLVER_STATUS_CANCELLED);
return TRUE;
@@ -2258,17 +2546,18 @@ gnm_iter_solver_class_init (GObjectClass *object_class)
object_class->dispose = gnm_iter_solver_dispose;
object_class->finalize = gnm_iter_solver_finalize;
+ object_class->constructed = gnm_iter_solver_constructed;
+ object_class->set_property = gnm_iter_solver_set_property;
+ object_class->get_property = gnm_iter_solver_get_property;
sclass->start = gnm_iter_solver_start;
sclass->stop = gnm_iter_solver_stop;
- iter_solver_signals[ITER_SOL_SIG_ITERATE] =
- g_signal_new ("iterate",
- G_OBJECT_CLASS_TYPE (object_class),
- G_SIGNAL_RUN_LAST,
- G_STRUCT_OFFSET (GnmIterSolverClass, iterate),
- NULL, NULL,
- gnm__BOOLEAN__VOID,
- G_TYPE_BOOLEAN, 0);
+ g_object_class_install_property (object_class, ISOL_PROP_FLIP_SIGN,
+ g_param_spec_boolean ("flip-sign",
+ P_("Flip Sign"),
+ P_("Flip sign of target value"),
+ FALSE,
+ GSF_PARAM_STATIC | G_PARAM_READWRITE));
}
GSF_CLASS (GnmIterSolver, gnm_iter_solver,
diff --git a/src/tools/gnm-solver.h b/src/tools/gnm-solver.h
index d1b627d..abdaa52 100644
--- a/src/tools/gnm-solver.h
+++ b/src/tools/gnm-solver.h
@@ -204,6 +204,8 @@ typedef struct {
/* Derived information */
GnmCell *target;
GPtrArray *input_cells;
+ GnmCellPos origin;
+ int input_width, input_height;
} GnmSolver;
typedef struct {
@@ -216,7 +218,7 @@ typedef struct {
gboolean (*stop) (GnmSolver *solver, GError **err);
} GnmSolverClass;
-GType gnm_solver_get_type (void);
+GType gnm_solver_get_type (void);
gboolean gnm_solver_prepare (GnmSolver *solver,
WorkbookControl *wbc, GError **err);
@@ -250,6 +252,8 @@ gboolean gnm_solver_saveas (GnmSolver *solver, WorkbookControl *wbc,
gboolean gnm_solver_debug (void);
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);
/* ------------------------------------------------------------------------- */
/* Solver subclass for subprocesses. */
@@ -283,7 +287,7 @@ typedef struct {
void (*child_exit) (GnmSubSolver *subsol, gboolean normal, int code);
} GnmSubSolverClass;
-GType gnm_sub_solver_get_type (void);
+GType gnm_sub_solver_get_type (void);
void gnm_sub_solver_clear (GnmSubSolver *subsol);
@@ -309,26 +313,88 @@ char *gnm_sub_solver_locate_binary (const char *binary, const char *solver,
WBCGtk *wbcg);
/* ------------------------------------------------------------------------- */
+
+typedef struct GnmIterSolver_ GnmIterSolver;
+typedef struct GnmSolverIterator_ GnmSolverIterator;
+
+/* Utility class for single iteration in a solving process. */
+
+#define GNM_SOLVER_ITERATOR_TYPE (gnm_solver_iterator_get_type ())
+#define GNM_SOLVER_ITERATOR(o) (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SOLVER_ITERATOR_TYPE,
GnmSolverIterator))
+#define GNM_IS_SOLVER_ITERATOR(o) (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_SOLVER_ITERATOR_TYPE))
+
+struct GnmSolverIterator_ {
+ GObject parent;
+};
+
+typedef struct {
+ GObjectClass parent_class;
+
+ gboolean (*iterate) (GnmSolverIterator *iter);
+} GnmSolverIteratorClass;
+
+GType gnm_solver_iterator_get_type (void);
+GnmSolverIterator *gnm_solver_iterator_new_func (GCallback iterate, gpointer user);
+gboolean gnm_solver_iterator_iterate (GnmSolverIterator *iter);
+
+
+
+#define GNM_SOLVER_ITERATOR_COMPOUND_TYPE (gnm_solver_iterator_compound_get_type ())
+#define GNM_SOLVER_ITERATOR_COMPOUND(o) (G_TYPE_CHECK_INSTANCE_CAST ((o),
GNM_SOLVER_ITERATOR_COMPOUND_TYPE, GnmSolverIteratorCompound))
+#define GNM_IS_SOLVER_ITERATOR_COMPOUND(o) (G_TYPE_CHECK_INSTANCE_TYPE ((o),
GNM_SOLVER_ITERATOR_COMPOUND_TYPE))
+
+typedef struct {
+ GnmSolverIterator parent;
+ unsigned cycles;
+
+ /* <protected> */
+ GPtrArray *iterators;
+ unsigned *counts;
+ unsigned next, next_counter, cycle;
+ gboolean cycle_progress;
+} GnmSolverIteratorCompound;
+
+typedef struct {
+ GnmSolverIteratorClass parent_class;
+} GnmSolverIteratorCompoundClass;
+
+GType gnm_solver_iterator_compound_get_type (void);
+void gnm_solver_iterator_compound_add (GnmSolverIteratorCompound *ic,
+ GnmSolverIterator *iter,
+ unsigned count);
+
+/* ------------------------------------------------------------------------- */
/* Solver subclass for iterative in-process solvers. */
#define GNM_ITER_SOLVER_TYPE (gnm_iter_solver_get_type ())
#define GNM_ITER_SOLVER(o) (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_ITER_SOLVER_TYPE, GnmIterSolver))
#define GNM_IS_ITER_SOLVER(o) (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_ITER_SOLVER_TYPE))
-typedef struct {
+struct GnmIterSolver_ {
GnmSolver parent;
+ /* Current point */
+ gnm_float *xk, yk;
+ gboolean flip_sign;
+
+ GnmSolverIterator *iterator;
+
guint64 iterations;
+
+ /* <private> */
guint idle_tag;
-} GnmIterSolver;
+};
typedef struct {
GnmSolverClass parent_class;
-
- void (*iterate) (GnmIterSolver *isol);
} GnmIterSolverClass;
-GType gnm_iter_solver_get_type (void);
+GType gnm_iter_solver_get_type (void);
+
+gnm_float gnm_iter_solver_get_target_value (GnmIterSolver *isol);
+
+gboolean gnm_iter_solver_get_initial_solution (GnmIterSolver *isol, GError **err);
+void gnm_iter_solver_set_solution (GnmIterSolver *isol);
/* ------------------------------------------------------------------------- */
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
