nsz Git - libfirm/blob - ir/lpp/lpp.h

   1 /*
   2  * Copyright (C) 2005-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Interface for specifying an milp. Does not define a solution method.
  23  * @author  Daniel Grund
  24  */
  25 #ifndef LPP_LPP_H
  26 #define LPP_LPP_H
  27
  28 #include <stdio.h>
  29 #include <obstack.h>
  30
  31 #include "set.h"
  32
  33 #include "sp_matrix.h"
  34
  35 typedef enum _lpp_opt_t {
  36         lpp_minimize,
  37         lpp_maximize
  38 } lpp_opt_t;
  39
  40 typedef enum _lpp_cst_t {
  41         lpp_objective,
  42         lpp_equal,
  43         lpp_less,
  44         lpp_greater
  45 } lpp_cst_t;
  46
  47 typedef enum _lpp_var_t {
  48         lpp_invalid,
  49         lpp_rhs,
  50         lpp_continous,
  51         lpp_binary
  52 } lpp_var_t;
  53
  54 typedef enum _lpp_sol_state_t {
  55         lpp_unknown,
  56         lpp_infeasible,
  57         lpp_inforunb,
  58         lpp_unbounded,
  59         lpp_feasible,
  60         lpp_optimal
  61 } lpp_sol_state_t;
  62
  63 typedef enum _lpp_value_kind_t {
  64         lpp_none,
  65         lpp_value_start,
  66         lpp_value_solution,
  67 } lpp_value_kind_t;
  68
  69 typedef enum _lpp_emphasis_t {
  70         lpp_balanced,
  71         lpp_feasability,
  72         lpp_optimality,
  73         lpp_bestbound,
  74         lpp_hiddenfeasibility
  75 } lpp_emphasis_t;
  76
  77 typedef struct _name_t {
  78         const char *name;           /**< the name of the var/constraint supplied by user */
  79         int nr;                     /**< the col/row number in the matrix */
  80         lpp_value_kind_t value_kind;
  81         double value;
  82         union _type {
  83                 lpp_var_t var_type;
  84                 lpp_cst_t cst_type;
  85         } type;
  86 } lpp_name_t;
  87
  88 typedef struct _lpp_t {
  89         /* The problem data */
  90         const char     *name;            /**< A textual name for this problem */
  91         FILE           *log;             /**< The log file. */
  92         lpp_opt_t      opt_type;         /**< Optimization direction */
  93         struct obstack obst;             /**< Obstack for variable names */
  94         sp_matrix_t    *m;               /**< The matrix holding objective, constraints and rhs */
  95
  96         /* Cst/Var to Nr mapping */
  97         set *cst2nr;                     /**< Holds name_t's for constraints */
  98         set *var2nr;                     /**< Holds name_t's for variables */
  99
 100         /* Nr to Cst/Var mapping */
 101         int        cst_size, var_size;   /**< Size of the csts/vars-arrays below */
 102         int        cst_next, var_next;   /**< Next free position in arrays below */
 103         lpp_name_t **csts;               /**< Pointers to the elements in the cst2nr set */
 104         lpp_name_t **vars;               /**< Pointers to the elements in the var2nr set */
 105         double     objval;               /**< OUT: Value of the objective function. */
 106         double     best_bound;           /**< OUT: best bound to the integer solution. */
 107         double     grow_factor;          /**< The factor by which the vars and constraints are enlarged */
 108
 109         /* Solving options */
 110         int    set_bound;                /**< IN: Boolean flag to set a bound for the objective function. */
 111         double bound;                    /**< IN: The bound. Only valid if set_bound == 1. */
 112         double time_limit_secs;          /**< IN: Time limit to obey while solving (0.0 means no time limit) */
 113
 114         /* Solution stuff */
 115         lpp_sol_state_t sol_state;       /**< State of the solution */
 116         double          sol_time;        /**< Time in seconds */
 117         unsigned        iterations;      /**< Number of iterations CPLEX needed to solve the ILP (whatever this means) */
 118
 119         char           *error;
 120         unsigned       next_name_number; /**< for internal use only */
 121         lpp_emphasis_t emphasis;         /**< On what should CPLEX concentrate (feasibility, bestbound, ...) */
 122
 123         /* some statistic stuff */
 124         unsigned       send_time;        /**< in case of solve_net: send time in usec */
 125         unsigned       recv_time;        /**< in case of solve_net: recv time in usec */
 126         unsigned       n_elems;          /**< number of elements stored in the matrix */
 127         unsigned       matrix_mem;       /**< memory used by matrix elements (in bytes) */
 128         double         density;          /**< density of the matrix (percentage) */
 129 } lpp_t;
 130
 131 #define ERR_NAME_NOT_ALLOWED -2
 132
 133 /**
 134  * Creates a new problem. Optimization type is minimize or maximize.
 135  * Implicit row with name "obj" is inserted.
 136  * Implicit col with name "rhs" is inserted.
 137  */
 138 lpp_t *new_lpp(const char *name, lpp_opt_t opt_type);
 139
 140 /**
 141  * Creates a new problem. Optimization type is minimize or maximize.
 142  * Implicit row with name "obj" is inserted.
 143  * Implicit col with name "rhs" is inserted.
 144  * @param estimated_vars   The estimated number of variables for the problem
 145  * @param estimated_csts   The estimated number of constraints for the problem
 146  * @param grow_factor      By which factor should the problem grow, if there are
 147  *                         more variables or constraints than estimated.
 148  */
 149 lpp_t *new_lpp_userdef(const char *name, lpp_opt_t opt_type,
 150                                            int estimated_vars, int estimated_csts, double grow_factor);
 151
 152 /**
 153  * Frees the matrix embedded in the LPP.
 154  */
 155 void free_lpp_matrix(lpp_t *lpp);
 156
 157 /**
 158  * Frees all memory allocated for LPP data structure.
 159  */
 160 void free_lpp(lpp_t *lpp);
 161
 162 /**
 163  * @return The constant term in the objective function
 164  */
 165 double lpp_get_fix_costs(lpp_t *lpp);
 166
 167 /**
 168  * Sets the constant term in the objective function to @p value
 169  */
 170 void lpp_set_fix_costs(lpp_t *lpp, double value);
 171
 172 /**
 173  * Adds a constraint to a problem. If a constraint with the same name already
 174  * exists nothing is altered, and the index of the existing entry is returned.
 175  * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
 176  * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal
 177  * @param rhs The right hand side value to set for this constraint.
 178  * @return The (new or existing) index of the constraint
 179  */
 180 int lpp_add_cst(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs);
 181
 182 /**
 183  * Adds a constraint to a problem. If a constraint with the same name already
 184  * exists it dies a horribly cruel death
 185  * @param cst_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
 186  * @param cst_type The type of constraint: objective, equality, less-or-equal, greater-or-equal
 187  * @param rhs The right hand side value to set for this constraint.
 188  * @return The (new or existing) index of the constraint
 189  */
 190 int lpp_add_cst_uniq(lpp_t *lpp, const char *cst_name, lpp_cst_t cst_type, double rhs);
 191
 192 /**
 193  * Returns the internal index of a constraint.
 194  * @param cst_name The name of the constraint
 195  * @return The internal index of constraint @p cst_name or -1 if it does not exist.
 196  */
 197 int lpp_get_cst_idx(lpp_t *lpp, const char *cst_name);
 198
 199 /**
 200  * Returns the name of a constraint.
 201  * @param index The internal index of a constraint.
 202  * @param buf A buffer to hold the name of the constraint
 203  * @param buf_size Size of the buffer
 204  */
 205 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size);
 206
 207 /**
 208  * Adds a variable to a problem. If a variable with the same name already
 209  * exists nothing is altered, and the index of the existing entry is returned.
 210  * @param var_name The name of the constraint (1st char only alpha-numeric!). If NULL, a default name will be used.
 211  * @param var_type The type of variable: real, binary
 212  * @param obj The objective value coefficient for this variable.
 213  * @return The (new or existing) index of the variable
 214  *
 215  * NOTE: common integer or semi-continuous vars are not (yet) implemented
 216  */
 217 int lpp_add_var(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj);
 218
 219 /**
 220  * Same as lpp_add_var() but the user can supply a default value.
 221  */
 222 int lpp_add_var_default(lpp_t *lpp, const char *var_name, lpp_var_t var_type, double obj, double startval);
 223
 224 /**
 225  * Returns the internal index of a variable.
 226  * @param cst_name The name of the variable
 227  * @return The internal index of variable @p var_name or -1 if it does not exist.
 228  */
 229 int lpp_get_var_idx(lpp_t *lpp, const char *var_name);
 230
 231 /**
 232  * Returns the name of a variable.
 233  * @param index The internal index of a variable.
 234  * @param buf A buffer to hold the name of the variable
 235  * @param buf_size Size of the buffer
 236  */
 237 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size);
 238
 239 /**
 240  * Sets the factor of the variable @p var_name in constraint @p cst_name to @p value.
 241  * @return -1 if constraint or variable name does not exist.
 242  *          0 otherwise
 243  */
 244 int lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, double value);
 245
 246 /**
 247  * Same as lpp_set_factor but uses the internal indices instead of names.
 248  * @return -1 if an index was invalid
 249  *          0 otherwise
 250  */
 251 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value);
 252
 253 int lpp_set_factor_fast_bulk(lpp_t *lpp, int cst_idx, int *var_idx, int num_vars, double value);
 254
 255 /**
 256  * Set a starting value for a var.
 257  * @param var_idx The index of the variable to set the value for.
 258  * @param value The value to set.
 259  */
 260 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value);
 261
 262 /**
 263  * @return The solution values of the variables from index begin to index end.
 264  */
 265 lpp_sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end);
 266
 267 /**
 268  * Dumps the lpp into a file with name @p filename in MPS-format
 269  */
 270 void lpp_dump(lpp_t *lpp, const char *filename);
 271
 272 /**
 273  * Set the log file, where the solver should write to.
 274  * @param lpp The problem.
 275  * @param log The logfile. NULL for no logging.
 276  */
 277 void lpp_set_log(lpp_t *lpp, FILE *log);
 278
 279 /**
 280  * Check the start values and list conflicting constraints.
 281  */
 282 void lpp_check_startvals(lpp_t *lpp);
 283
 284 /**
 285  * Dump problem into a text file.
 286  * @param lpp The problem.
 287  * @param f   The file.
 288  */
 289 void lpp_dump_plain(lpp_t *lpp, FILE *f);
 290
 291 #define lpp_get_iter_cnt(lpp)         ((lpp)->iterations)
 292 #define lpp_get_sol_time(lpp)         ((lpp)->sol_time)
 293 #define lpp_get_sol_state(lpp)        ((lpp)->sol_state)
 294 #define lpp_get_var_count(lpp)        ((lpp)->var_next-1)
 295 #define lpp_get_cst_count(lpp)        ((lpp)->cst_next-1)
 296 #define lpp_get_sol_state(lpp)        ((lpp)->sol_state)
 297 #define lpp_get_var_sol(lpp,idx)      ((lpp)->vars[idx]->value)
 298 #define lpp_is_sol_valid(lpp)         (lpp_get_sol_state(lpp) >= lpp_feasible)
 299
 300 #define lpp_set_time_limit(lpp,secs)  ((lpp)->time_limit_secs = secs)
 301
 302 /**
 303  * Set a bound for the objective function.
 304  * @param lpp The problem.
 305  * @param bound A bound for the objective function.
 306  *              If the problem is a minimization problem, the bound
 307  *              is a lower bound. If it is a maximization problem,
 308  *              the bound is an upper bound.
 309  */
 310 #define lpp_set_bound(lpp,bnd)        ((lpp)->set_bound = 1, (lpp)->bound = (bnd))
 311
 312 /**
 313  * Clear a set bound.
 314  * @param lpp The problem.
 315  */
 316 #define lpp_unset_bound(lpp)          ((lpp)->set_bound = 0)
 317
 318 /**
 319  * Solve an ILP.
 320  * @param lpp    The problem.
 321  * @param host   The host to solve on.
 322  * @param solver The solver to use.
 323  */
 324 void lpp_solve(lpp_t *lpp, const char* host, const char* solver);
 325
 326 #endif