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