src/tools/gnm-solver.h

   1 #ifndef _TOOLS_GNM_SOLVER_H_
   2 #define _TOOLS_GNM_SOLVER_H_
   3
   4 #include <gnumeric.h>
   5 #include <glib-object.h>
   6 #include <dependent.h>
   7 #include <numbers.h>
   8 #include <wbc-gtk.h>
   9
  10 G_BEGIN_DECLS
  11
  12 /* ------------------------------------------------------------------------- */
  13
  14 typedef enum {
  15         GNM_SOLVER_RESULT_NONE,
  16         GNM_SOLVER_RESULT_FEASIBLE,
  17         GNM_SOLVER_RESULT_OPTIMAL,
  18         GNM_SOLVER_RESULT_INFEASIBLE,
  19         GNM_SOLVER_RESULT_UNBOUNDED
  20 } GnmSolverResultQuality;
  21
  22
  23 GType gnm_solver_status_get_type (void);
  24 #define GNM_SOLVER_STATUS_TYPE (gnm_solver_status_get_type ())
  25
  26 typedef enum {
  27         GNM_SOLVER_STATUS_READY,
  28         GNM_SOLVER_STATUS_PREPARING,
  29         GNM_SOLVER_STATUS_PREPARED,
  30         GNM_SOLVER_STATUS_RUNNING,
  31         GNM_SOLVER_STATUS_DONE,
  32         GNM_SOLVER_STATUS_ERROR,
  33         GNM_SOLVER_STATUS_CANCELLED
  34 } GnmSolverStatus;
  35
  36
  37 typedef enum {
  38         GNM_SOLVER_LE,
  39         GNM_SOLVER_GE,
  40         GNM_SOLVER_EQ,
  41         GNM_SOLVER_INTEGER,
  42         GNM_SOLVER_BOOLEAN
  43 } GnmSolverConstraintType;
  44
  45
  46 typedef enum {
  47         GNM_SOLVER_LP, GNM_SOLVER_QP, GNM_SOLVER_NLP
  48 } GnmSolverModelType;
  49
  50
  51 GType gnm_solver_problem_type_get_type (void);
  52 #define GNM_SOLVER_PROBLEM_TYPE_TYPE (gnm_solver_problem_type_get_type ())
  53
  54 typedef enum {
  55         GNM_SOLVER_MINIMIZE, GNM_SOLVER_MAXIMIZE
  56 } GnmSolverProblemType;
  57
  58 /* -------------------------------------------------------------------------- */
  59
  60 struct GnmSolverConstraint_ {
  61         GnmSolverConstraintType type;
  62
  63         /* Must be a range.  */
  64         GnmDependent lhs;
  65
  66         /* Must be a constant or a range.  */
  67         GnmDependent rhs;
  68 };
  69
  70 GType gnm_solver_constraint_get_type (void);
  71
  72 GnmSolverConstraint *gnm_solver_constraint_new (Sheet *sheet);
  73 void gnm_solver_constraint_free (GnmSolverConstraint *c);
  74 GnmSolverConstraint *gnm_solver_constraint_dup (GnmSolverConstraint *c,
  75                                                 Sheet *sheet);
  76 gboolean gnm_solver_constraint_equal (GnmSolverConstraint const *a,
  77                                       GnmSolverConstraint const *b);
  78
  79 void gnm_solver_constraint_set_old (GnmSolverConstraint *c,
  80                                     GnmSolverConstraintType type,
  81                                     int lhs_col, int lhs_row,
  82                                     int rhs_col, int rhs_row,
  83                                     int cols, int rows);
  84
  85 gboolean gnm_solver_constraint_has_rhs (GnmSolverConstraint const *c);
  86 gboolean gnm_solver_constraint_valid (GnmSolverConstraint const *c,
  87                                       GnmSolverParameters const *sp);
  88 gboolean gnm_solver_constraint_get_part (GnmSolverConstraint const *c,
  89                                          GnmSolverParameters const *sp, int i,
  90                                          GnmCell **lhs, gnm_float *cl,
  91                                          GnmCell **rhs, gnm_float *cr);
  92
  93 GnmValue const *gnm_solver_constraint_get_lhs (GnmSolverConstraint const *c);
  94 GnmValue const *gnm_solver_constraint_get_rhs (GnmSolverConstraint const *c);
  95
  96 void gnm_solver_constraint_set_lhs (GnmSolverConstraint *c, GnmValue *v);
  97 void gnm_solver_constraint_set_rhs (GnmSolverConstraint *c, GnmValue *v);
  98
  99 void gnm_solver_constraint_side_as_str (GnmSolverConstraint const *c,
 100                                         Sheet const *sheet,
 101                                         GString *buf, gboolean lhs);
 102 char *gnm_solver_constraint_as_str (GnmSolverConstraint const *c, Sheet *sheet);
 103 char *gnm_solver_constraint_part_as_str (GnmSolverConstraint const *c, int i,
 104                                          GnmSolverParameters *sp);
 105
 106 /* ------------------------------------------------------------------------- */
 107
 108 typedef struct {
 109         int                 max_time_sec;
 110         unsigned            max_iter;
 111         GnmSolverFactory   *algorithm;
 112         GnmSolverModelType  model_type;
 113         gboolean            assume_non_negative;
 114         gboolean            assume_discrete;
 115         gboolean            automatic_scaling;
 116         gboolean            program_report;
 117         gboolean            sensitivity_report;
 118         gboolean            add_scenario;
 119         gchar               *scenario_name;
 120         unsigned            gradient_order;
 121 } GnmSolverOptions;
 122
 123 #define GNM_SOLVER_PARAMETERS_TYPE   (gnm_solver_param_get_type ())
 124 #define GNM_SOLVER_PARAMETERS(o)     (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SOLVER_PARAMETERS_TYPE, GnmSolverParameters))
 125 #define GNM_IS_SOLVER_PARAMETERS(o)  (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_SOLVER_PARAMETERS_TYPE))
 126
 127 struct GnmSolverParameters_ {
 128         GObject parent;
 129
 130         /* Default parsing sheet.  No ref held.  */
 131         Sheet *sheet;
 132
 133         GnmSolverProblemType problem_type;
 134         GnmDependent target;
 135         GnmDependent input;
 136         GSList *constraints;
 137         GnmSolverOptions options;
 138 };
 139
 140 typedef struct {
 141         GObjectClass parent_class;
 142 } GnmSolverParametersClass;
 143
 144 GType gnm_solver_param_get_type (void);
 145
 146 /* Creates a new GnmSolverParameters object. */
 147 GnmSolverParameters *gnm_solver_param_new (Sheet *sheet);
 148
 149 /* Duplicate a GnmSolverParameters object. */
 150 GnmSolverParameters *gnm_solver_param_dup (GnmSolverParameters *src,
 151                                            Sheet *new_sheet);
 152
 153 gboolean gnm_solver_param_equal (GnmSolverParameters const *a,
 154                                  GnmSolverParameters const *b);
 155
 156 GnmValue const *gnm_solver_param_get_input (GnmSolverParameters const *sp);
 157 void gnm_solver_param_set_input (GnmSolverParameters *sp, GnmValue *v);
 158 GPtrArray *gnm_solver_param_get_input_cells (GnmSolverParameters const *sp);
 159
 160 const GnmCellRef *gnm_solver_param_get_target (GnmSolverParameters const *sp);
 161 void gnm_solver_param_set_target (GnmSolverParameters *sp,
 162                                   GnmCellRef const *cr);
 163 GnmCell *gnm_solver_param_get_target_cell (GnmSolverParameters const *sp);
 164
 165 void gnm_solver_param_set_algorithm (GnmSolverParameters *sp,
 166                                      GnmSolverFactory *algo);
 167
 168 gboolean gnm_solver_param_valid (GnmSolverParameters const *sp, GError **err);
 169
 170 /* -------------------------------------------------------------------------- */
 171
 172 #define GNM_SOLVER_RESULT_TYPE   (gnm_solver_result_get_type ())
 173 #define GNM_SOLVER_RESULT(o)     (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SOLVER_RESULT_TYPE, GnmSolverResult))
 174
 175 typedef struct {
 176         GObject parent;
 177
 178         GnmSolverResultQuality quality;
 179
 180         /* Objective value, if any */
 181         gnm_float value;
 182
 183         /* Array value of solution, if any */
 184         gnm_float *solution;
 185 } GnmSolverResult;
 186
 187 typedef struct {
 188         GObjectClass parent_class;
 189 } GnmSolverResultClass;
 190
 191 GType gnm_solver_result_get_type (void);
 192
 193 /* ------------------------------------------------------------------------- */
 194
 195 #define GNM_SOLVER_SENSITIVITY_TYPE   (gnm_solver_sensitivity_get_type ())
 196 #define GNM_SOLVER_SENSITIVITY(o)     (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SOLVER_SENSITIVITY_TYPE, GnmSolverSensitivity))
 197
 198 typedef struct {
 199         GObject parent;
 200
 201         GnmSolver *solver;
 202
 203         struct GnmSolverSensitivityVars_ {
 204                 gnm_float low, high;      //  Allowable range
 205                 gnm_float reduced_cost;
 206         } *vars;
 207
 208         struct GnmSolverSensitivityConstraints_ {
 209                 gnm_float low, high;      //  Allowable range
 210                 gnm_float shadow_price;
 211         } *constraints;
 212 } GnmSolverSensitivity;
 213
 214 typedef struct {
 215         GObjectClass parent_class;
 216 } GnmSolverSensitivityClass;
 217
 218 GType gnm_solver_sensitivity_get_type (void);
 219
 220 GnmSolverSensitivity *gnm_solver_sensitivity_new (GnmSolver *sol);
 221
 222 /* ------------------------------------------------------------------------- */
 223 /* Generic Solver class. */
 224
 225 #define GNM_SOLVER_TYPE        (gnm_solver_get_type ())
 226 #define GNM_SOLVER(o)          (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SOLVER_TYPE, GnmSolver))
 227 #define GNM_IS_SOLVER(o)       (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_SOLVER_TYPE))
 228
 229 struct GnmSolver_ {
 230         GObject parent;
 231
 232         GnmSolverStatus status;
 233         char *reason;
 234
 235         GnmSolverParameters *params;
 236         GnmSolverResult *result;
 237         GnmSolverSensitivity *sensitivity;
 238         double starttime, endtime;
 239         gboolean flip_sign;
 240
 241         /* Derived information */
 242         GnmCell *target;
 243         GPtrArray *input_cells;
 244         GHashTable *index_from_cell;
 245         gnm_float *min;
 246         gnm_float *max;
 247         guint8 *discrete;
 248
 249         // Analytic gradient
 250         int gradient_status; // 0: not tried; 1: ok; 2: fail
 251         GPtrArray *gradient;
 252
 253         // Analytic Hessian
 254         int hessian_status; // 0: not tried; 1: ok; 2: fail
 255         GPtrArray *hessian;
 256 };
 257
 258 typedef struct {
 259         GObjectClass parent_class;
 260
 261         gboolean (*prepare) (GnmSolver *sol,
 262                              WorkbookControl *wbc, GError **err);
 263         gboolean (*start) (GnmSolver *sol,
 264                            WorkbookControl *wbc, GError **err);
 265         gboolean (*stop) (GnmSolver *sol, GError **err);
 266 } GnmSolverClass;
 267
 268 GType gnm_solver_get_type (void);
 269
 270 gboolean gnm_solver_prepare (GnmSolver *sol,
 271                              WorkbookControl *wbc, GError **err);
 272 gboolean gnm_solver_start (GnmSolver *sol,
 273                            WorkbookControl *wbc, GError **err);
 274 gboolean gnm_solver_stop (GnmSolver *sol, GError **err);
 275
 276 void gnm_solver_set_status (GnmSolver *solver, GnmSolverStatus status);
 277
 278 void gnm_solver_set_reason (GnmSolver *solver, const char *reason);
 279
 280 void gnm_solver_store_result (GnmSolver *solver);
 281
 282 void gnm_solver_create_report (GnmSolver *solver, const char *name);
 283
 284 double gnm_solver_elapsed (GnmSolver *solver);
 285
 286 gboolean gnm_solver_check_timeout (GnmSolver *solver);
 287
 288 gboolean gnm_solver_finished (GnmSolver *solver);
 289
 290 gboolean gnm_solver_has_solution (GnmSolver *solver);
 291
 292 gboolean gnm_solver_check_constraints (GnmSolver *solver);
 293
 294 gboolean gnm_solver_saveas (GnmSolver *solver, WorkbookControl *wbc,
 295                             GOFileSaver *fs,
 296                             const char *templ, char **filename,
 297                             GError **err);
 298
 299 gboolean gnm_solver_debug (void);
 300
 301 int gnm_solver_cell_index (GnmSolver *solver, GnmCell const *cell);
 302
 303 gnm_float gnm_solver_get_target_value (GnmSolver *solver);
 304 void gnm_solver_set_var (GnmSolver *sol, int i, gnm_float x);
 305 void gnm_solver_set_vars (GnmSolver *sol, gnm_float const *xs);
 306
 307 GPtrArray *gnm_solver_save_vars (GnmSolver *sol);
 308 void gnm_solver_restore_vars (GnmSolver *sol, GPtrArray *vals);
 309
 310 gboolean gnm_solver_has_analytic_gradient (GnmSolver *sol);
 311 gnm_float *gnm_solver_compute_gradient (GnmSolver *sol, gnm_float const *xs);
 312
 313 gboolean gnm_solver_has_analytic_hessian (GnmSolver *sol);
 314 GnmMatrix *gnm_solver_compute_hessian (GnmSolver *sol, gnm_float const *xs);
 315
 316 gnm_float gnm_solver_line_search (GnmSolver *sol,
 317                                   gnm_float const *x0, gnm_float const *dir,
 318                                   gboolean try_reverse,
 319                                   gnm_float step, gnm_float max_step, gnm_float eps,
 320                                   gnm_float *py);
 321
 322 void gnm_solver_pick_lp_coords (GnmSolver *sol,
 323                                 gnm_float **px1, gnm_float **px2);
 324
 325 gnm_float *gnm_solver_get_lp_coeffs (GnmSolver *sol, GnmCell *ycell,
 326                                      gnm_float const *x1, gnm_float const *x2,
 327                                      GError **err);
 328
 329 /* ------------------------------------------------------------------------- */
 330 /* Solver subclass for subprocesses. */
 331
 332 #define GNM_SUB_SOLVER_TYPE     (gnm_sub_solver_get_type ())
 333 #define GNM_SUB_SOLVER(o)       (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SUB_SOLVER_TYPE, GnmSubSolver))
 334 #define GNM_IS_SUB_SOLVER(o)    (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_SUB_SOLVER_TYPE))
 335
 336 typedef struct {
 337         GnmSolver parent;
 338
 339         char *program_filename;
 340
 341         /* Hashes between char* and cell*.  */
 342         GHashTable *cell_from_name;
 343         GHashTable *name_from_cell;
 344
 345         GHashTable *constraint_from_name;
 346
 347         GPid child_pid;
 348         guint child_watch;
 349
 350         gint fd[3];
 351         GIOChannel *channels[3];
 352         guint channel_watches[3];
 353         GIOFunc io_funcs[3];
 354         gpointer io_funcs_data[3];
 355 } GnmSubSolver;
 356
 357 typedef struct {
 358         GnmSolverClass parent_class;
 359
 360         void (*child_exit) (GnmSubSolver *subsol, gboolean normal, int code);
 361 } GnmSubSolverClass;
 362
 363 GType gnm_sub_solver_get_type (void);
 364
 365 void gnm_sub_solver_clear (GnmSubSolver *subsol);
 366
 367 gboolean gnm_sub_solver_spawn
 368                 (GnmSubSolver *subsol,
 369                  char **argv,
 370                  GSpawnChildSetupFunc child_setup, gpointer setup_data,
 371                  GIOFunc io_stdout, gpointer stdout_data,
 372                  GIOFunc io_stderr, gpointer stderr_data,
 373                  GError **err);
 374
 375 void gnm_sub_solver_flush (GnmSubSolver *subsol);
 376
 377 const char *gnm_sub_solver_name_cell (GnmSubSolver *subsol,
 378                                       GnmCell const *cell,
 379                                       const char *name);
 380 GnmCell *gnm_sub_solver_find_cell (GnmSubSolver *subsol, const char *name);
 381 const char *gnm_sub_solver_get_cell_name (GnmSubSolver *subsol,
 382                                           GnmCell const *cell);
 383
 384 const char *gnm_sub_solver_name_constraint (GnmSubSolver *subsol,
 385                                             int cidx,
 386                                             const char *name);
 387 int gnm_sub_solver_find_constraint (GnmSubSolver *subsol, const char *name);
 388
 389 char *gnm_sub_solver_locate_binary (const char *binary, const char *solver,
 390                                     const char *url,
 391                                     WBCGtk *wbcg);
 392
 393 /* ------------------------------------------------------------------------- */
 394
 395 typedef struct GnmIterSolver_ GnmIterSolver;
 396 typedef struct GnmSolverIterator_ GnmSolverIterator;
 397
 398 /* Utility class for single iteration in a solving process.  */
 399
 400 #define GNM_SOLVER_ITERATOR_TYPE     (gnm_solver_iterator_get_type ())
 401 #define GNM_SOLVER_ITERATOR(o)       (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SOLVER_ITERATOR_TYPE, GnmSolverIterator))
 402 #define GNM_IS_SOLVER_ITERATOR(o)    (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_SOLVER_ITERATOR_TYPE))
 403
 404 struct GnmSolverIterator_ {
 405         GObject parent;
 406 };
 407
 408 typedef struct {
 409         GObjectClass parent_class;
 410
 411         gboolean (*iterate) (GnmSolverIterator *iter);
 412 } GnmSolverIteratorClass;
 413
 414 GType gnm_solver_iterator_get_type (void);
 415
 416 GnmSolverIterator *gnm_solver_iterator_new_func (GCallback iterate, gpointer user);
 417 GnmSolverIterator *gnm_solver_iterator_new_polish (GnmIterSolver *isol);
 418 GnmSolverIterator *gnm_solver_iterator_new_gradient (GnmIterSolver *isol);
 419
 420 gboolean gnm_solver_iterator_iterate (GnmSolverIterator *iter);
 421
 422
 423
 424 #define GNM_SOLVER_ITERATOR_COMPOUND_TYPE     (gnm_solver_iterator_compound_get_type ())
 425 #define GNM_SOLVER_ITERATOR_COMPOUND(o)       (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SOLVER_ITERATOR_COMPOUND_TYPE, GnmSolverIteratorCompound))
 426 #define GNM_IS_SOLVER_ITERATOR_COMPOUND(o)    (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_SOLVER_ITERATOR_COMPOUND_TYPE))
 427
 428 typedef struct {
 429         GnmSolverIterator parent;
 430         unsigned cycles;
 431
 432         /* <protected> */
 433         GPtrArray *iterators;
 434         unsigned *counts;
 435         unsigned next, next_counter, cycle;
 436         gboolean cycle_progress;
 437 } GnmSolverIteratorCompound;
 438
 439 typedef struct {
 440         GnmSolverIteratorClass parent_class;
 441 } GnmSolverIteratorCompoundClass;
 442
 443 GType gnm_solver_iterator_compound_get_type (void);
 444 void gnm_solver_iterator_compound_add (GnmSolverIteratorCompound *ic,
 445                                        GnmSolverIterator *iter,
 446                                        unsigned count);
 447
 448 /* ------------------------------------------------------------------------- */
 449 /* Solver subclass for iterative in-process solvers. */
 450
 451 #define GNM_ITER_SOLVER_TYPE     (gnm_iter_solver_get_type ())
 452 #define GNM_ITER_SOLVER(o)       (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_ITER_SOLVER_TYPE, GnmIterSolver))
 453 #define GNM_IS_ITER_SOLVER(o)    (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_ITER_SOLVER_TYPE))
 454
 455 struct GnmIterSolver_ {
 456         GnmSolver parent;
 457
 458         /* Current point */
 459         gnm_float *xk, yk;
 460
 461         GnmSolverIterator *iterator;
 462
 463         guint64 iterations;
 464
 465         /* <private> */
 466         guint idle_tag;
 467 };
 468
 469 typedef struct {
 470         GnmSolverClass parent_class;
 471 } GnmIterSolverClass;
 472
 473 GType gnm_iter_solver_get_type (void);
 474
 475 void gnm_iter_solver_set_iterator (GnmIterSolver *isol, GnmSolverIterator *iterator);
 476
 477 gboolean gnm_iter_solver_get_initial_solution (GnmIterSolver *isol, GError **err);
 478 void gnm_iter_solver_set_solution (GnmIterSolver *isol);
 479
 480 /* ------------------------------------------------------------------------- */
 481
 482 #define GNM_SOLVER_FACTORY_TYPE        (gnm_solver_factory_get_type ())
 483 #define GNM_SOLVER_FACTORY(o)          (G_TYPE_CHECK_INSTANCE_CAST ((o), GNM_SOLVER_FACTORY_TYPE, GnmSolverFactory))
 484 #define GNM_IS_SOLVER_FACTORY(o)       (G_TYPE_CHECK_INSTANCE_TYPE ((o), GNM_SOLVER_FACTORY_TYPE))
 485
 486 typedef GnmSolver * (*GnmSolverCreator) (GnmSolverFactory *factory,
 487                                          GnmSolverParameters *param,
 488                                          gpointer data);
 489 typedef gboolean (*GnmSolverFactoryFunctional) (GnmSolverFactory *factory,
 490                                                 WBCGtk *wbcg,
 491                                                 gpointer data);
 492
 493 struct GnmSolverFactory_ {
 494         GObject parent;
 495
 496         /* <private> */
 497         char *id;
 498         char *name; /* Already translated */
 499         GnmSolverModelType type;
 500         GnmSolverCreator creator;
 501         GnmSolverFactoryFunctional functional;
 502         gpointer data;
 503         GDestroyNotify notify;
 504 };
 505
 506 typedef struct {
 507         GObjectClass parent_class;
 508 } GnmSolverFactoryClass;
 509
 510 GType gnm_solver_factory_get_type (void);
 511
 512 GnmSolverFactory *gnm_solver_factory_new (const char *id,
 513                                           const char *name,
 514                                           GnmSolverModelType type,
 515                                           GnmSolverCreator creator,
 516                                           GnmSolverFactoryFunctional functional,
 517                                           gpointer data,
 518                                           GDestroyNotify notify);
 519 GnmSolver *gnm_solver_factory_create (GnmSolverFactory *factory,
 520                                       GnmSolverParameters *param);
 521 gboolean gnm_solver_factory_functional (GnmSolverFactory *factory,
 522                                         WBCGtk *wbcg);
 523
 524 GSList *gnm_solver_db_get (void);
 525 void gnm_solver_db_register (GnmSolverFactory *factory);
 526 void gnm_solver_db_unregister (GnmSolverFactory *factory);
 527
 528 /* ------------------------------------------------------------------------- */
 529
 530 G_END_DECLS
 531
 532 #endif /* _TOOLS_GNM_SOLVER_H_ */