/* vim: set sw=8: -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ /* * mps.c: MPS file importer. * * Authors: * Jukka-Pekka Iivonen * * MPS importer module. MPS format is a de facto standard ASCII format * among most of the commercial LP solvers. * * This implementation does not yet support ranges and all types * of bounds but is already quite suitable for testing the * solving algorithms. See, for example, the Netlib collection * of LP problems in MPS format (ftp://netlib2.cs.utk.edu/lp/data). * * Supported bound types are: UP and LO. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include #include #include #include #include #include #include #include "cell.h" #include "sheet.h" #include "value.h" #include "file.h" #include "io-context.h" #include "workbook-view.h" #include "workbook.h" #include "plugin-util.h" #include "module-plugin-defs.h" #include "ranges.h" #include "style.h" #include "value.h" #include "solver.h" #include "sheet-style.h" #include "parse-util.h" #include "func.h" #include "expr.h" #include "mps.h" GNUMERIC_MODULE_PLUGIN_INFO_DECL; /************************************************************************* * * Sheet creation. */ /* Writes a string into a cell. */ static inline void mps_set_cell (Sheet *sh, int col, int row, const gchar *str) { GnmCell *cell = sheet_cell_fetch (sh, col, row); sheet_cell_set_value (cell, value_new_string (str)); } /* Writes a float into a cell. */ static inline void mps_set_cell_float (Sheet *sh, int col, int row, const gnm_float f) { GnmCell *cell = sheet_cell_fetch (sh, col, row); sheet_cell_set_value (cell, value_new_float (f)); } static void mps_set_style (Sheet *sh, int c1, int r1, int c2, int r2, gboolean italic, gboolean bold, gboolean ulined) { GnmStyle *mstyle; GnmRange range; mstyle = mstyle_new (); range_init (&range, c1, r1, c2, r2); mstyle_set_font_italic (mstyle, italic); mstyle_set_font_bold (mstyle, bold); mstyle_set_font_uline (mstyle, ulined); sheet_style_apply_range (sh, &range, mstyle); } /* Callback for the hash table mapping. */ static void put_into_index (gpointer key, gpointer value, gpointer user_data) { MpsInputContext *ctxt = (MpsInputContext *) user_data; MpsColInfo *info = (MpsColInfo *) value; ctxt->col_name_tbl[info->index] = info->name; } /* Make the constraint coefficient matrix and other preparations. */ static void mps_prepare (WorkbookView *wbv, MpsInputContext *ctxt) { gint i, n, col; GSList *current, *tmp; ctxt->rows = g_slist_reverse (ctxt->rows); ctxt->cols = g_slist_reverse (ctxt->cols); ctxt->col_name_tbl = g_new (gchar *, ctxt->n_cols); g_hash_table_foreach (ctxt->col_hash, put_into_index, (gpointer) ctxt); ctxt->matrix = g_new (gnm_float *, ctxt->n_rows + ctxt->n_bounds); for (i = 0; i < ctxt->n_rows + ctxt->n_bounds; i++) { ctxt->matrix[i] = g_new (gnm_float, ctxt->n_cols); for (n = 0; n < ctxt->n_cols; n++) ctxt->matrix[i][n] = 0.0; } current = ctxt->cols; while (current != NULL) { MpsCol *col = (MpsCol *) current->data; MpsColInfo *info; info = (MpsColInfo *) g_hash_table_lookup (ctxt->col_hash, col->name); ctxt->matrix[col->row->index][info->index] = col->value; current = current->next; } if ((ctxt->n_cols + MAX_COL - 1) / MAX_COL == 1) col = CONSTRAINT_COL + ctxt->n_cols - 1; else col = CONSTRAINT_COL + MAX_COL - 1; current = ctxt->bounds; tmp = ctxt->rows; ctxt->rows = NULL; i = ctxt->n_rows + ctxt->n_bounds - 2; while (current != NULL) { MpsBound *bound = (MpsBound *) current->data; static const MpsRowType type_map[] = { LessOrEqualRow, GreaterOrEqualRow, EqualityRow }; ctxt->matrix[ctxt->n_rows][bound->col_index] = 1.0; mps_set_cell_float (wbv->current_sheet, col + 3, i-- + CONSTRAINT_ROW, bound->value); mps_add_row (ctxt, type_map[(gint) bound->type], bound->name); current = current->next; } ctxt->rows = g_slist_concat (tmp, ctxt->rows); } static void mps_write_sheet_labels (MpsInputContext *ctxt, Sheet *sh) { int i, row, col, inc; int n_rows_per_fn; /* * Sheet header titles. */ /* Print 'Program Name'. */ n_rows_per_fn = (ctxt->n_cols + MAX_COL - 1) / MAX_COL; mps_set_cell (sh, MAIN_INFO_COL, MAIN_INFO_ROW - 1, _("Program Name")); mps_set_style (sh, MAIN_INFO_COL, MAIN_INFO_ROW - 1, MAIN_INFO_COL + 5, MAIN_INFO_ROW - 1, FALSE, TRUE, FALSE); /* Print 'Status'. */ mps_set_cell (sh, MAIN_INFO_COL + 3, MAIN_INFO_ROW - 1, _("Feasible")); /* Names of the variables. */ row = VARIABLE_ROW - 1; if (n_rows_per_fn == 1) { for (i = 0; i < ctxt->n_cols; i++) mps_set_cell (sh, VARIABLE_COL + i, row, ctxt->col_name_tbl [i]); } else { GString *buf; for (i = 0; i < MAX_COL; i++) { buf = g_string_new (NULL); g_string_append_printf (buf, "C[%d]", i + 1); mps_set_cell (sh, VARIABLE_COL + i, row, buf->str); g_string_free (buf, FALSE); } for (i = 0; i < n_rows_per_fn; i++) { buf = g_string_new (NULL); g_string_append_printf (buf, "R[%d]", i + 1); mps_set_cell (sh, VARIABLE_COL - 1, row + i + 1, buf->str); g_string_free (buf, FALSE); } mps_set_style (sh, VARIABLE_COL - 1, row, VARIABLE_COL - 1, row + n_rows_per_fn, FALSE, TRUE, FALSE); } mps_set_style (sh, VARIABLE_COL, row, VARIABLE_COL + MAX_COL, row, FALSE, TRUE, FALSE); /* Print 'Objective value'. */ mps_set_cell (sh, MAIN_INFO_COL + 1, MAIN_INFO_ROW - 1, _("Objective Value")); inc = n_rows_per_fn * 2; /* Print 'Objective function:' */ mps_set_cell (sh, VARIABLE_COL, VARIABLE_ROW - 2, _("Objective function:")); mps_set_style (sh, VARIABLE_COL, VARIABLE_ROW - 2, VARIABLE_COL, VARIABLE_ROW - 2, FALSE, TRUE, TRUE); /* Print 'Constraints:'. */ mps_set_cell (sh, CONSTRAINT_COL, CONSTRAINT_ROW - 2 + inc, _("Constraints:")); mps_set_style (sh, CONSTRAINT_COL, CONSTRAINT_ROW - 2 + inc, CONSTRAINT_COL, CONSTRAINT_ROW - 2 + inc, FALSE, TRUE, TRUE); /* * Print constraint titles. */ /* Name field. */ row = CONSTRAINT_ROW - 1 + inc; mps_set_cell (sh, CONSTRAINT_COL - 1, row, _("Name")); /* Names of the variables. */ if (n_rows_per_fn == 1) { for (i = 0; i < ctxt->n_cols; i++) mps_set_cell (sh, CONSTRAINT_COL + i, row, ctxt->col_name_tbl [i]); } else { GString *buf; for (i = 0; i < MAX_COL; i++) { buf = g_string_new (NULL); g_string_append_printf (buf, "C[%d]", i + 1); mps_set_cell (sh, CONSTRAINT_COL + i, row, buf->str); g_string_free (buf, FALSE); } } mps_set_style (sh, CONSTRAINT_COL - 1, row, CONSTRAINT_COL + MAX_COL + 5, row, FALSE, TRUE, FALSE); /* Value, Type, RHS, Slack, and Status titles. */ if (n_rows_per_fn == 1) col = CONSTRAINT_COL + ctxt->n_cols - 1; else col = CONSTRAINT_COL + MAX_COL - 1; mps_set_cell (sh, col + 1, row, _("Value")); mps_set_cell (sh, col + 2, row, _("Type")); mps_set_cell (sh, col + 3, row, _("RHS")); mps_set_cell (sh, col + 4, row, _("Slack")); } static void mps_write_coefficients (MpsInputContext *ctxt, Sheet *sh, SolverParameters *param) { GSList *current; int i, n, r, ecol, inc2; int n_rows_per_fn; GString *var_range [2]; GnmRange range, v_range; GnmCell *cell; GString *buf; /* * Add objective function stuff into the sheet. */ /* Print the column names, initialize the variables to 0, and * print the coefficients of the objective function. */ n_rows_per_fn = (ctxt->n_cols + MAX_COL - 1) / MAX_COL; if (n_rows_per_fn == 1) ecol = CONSTRAINT_COL + ctxt->n_cols - 1; else ecol = CONSTRAINT_COL + MAX_COL - 1; for (i = 0; i < ctxt->n_cols; i++) { mps_set_cell_float (sh, VARIABLE_COL + i % MAX_COL, VARIABLE_ROW + (i / MAX_COL), 0.0); mps_set_cell_float (sh, VARIABLE_COL + i % MAX_COL, VARIABLE_ROW + n_rows_per_fn + (i / MAX_COL) + 1, ctxt->matrix[ctxt->objective_row->index][i]); } /* * Add constraints into the sheet. */ /* Print constraints. */ inc2 = 2 * n_rows_per_fn; param->constraints = NULL; var_range [0] = g_string_new (NULL); var_range [1] = g_string_new (NULL); /* Initialize var_range to contain the range name of the * objective function variables. */ i = 0; range_init (&v_range, VARIABLE_COL, VARIABLE_ROW + n_rows_per_fn - 1, (ctxt->n_cols % MAX_COL), VARIABLE_ROW + n_rows_per_fn - 1); g_string_append_printf (var_range [i], "%s", range_name (&v_range)); i = 0; for (current = ctxt->rows; current != NULL; current = current->next) { SolverConstraint *c; MpsRow *row; int col, r; GnmExpr *expr; GnmExprList *args; GnmCellRef ref1, ref2; static const gchar *type_str[] = { "=", "<=", ">=" }; static const SolverConstraintType type_map[] = { SolverEQ, SolverLE, SolverGE }; row = (MpsRow *) current->data; if (row->type == ObjectiveRow) continue; col = CONSTRAINT_COL; r = CONSTRAINT_ROW + i * n_rows_per_fn + inc2; /* Add row name. */ mps_set_cell (sh, col - 1, r, row->name); /* Coefficients. */ for (n = 0; n < ctxt->n_cols; n++) /* Write only non-zero coefficents in order to save * memory, and, in addition, to speed up the loading. */ #ifndef MPS_WRITE_ZERO_COEFFICIENTS if (ctxt->matrix [row->index][n] != 0) #endif mps_set_cell_float (sh, col + n % MAX_COL, r + n / MAX_COL, ctxt->matrix[row->index][n]); /* Add Type field. */ mps_set_cell (sh, ecol + 2, r, type_str[(int) row->type]); /* Add RHS field (zero). */ mps_set_cell_float (sh, ecol + 3, r, 0); /* Add LHS field using SUMPRODUCT function. */ range_init (&range, col, r, ctxt->n_cols, r); args = (GnmExprList *) g_list_append (NULL, (gpointer) gnm_expr_new_constant (value_new_cellrange_r (NULL, &v_range))); args = (GnmExprList *) g_list_append ((GList *) args, (gpointer) gnm_expr_new_constant (value_new_cellrange_r (NULL, &range))); cell = sheet_cell_fetch (sh, ecol + 1, r); expr = (GnmExpr *) gnm_expr_new_funcall (gnm_func_lookup ("SUMPRODUCT", NULL), args); cell_set_expr (cell, expr); cell_queue_recalc (cell); /* Add Slack calculation */ cellref_init (&ref1, sh, ecol + 1, r, FALSE); cellref_init (&ref2, sh, ecol + 3, r, FALSE); expr = (GnmExpr *) gnm_expr_new_binary (gnm_expr_new_cellref (&ref1), GNM_EXPR_OP_SUB, gnm_expr_new_cellref (&ref2)); args = (GnmExprList *) g_list_append (NULL, (gpointer) expr); cell = sheet_cell_fetch (sh, ecol + 4, r); expr = (GnmExpr *) gnm_expr_new_funcall (gnm_func_lookup ("ABS", NULL), args); cell_set_expr (cell, expr); cell_queue_recalc (cell); /* Add Solver constraint */ c = g_new (SolverConstraint, 1); c->lhs.col = ecol + 1; c->lhs.row = r; c->rhs.col = ecol + 3; c->rhs.row = r; c->type = type_map[row->type]; /* const_cast */ c->cols = 1; c->rows = 1; c->str = write_constraint_str (c->lhs.col, c->lhs.row, c->rhs.col, c->rhs.row, c->type, c->cols, c->rows); param->constraints = g_slist_append (param->constraints, c); i++; } /* Write RHSes. */ current = ctxt->rhs; r = CONSTRAINT_ROW + inc2; while (current != NULL) { MpsRhs *rhs = (MpsRhs *) current->data; mps_set_cell_float (sh, ecol + 3, r + rhs->row->index * n_rows_per_fn, rhs->value); current = current->next; } /* Write the objective fn. */ buf = g_string_new (NULL); range_init (&range, VARIABLE_COL, VARIABLE_ROW + 1 + n_rows_per_fn, ctxt->n_cols, VARIABLE_ROW + 1 + n_rows_per_fn); g_string_append_printf (buf, "=SUMPRODUCT(%s,%s)", var_range[0]->str, range_name (&range)); cell = sheet_cell_fetch (sh, OBJECTIVE_VALUE_COL, MAIN_INFO_ROW); sheet_cell_set_text (cell, buf->str, NULL); g_string_free (buf, FALSE); /* Store the input cell range for the Solver dialog. */ g_string_free (var_range [0], FALSE); var_range [0] = g_string_new (NULL); range_init (&range, VARIABLE_COL, VARIABLE_ROW, MAX_COL, VARIABLE_ROW + n_rows_per_fn - 1); g_string_append_printf (var_range [0], "%s", range_name (&range)); param->input_entry_str = g_strdup (var_range [0]->str); g_string_free (var_range [0], FALSE); g_string_free (var_range [1], FALSE); } /* Creates the spreadsheet model. */ static void mps_create_sheet (MpsInputContext *ctxt, WorkbookView *wbv) { Sheet *sh = wbv->current_sheet; gint i; int n_rows_per_fn; SolverParameters *param = sh->solver_parameters; n_rows_per_fn = (ctxt->n_cols + MAX_COL - 1) / MAX_COL; mps_prepare (wbv, ctxt); mps_write_sheet_labels (ctxt, sh); mps_write_coefficients (ctxt, sh, param); /* Print the name of the objective function */ if (ctxt->n_cols < MAX_COL) mps_set_cell (sh, VARIABLE_COL - 1, VARIABLE_ROW + 1 + n_rows_per_fn, ctxt->objective_row->name); else { for (i = 0; i < n_rows_per_fn; i++) { GString *buf = g_string_new (NULL); g_string_append_printf (buf, "%s (R[%d])", ctxt->objective_row->name, i+1); mps_set_cell (sh, VARIABLE_COL - 1, VARIABLE_ROW + 1 + i + n_rows_per_fn, buf->str); g_string_free (buf, FALSE); } } param->target_cell = sheet_cell_fetch (sh, OBJECTIVE_VALUE_COL, MAIN_INFO_ROW); param->problem_type = SolverMinimize; /* Write the name of the program. */ if (ctxt->name != NULL) mps_set_cell (sh, MAIN_INFO_COL, MAIN_INFO_ROW, ctxt->name); /* Autofit column A */ i = sheet_col_size_fit_pixels (sh, 0); if (i == 0) return; sheet_col_set_size_pixels (sh, 0, i, TRUE); sheet_recompute_spans_for_col (sh, 0); workbook_recalc (sh->workbook); } /************************************************************************ * * Data structure initializations and releasing. */ /* Make the initializations. */ static MpsInputContext * mps_input_context_new (IOContext *io_context, Workbook *wb, GsfInput *input) { MpsInputContext *ctxt = NULL; ctxt = g_new (MpsInputContext, 1); ctxt->io_context = io_context; ctxt->input = (GsfInputTextline *)gsf_input_textline_new (input); ctxt->line_no = 1; ctxt->line = NULL; ctxt->sheet = workbook_sheet_add (wb, NULL, FALSE); ctxt->name = NULL; ctxt->rows = NULL; ctxt->cols = NULL; ctxt->rhs = NULL; ctxt->bounds = NULL; ctxt->row_hash = g_hash_table_new (g_str_hash, g_str_equal); ctxt->col_hash = g_hash_table_new (g_str_hash, g_str_equal); ctxt->col_name_tbl = NULL; ctxt->matrix = NULL; ctxt->n_rows = ctxt->n_cols = ctxt->n_bounds = 0; g_slist_free (ctxt->rows); io_progress_message (io_context, _("Reading file...")); return ctxt; } /* Call-back for mps_input_context_destroy. */ static gboolean rh_rm_cb (gpointer key, gpointer value, gpointer user_data) { return TRUE; } /* Call-back for mps_input_context_destroy. */ static gboolean ch_rm_cb (gpointer key, gpointer value, gpointer user_data) { MpsColInfo *info = (MpsColInfo *) value; g_free (info->name); g_free (info); return TRUE; } /* Free the allocated memory. */ static void mps_input_context_destroy (MpsInputContext *ctxt) { GSList *current; io_progress_unset (ctxt->io_context); /* Free ROWS */ for (current = ctxt->rows; current != NULL; current = current->next) { MpsRow *row = (MpsRow *) current->data; g_free (row->name); g_free (current->data); } /* Free COLUMNS */ for (current = ctxt->cols; current != NULL; current = current->next) { MpsCol *col = (MpsCol *) current->data; g_free (col->name); g_free (current->data); } ctxt->cols = NULL; /* Free RHSs */ for (current = ctxt->rhs; current != NULL; current = current->next) { MpsRhs *rhs = (MpsRhs *) current->data; g_free (rhs->name); g_free (current->data); } /* Free BOUNDS */ for (current = ctxt->bounds; current!=NULL; current = current->next) { MpsBound *bound = (MpsBound *) current->data; g_free (bound->name); g_free (current->data); } g_slist_free (ctxt->rows); g_slist_free (ctxt->cols); g_slist_free (ctxt->rhs); g_slist_free (ctxt->bounds); g_hash_table_foreach_remove (ctxt->row_hash, (GHRFunc) rh_rm_cb, NULL); g_hash_table_foreach_remove (ctxt->col_hash, (GHRFunc) ch_rm_cb, NULL); g_hash_table_destroy (ctxt->row_hash); g_hash_table_destroy (ctxt->col_hash); if (ctxt->col_name_tbl) { g_free (ctxt->col_name_tbl); ctxt->col_name_tbl = NULL; } if (ctxt->matrix) { g_free (ctxt->matrix); ctxt->matrix = NULL; } g_free (ctxt->name); g_object_unref (G_OBJECT (ctxt->input)); ctxt->input = NULL; g_free (ctxt); } /*---------------------------------------------------------------------*/ /* * The public plug-in API. */ void mps_file_open (GnmFileOpener const *fo, IOContext *io_context, WorkbookView *wbv, GsfInput *input) { MpsInputContext *ctxt; ctxt = mps_input_context_new (io_context, wb_view_workbook (wbv), input); if (ctxt != NULL) { mps_parse_file (ctxt); if (gnumeric_io_error_occurred (io_context)) { gnumeric_io_error_push (io_context, error_info_new_str (_("Error while reading MPS " "file."))); } else mps_create_sheet (ctxt, wbv); mps_input_context_destroy (ctxt); } else if (!gnumeric_io_error_occurred (io_context)) gnumeric_io_error_unknown (io_context); }