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 GnmDepManaged lhs; 65 66 /* Must be a constant or a range. */ 67 GnmDepManaged 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 GnmDepManaged target; 135 GnmDepManaged 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_ */ 533