A Mixed Integer (linear) Programming problem. More...

Inheritance diagram for parma_polyhedra_library.MIP_Problem:

Collaboration diagram for parma_polyhedra_library.MIP_Problem:

Public Member Functions
Functions that Do Not Modify the MIP_Problem
native long	max_space_dimension ()
	Returns the maximum space dimension an MIP_Problem can handle. More...

native long	space_dimension ()
	Returns the space dimension of the MIP problem. More...

native Variables_Set	integer_space_dimensions ()
	Returns a set containing all the variables' indexes constrained to be integral. More...

native Constraint_System	constraints ()
	Returns the constraints . More...

native Linear_Expression	objective_function ()
	Returns the objective function. More...

native Optimization_Mode	optimization_mode ()
	Returns the optimization mode. More...

native String	ascii_dump ()
	Returns an ascii formatted internal representation of `this`. More...

native String	toString ()
	Returns a string representation of `this`. More...

native long	total_memory_in_bytes ()
	Returns the total size in bytes of the memory occupied by the underlying C++ object. More...

native boolean	OK ()
	Checks if all the invariants are satisfied. More...

Functions that May Modify the MIP_Problem
native void	clear ()
	Resets `this` to be equal to the trivial MIP problem. More...

native void	add_space_dimensions_and_embed (long m)
	Adds `m` new space dimensions and embeds the old MIP problem in the new vector space. More...

native void	add_to_integer_space_dimensions (Variables_Set i_vars)
	Sets the variables whose indexes are in set `i_vars` to be integer space dimensions. More...

native void	add_constraint (Constraint c)
	Adds a copy of constraint `c` to the MIP problem. More...

native void	add_constraints (Constraint_System cs)
	Adds a copy of the constraints in `cs` to the MIP problem. More...

native void	set_objective_function (Linear_Expression obj)
	Sets the objective function to `obj`. More...

native void	set_optimization_mode (Optimization_Mode mode)
	Sets the optimization mode to `mode`. More...

Computing the Solution of the MIP_Problem
native boolean	is_satisfiable ()
	Checks satisfiability of `this`. More...

native MIP_Problem_Status	solve ()
	Optimizes the MIP problem. More...

native void	evaluate_objective_function (Generator evaluating_point, Coefficient num, Coefficient den)
	Sets `num` and `den` so that $\frac{num}{den}$ is the result of evaluating the objective function on `evaluating_point`. More...

native Generator	feasible_point ()
	Returns a feasible point for `this`, if it exists. More...

native Generator	optimizing_point ()
	Returns an optimal point for `this`, if it exists. More...

native void	optimal_value (Coefficient num, Coefficient den)
	Sets `num` and `den` so that $\frac{num}{den}$ is the solution of the optimization problem. More...

Querying/Setting Control Parameters
native Control_Parameter_Value	get_control_parameter (Control_Parameter_Name name)
	Returns the value of control parameter `name`. More...

native void	set_control_parameter (Control_Parameter_Value value)
	Sets control parameter `value`. More...

Private Member Functions
native void	build_cpp_object (long dim)
	Builds the underlying C++ object. More...

native void	build_cpp_object (long dim, Constraint_System cs, Linear_Expression obj, Optimization_Mode mode)
	Builds the underlying C++ object. More...

native void	build_cpp_object (MIP_Problem y)
	Builds the underlying C++ object. More...

Constructors and Destructor
	MIP_Problem (long dim)
	Builds a trivial MIP problem. More...

	MIP_Problem (long dim, Constraint_System cs, Linear_Expression obj, Optimization_Mode mode)
	Builds an MIP problem having space dimension `dim` from the constraint system `cs`, the objective function `obj` and optimization mode `mode`. More...

	MIP_Problem (MIP_Problem y)
	Builds a copy of `y`. More...

native void	free ()
	Releases all resources managed by `this`, also resetting it to a null reference. More...

native void	finalize ()
	Releases all resources managed by `this`. More...

Additional Inherited Members
Protected Member Functions inherited from parma_polyhedra_library.PPL_Object
	PPL_Object ()
	Builds an object that points to `null'. More...

Detailed Description

A Mixed Integer (linear) Programming problem.

An object of this class encodes a mixed integer (linear) programming problem. The MIP problem is specified by providing:

the dimension of the vector space;
the feasible region, by means of a finite set of linear equality and non-strict inequality constraints;
the subset of the unknown variables that range over the integers (the other variables implicitly ranging over the reals);
the objective function, described by a Linear_Expression;
the optimization mode (either maximization or minimization).

The class provides support for the (incremental) solution of the MIP problem based on variations of the revised simplex method and on branch-and-bound techniques. The result of the resolution process is expressed in terms of an enumeration, encoding the feasibility and the unboundedness of the optimization problem. The class supports simple feasibility tests (i.e., no optimization), as well as the extraction of an optimal (resp., feasible) point, provided the MIP_Problem is optimizable (resp., feasible).

By exploiting the incremental nature of the solver, it is possible to reuse part of the computational work already done when solving variants of a given MIP_Problem: currently, incremental resolution supports the addition of space dimensions, the addition of constraints, the change of objective function and the change of optimization mode.

Definition at line 54 of file MIP_Problem.java.

Constructor & Destructor Documentation

parma_polyhedra_library.MIP_Problem.MIP_Problem ( long dim )

inline

Builds a trivial MIP problem.

A trivial MIP problem requires to maximize the objective function $0$ on a vector space under no constraints at all: the origin of the vector space is an optimal solution.

Parameters

dim	The dimension of the vector space enclosing `this`.

Exceptions

Length_Error_Exception Thrown if dim exceeds max_space_dimension().

Definition at line 71 of file MIP_Problem.java.

References parma_polyhedra_library.MIP_Problem.build_cpp_object().

parma_polyhedra_library.MIP_Problem.MIP_Problem	(	long	dim,
		Constraint_System	cs,
		Linear_Expression	obj,
		Optimization_Mode	mode
	)

inline

Builds an MIP problem having space dimension dim from the constraint system cs, the objective function obj and optimization mode mode.

Parameters

dim	The dimension of the vector space enclosing `this`.
cs	The constraint system defining the feasible region.
obj	The objective function.
mode	The optimization mode.

Exceptions

Length_Error_Exception	Thrown if `dim` exceeds `max_space_dimension()`.
Invalid_Argument_Exception	Thrown if the constraint system contains any strict inequality or if the space dimension of the constraint system (resp., the objective function) is strictly greater than `dim`.

Definition at line 100 of file MIP_Problem.java.

References parma_polyhedra_library.MIP_Problem.build_cpp_object().

parma_polyhedra_library.MIP_Problem.MIP_Problem ( MIP_Problem y )

inline

Builds a copy of y.

Definition at line 106 of file MIP_Problem.java.

References parma_polyhedra_library.MIP_Problem.build_cpp_object().

Member Function Documentation

native void parma_polyhedra_library.MIP_Problem.add_constraint ( Constraint c )

Adds a copy of constraint c to the MIP problem.

Exceptions

Invalid_Argument_Exception Thrown if the constraint c is a strict inequality or if its space dimension is strictly greater than the space dimension of this.

native void parma_polyhedra_library.MIP_Problem.add_constraints ( Constraint_System cs )

Adds a copy of the constraints in cs to the MIP problem.

Exceptions

Invalid_Argument_Exception Thrown if the constraint system cs contains any strict inequality or if its space dimension is strictly greater than the space dimension of this.

native void parma_polyhedra_library.MIP_Problem.add_space_dimensions_and_embed ( long m )

Adds m new space dimensions and embeds the old MIP problem in the new vector space.

Parameters

m	The number of dimensions to add.

Exceptions

Length_Error_Exception Thrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension().

The new space dimensions will be those having the highest indexes in the new MIP problem; they are initially unconstrained.

native void parma_polyhedra_library.MIP_Problem.add_to_integer_space_dimensions ( Variables_Set i_vars )

Sets the variables whose indexes are in set i_vars to be integer space dimensions.

Exceptions

Invalid_Argument_Exception Thrown if some index in i_vars does not correspond to a space dimension in this.

native String parma_polyhedra_library.MIP_Problem.ascii_dump ( )

Returns an ascii formatted internal representation of this.

native void parma_polyhedra_library.MIP_Problem.build_cpp_object ( long dim )

private

Builds the underlying C++ object.

Referenced by parma_polyhedra_library.MIP_Problem.MIP_Problem().

native void parma_polyhedra_library.MIP_Problem.build_cpp_object	(	long	dim,
		Constraint_System	cs,
		Linear_Expression	obj,
		Optimization_Mode	mode
	)

private

Builds the underlying C++ object.

native void parma_polyhedra_library.MIP_Problem.build_cpp_object ( MIP_Problem y )

private

Builds the underlying C++ object.

native void parma_polyhedra_library.MIP_Problem.clear ( )

Resets this to be equal to the trivial MIP problem.

The space dimension is reset to $0$ .

native Constraint_System parma_polyhedra_library.MIP_Problem.constraints ( )

Returns the constraints .

native void parma_polyhedra_library.MIP_Problem.evaluate_objective_function	(	Generator	evaluating_point,
		Coefficient	num,
		Coefficient	den
	)

Sets num and den so that $\frac{num}{den}$ is the result of evaluating the objective function on evaluating_point.

Parameters

evaluating_point	The point on which the objective function will be evaluated.
num	On exit will contain the numerator of the evaluated value.
den	On exit will contain the denominator of the evaluated value.

Exceptions

Invalid_Argument_Exception Thrown if this and evaluating_point are dimension-incompatible or if the generator evaluating_point is not a point.

native Generator parma_polyhedra_library.MIP_Problem.feasible_point ( )

Returns a feasible point for this, if it exists.

Exceptions

Domain_Error_Exception Thrown if the MIP problem is not satisfiable.

native void parma_polyhedra_library.MIP_Problem.finalize ( )

protected

Releases all resources managed by this.

native void parma_polyhedra_library.MIP_Problem.free ( )

Releases all resources managed by this, also resetting it to a null reference.

native Control_Parameter_Value parma_polyhedra_library.MIP_Problem.get_control_parameter ( Control_Parameter_Name name )

Returns the value of control parameter name.

native Variables_Set parma_polyhedra_library.MIP_Problem.integer_space_dimensions ( )

Returns a set containing all the variables' indexes constrained to be integral.

native boolean parma_polyhedra_library.MIP_Problem.is_satisfiable ( )

Checks satisfiability of this.

Returns: true if and only if the MIP problem is satisfiable.

native long parma_polyhedra_library.MIP_Problem.max_space_dimension ( )

Returns the maximum space dimension an MIP_Problem can handle.

native Linear_Expression parma_polyhedra_library.MIP_Problem.objective_function ( )

Returns the objective function.

native boolean parma_polyhedra_library.MIP_Problem.OK ( )

Checks if all the invariants are satisfied.

native void parma_polyhedra_library.MIP_Problem.optimal_value	(	Coefficient	num,
		Coefficient	den
	)

Sets num and den so that $\frac{num}{den}$ is the solution of the optimization problem.

Exceptions

Domain_Error_Exception Thrown if this doesn't not have an optimizing point, i.e., if the MIP problem is unbounded or not satisfiable.

native Optimization_Mode parma_polyhedra_library.MIP_Problem.optimization_mode ( )

Returns the optimization mode.

native Generator parma_polyhedra_library.MIP_Problem.optimizing_point ( )

Returns an optimal point for this, if it exists.

Exceptions

Domain_Error_Exception Thrown if this doesn't not have an optimizing point, i.e., if the MIP problem is unbounded or not satisfiable.

native void parma_polyhedra_library.MIP_Problem.set_control_parameter ( Control_Parameter_Value value )

Sets control parameter value.

native void parma_polyhedra_library.MIP_Problem.set_objective_function ( Linear_Expression obj )

Sets the objective function to obj.

Exceptions

Invalid_Argument_Exception Thrown if the space dimension of obj is strictly greater than the space dimension of this.

native void parma_polyhedra_library.MIP_Problem.set_optimization_mode ( Optimization_Mode mode )

Sets the optimization mode to mode.

native MIP_Problem_Status parma_polyhedra_library.MIP_Problem.solve ( )

Optimizes the MIP problem.

Returns: An MIP_Problem_Status flag indicating the outcome of the optimization attempt (unfeasible, unbounded or optimized problem).

native long parma_polyhedra_library.MIP_Problem.space_dimension ( )

Returns the space dimension of the MIP problem.

native String parma_polyhedra_library.MIP_Problem.toString ( )

Returns a string representation of this.

native long parma_polyhedra_library.MIP_Problem.total_memory_in_bytes ( )

Returns the total size in bytes of the memory occupied by the underlying C++ object.

The documentation for this class was generated from the following file:

MIP_Problem.java

Public Member Functions

Private Member Functions

Constructors and Destructor

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation