1 /* MIP_Problem Java class declaration and implementation. 2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it> 3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com) 4 5 This file is part of the Parma Polyhedra Library (PPL). 6 7 The PPL is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 3 of the License, or (at your 10 option) any later version. 11 12 The PPL is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software Foundation, 19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. 20 21 For the most up-to-date information see the Parma Polyhedra Library 22 site: http://bugseng.com/products/ppl/ . */ 23 24 25 package parma_polyhedra_library; 26 27 //! A Mixed Integer (linear) Programming problem. 28 /*! \ingroup PPL_Java_interface 29 An object of this class encodes a mixed integer (linear) programming problem. 30 The MIP problem is specified by providing: 31 - the dimension of the vector space; 32 - the feasible region, by means of a finite set of linear equality 33 and non-strict inequality constraints; 34 - the subset of the unknown variables that range over the integers 35 (the other variables implicitly ranging over the reals); 36 - the objective function, described by a Linear_Expression; 37 - the optimization mode (either maximization or minimization). 38 39 The class provides support for the (incremental) solution of the 40 MIP problem based on variations of the revised simplex method and 41 on branch-and-bound techniques. The result of the resolution 42 process is expressed in terms of an enumeration, encoding the 43 feasibility and the unboundedness of the optimization problem. 44 The class supports simple feasibility tests (i.e., no optimization), 45 as well as the extraction of an optimal (resp., feasible) point, 46 provided the MIP_Problem is optimizable (resp., feasible). 47 48 By exploiting the incremental nature of the solver, it is possible 49 to reuse part of the computational work already done when solving 50 variants of a given MIP_Problem: currently, incremental resolution 51 supports the addition of space dimensions, the addition of constraints, 52 the change of objective function and the change of optimization mode. 53 */ 54 public class MIP_Problem extends PPL_Object { 55 56 //! \name Constructors and Destructor 57 /*@{*/ 58 59 //! Builds a trivial MIP problem. 60 /*! 61 A trivial MIP problem requires to maximize the objective function 62 \f$0\f$ on a vector space under no constraints at all: 63 the origin of the vector space is an optimal solution. 64 65 \param dim 66 The dimension of the vector space enclosing \p this. 67 68 \exception Length_Error_Exception 69 Thrown if \p dim exceeds <CODE>max_space_dimension()</CODE>. 70 */ MIP_Problem(long dim)71 public MIP_Problem(long dim) { 72 build_cpp_object(dim); 73 } 74 75 /*! \brief 76 Builds an MIP problem having space dimension \p dim from the constraint 77 system \p cs, the objective function \p obj and optimization mode 78 \p mode. 79 80 \param dim 81 The dimension of the vector space enclosing \p this. 82 83 \param cs 84 The constraint system defining the feasible region. 85 86 \param obj 87 The objective function. 88 89 \param mode 90 The optimization mode. 91 92 \exception Length_Error_Exception 93 Thrown if \p dim exceeds <CODE>max_space_dimension()</CODE>. 94 95 \exception Invalid_Argument_Exception 96 Thrown if the constraint system contains any strict inequality 97 or if the space dimension of the constraint system (resp., the 98 objective function) is strictly greater than \p dim. 99 */ MIP_Problem(long dim, Constraint_System cs, Linear_Expression obj, Optimization_Mode mode)100 public MIP_Problem(long dim, Constraint_System cs, Linear_Expression obj, 101 Optimization_Mode mode) { 102 build_cpp_object(dim, cs, obj, mode); 103 } 104 105 //! Builds a copy of \p y. MIP_Problem(MIP_Problem y)106 public MIP_Problem(MIP_Problem y) { 107 build_cpp_object(y); 108 } 109 110 /*! \brief 111 Releases all resources managed by \p this, 112 also resetting it to a null reference. 113 */ free()114 public native void free(); 115 116 //! Releases all resources managed by \p this. finalize()117 protected native void finalize(); 118 119 /*@}*/ /* Constructors and Destructor */ 120 121 //! \name Functions that Do Not Modify the MIP_Problem 122 /*@{*/ 123 124 //! Returns the maximum space dimension an MIP_Problem can handle. max_space_dimension()125 public native long max_space_dimension(); 126 127 //! Returns the space dimension of the MIP problem. space_dimension()128 public native long space_dimension(); 129 130 /*! \brief 131 Returns a set containing all the variables' indexes constrained 132 to be integral. 133 */ integer_space_dimensions()134 public native Variables_Set integer_space_dimensions(); 135 136 //! Returns the constraints . constraints()137 public native Constraint_System constraints(); 138 139 //! Returns the objective function. objective_function()140 public native Linear_Expression objective_function(); 141 142 //! Returns the optimization mode. optimization_mode()143 public native Optimization_Mode optimization_mode(); 144 145 //! Returns an ascii formatted internal representation of \p this. ascii_dump()146 public native String ascii_dump(); 147 148 //! Returns a string representation of \p this. toString()149 public native String toString(); 150 151 /*! \brief 152 Returns the total size in bytes of the memory occupied by the 153 underlying C++ object. 154 */ total_memory_in_bytes()155 public native long total_memory_in_bytes(); 156 157 //! Checks if all the invariants are satisfied. OK()158 public native boolean OK(); 159 160 /*@}*/ /* Functions that Do Not Modify the MIP_Problem */ 161 162 //! \name Functions that May Modify the MIP_Problem 163 /*@{*/ 164 165 //! Resets \p this to be equal to the trivial MIP problem. 166 /*! 167 The space dimension is reset to \f$0\f$. 168 */ clear()169 public native void clear(); 170 171 /*! \brief 172 Adds \p m new space dimensions and embeds the old MIP problem 173 in the new vector space. 174 175 \param m 176 The number of dimensions to add. 177 178 \exception Length_Error_Exception 179 Thrown if adding \p m new space dimensions would cause the 180 vector space to exceed dimension <CODE>max_space_dimension()</CODE>. 181 182 The new space dimensions will be those having the highest indexes 183 in the new MIP problem; they are initially unconstrained. 184 */ add_space_dimensions_and_embed(long m)185 public native void add_space_dimensions_and_embed(long m); 186 187 /*! \brief 188 Sets the variables whose indexes are in set \p i_vars to be 189 integer space dimensions. 190 191 \exception Invalid_Argument_Exception 192 Thrown if some index in \p i_vars does not correspond to 193 a space dimension in \p this. 194 */ add_to_integer_space_dimensions(Variables_Set i_vars)195 public native void add_to_integer_space_dimensions(Variables_Set i_vars); 196 197 /*! \brief 198 Adds a copy of constraint \p c to the MIP problem. 199 200 \exception Invalid_Argument_Exception 201 Thrown if the constraint \p c is a strict inequality or if its space 202 dimension is strictly greater than the space dimension of \p this. 203 */ add_constraint(Constraint c)204 public native void add_constraint(Constraint c); 205 206 /*! \brief 207 Adds a copy of the constraints in \p cs to the MIP problem. 208 209 \exception Invalid_Argument_Exception 210 Thrown if the constraint system \p cs contains any strict inequality 211 or if its space dimension is strictly greater than the space dimension 212 of \p this. 213 */ add_constraints(Constraint_System cs)214 public native void add_constraints(Constraint_System cs); 215 216 //! Sets the objective function to \p obj. 217 /*! 218 \exception Invalid_Argument_Exception 219 Thrown if the space dimension of \p obj is strictly greater than 220 the space dimension of \p this. 221 */ set_objective_function(Linear_Expression obj)222 public native void set_objective_function(Linear_Expression obj); 223 224 //! Sets the optimization mode to \p mode. set_optimization_mode(Optimization_Mode mode)225 public native void set_optimization_mode(Optimization_Mode mode); 226 227 /*@}*/ /* Functions that May Modify the MIP_Problem */ 228 229 //! \name Computing the Solution of the MIP_Problem 230 /*@{*/ 231 232 //! Checks satisfiability of \p this. 233 /*! 234 \return 235 <CODE>true</CODE> if and only if the MIP problem is satisfiable. 236 */ is_satisfiable()237 public native boolean is_satisfiable(); 238 239 //! Optimizes the MIP problem. 240 /*! 241 \return 242 An MIP_Problem_Status flag indicating the outcome of the optimization 243 attempt (unfeasible, unbounded or optimized problem). 244 */ solve()245 public native MIP_Problem_Status solve(); 246 247 /*! \brief 248 Sets \p num and \p den so that \f$\frac{num}{den}\f$ is the result 249 of evaluating the objective function on \p evaluating_point. 250 251 \param evaluating_point 252 The point on which the objective function will be evaluated. 253 254 \param num 255 On exit will contain the numerator of the evaluated value. 256 257 \param den 258 On exit will contain the denominator of the evaluated value. 259 260 \exception Invalid_Argument_Exception 261 Thrown if \p this and \p evaluating_point are dimension-incompatible 262 or if the generator \p evaluating_point is not a point. 263 */ evaluate_objective_function(Generator evaluating_point, Coefficient num, Coefficient den)264 public native void evaluate_objective_function(Generator evaluating_point, 265 Coefficient num, 266 Coefficient den); 267 268 //! Returns a feasible point for \p this, if it exists. 269 /*! 270 \exception Domain_Error_Exception 271 Thrown if the MIP problem is not satisfiable. 272 */ feasible_point()273 public native Generator feasible_point(); 274 275 //! Returns an optimal point for \p this, if it exists. 276 /*! 277 \exception Domain_Error_Exception 278 Thrown if \p this doesn't not have an optimizing point, i.e., 279 if the MIP problem is unbounded or not satisfiable. 280 */ optimizing_point()281 public native Generator optimizing_point(); 282 283 /*! \brief 284 Sets \p num and \p den so that \f$\frac{num}{den}\f$ is 285 the solution of the optimization problem. 286 287 \exception Domain_Error_Exception 288 Thrown if \p this doesn't not have an optimizing point, i.e., 289 if the MIP problem is unbounded or not satisfiable. 290 */ optimal_value(Coefficient num, Coefficient den)291 public native void optimal_value(Coefficient num, Coefficient den); 292 293 /*@}*/ /* Computing the Solution of the MIP_Problem */ 294 295 //! \name Querying/Setting Control Parameters 296 /*@{*/ 297 298 /*! \brief 299 Returns the value of control parameter \p name. 300 */ 301 public native Control_Parameter_Value get_control_parameter(Control_Parameter_Name name)302 get_control_parameter(Control_Parameter_Name name); 303 304 /*! \brief 305 Sets control parameter \p value. 306 */ set_control_parameter(Control_Parameter_Value value)307 public native void set_control_parameter(Control_Parameter_Value value); 308 309 /*@}*/ /* Querying/Setting Control Parameters */ 310 311 //! Builds the underlying C++ object. build_cpp_object(long dim)312 private native void build_cpp_object(long dim); 313 314 //! Builds the underlying C++ object. build_cpp_object(long dim, Constraint_System cs, Linear_Expression obj, Optimization_Mode mode)315 private native void build_cpp_object(long dim, 316 Constraint_System cs, 317 Linear_Expression obj, 318 Optimization_Mode mode); 319 320 //! Builds the underlying C++ object. build_cpp_object(MIP_Problem y)321 private native void build_cpp_object(MIP_Problem y); 322 } 323