Sm_lps4_0_1_0 Class Reference

Solver module for lp_solve 4.0.1.0. More...

#include "Sm_lps4_0_1_0.h"

Inheritance diagram for Sm_lps4_0_1_0:

Collaboration diagram for Sm_lps4_0_1_0:

List of all members.

Static Public Member Functions

static double get_accuracy ()

Get accuracy used by lp_solve.

static const char * get_version ()

Get module version string.

static bool init (Report *report)

Initialize the module.

static void print_brief_version ()

Print brief module version.

static void print_options ()

Print supported options.

static void print_version ()

Print module version.

static bool read_lp (Lp *lp, FILE *in, const double relative_interval_radius, double &eta)

Read lp.

static void restore_dual (Lp *lp)

Restore lp after dual perturbation.

static void restore_primal (Lp *lp)

Restore lp after primal perturbation.

static bool set_lp (Lp *lp, const double relative_interval_radius, double &eta)

Set lp.

static bool set_module_options (Lp *lp, int argc, char *argv[])

Set module options.

static bool solve_dual_perturbed (const VECTOR &deflation_c, Lp *lp, const int iteration)

Compute solution of dual perturbed lp.

static bool solve_original (Lp *lp, double &optimal_value)

Compute solution of unperturbed lp.

static bool solve_primal_perturbed (const Primal_deflation &deflation, Lp *lp, const int iteration)

Compute solution of primal perturbed lp.

Static Private Member Functions

static void dual_perturb (const VECTOR &d_c, const Lp *lp)

Dual perturb lp.

static void WINAPI lps_log (void *lp, void *userhandle, char *buf)

Callback function for lp_solve's log messages.

static void postprocess (Lp *lp, const int status)

Postprocess lp.

static void primal_perturb (const Primal_deflation &d, const Lp *lp)

Primal perturb lp.

static bool read_duals (Lp *lp)

Read dual solution.

static bool read_primals (Lp *lp, const int cols)

Read primal solution.

static bool solve_lp (Lp *lp)

Solve lp with lp_solve.

Lp transforming routines

The following routines read the lp from the data structures of lp_solve 4.0.1.0 and transform it into Lurupa's representation.

static void adjust_eta (double &eta, const Lp *lp)

Adjust eta to the lp.

static bool build_constraint_maps (int &c_eq, int &c_le, const int rows, const int cols, Lp *lp)

Build mapping between lp_solve's and Lurupa's constraint structures.

static void find_free_variables (const int vars, Lp *lp)

Find free variables.

static void inflate_lp (Lp *lp, const double r)

Inflate lp parameters.

static void read_general_data (Lp *lp)

Read general data from lp_solve's structures.

static void read_lp_mat (const int rows, Lp *lp)

Read lp_solve's lp_mat structure.

static void read_right_hand_sides (Lp *lp)

Read right hand sides of the constraints.

static void read_simple_bounds (Lp *lp)

Read simple bounds.

static void resize_lp (Lp *lp, const int cols, const int c_eq, const int c_le)

Resize Lurupa's data structures according to the lp dimensions.

static bool transform_lp (Lp *lp, const double relative_interval_radius, double &eta)

Transform lp from lp_solve to Lurupa.

Detailed Description

Solver module for lp_solve 4.0.1.0.

Member Function Documentation

void Sm_lps4_0_1_0::adjust_eta	(	double &	eta,
		const Lp *	lp
	)			`[static, private]`

Adjust eta to the lp.

Adjust the algorithm parameter eta to be problem dependent. It becomes the maximum of its previous value and $10^{-20}$ times the maximum norm of the right hand sides of the inequality constraints,

$\eta = \max\{\eta, 10^{-20} \|a\|_{\infty}\}.$

Parameters:

`[out]`	eta	parameter to be adjusted
`[in]`	lp	lp `eta` is adjusted to

References Lp::ia, Solver_module::preport, and Report::print().

Referenced by transform_lp().

bool Sm_lps4_0_1_0::build_constraint_maps	(	int &	c_eq,
		int &	c_le,
		const int	rows,
		const int	cols,
		Lp *	lp
	)			`[static, private]`

Build mapping between lp_solve's and Lurupa's constraint structures.

Build a mapping from Lurupa's equality and inequality constraints to lp_solve's constraints, which is storing all constraints in one big matrix. Store the mapping in lp->module->mp_eq_con and lp->module->mp_le_con. Check if the number of constraints is less than the number of variables.

Parameters:

`[out]`	c_eq	number of equations in lp
`[out]`	c_le	number of inequalities in lp
`[in]`	rows	number of rows of constraint matrix
`[in]`	cols	number of columns of constraint matrix
`[in]`	lp	the lp

Return values:

	true	if number of constraints is less than number of variables,
	false	otherwise

References Lp_lp_solve::lp, Lp::module, Lp_lp_solve::mp_eq_con, Lp_lp_solve::mp_le_con, Solver_module::preport, and Report::print().

Referenced by transform_lp().

void Sm_lps4_0_1_0::dual_perturb	(	const VECTOR &	d_c,
		const Lp *	lp
	)			`[static, private]`

Dual perturb lp.

Perturb the lp in the cost vector.

Parameters:

`[in]`	d_c	deflation parameters
`[out]`	lp	contains the base for the deflation

References Lp::ic, Lp_lp_solve::lp, Lp::maximize, and Lp::module.

Referenced by solve_dual_perturbed().

void Sm_lps4_0_1_0::find_free_variables	(	const int	vars,
		Lp *	lp
	)			`[static, private]`

Find free variables.

Find free variables in the lp. Store the indices of the free variables in lp->free_variables and their number in lp->free_variables_size.

Parameters:

`[in]`	vars	number of variables in lp
`[out]`	lp	stores number and indices of the free variables

References Lp::free_variables, Lp::free_variables_size, Lp::infinite, and Lp::module.

Referenced by transform_lp().

double Sm_lps4_0_1_0::get_accuracy ( ) [static]

Get accuracy used by lp_solve.

Get lp_solve's set accuracy

Returns:: lp_solve's accuracy

Reimplemented from Solver_module.

Referenced by get_func_pointers().

const char * Sm_lps4_0_1_0::get_version ( ) [static]

Get module version string.

Get the version information of the solver module.

Reimplemented from Solver_module.

References version.

Referenced by get_func_pointers().

void Sm_lps4_0_1_0::inflate_lp	(	Lp *	lp,
		const double	r
	)			`[static, private]`

Inflate lp parameters.

Inflate all lp parameters to intervals with relative radius r,

$x \quad \rightarrow \quad \mathbf{x} \triangleq x \cdot [1-r, 1+r]$

Parameters:

`[out]`	lp	lp to be inflated
`[in]`	r	relative interval radius

References Lp::ia, Lp::IA, Lp::ib, Lp::IB, and Lp::ic.

Referenced by transform_lp().

bool Sm_lps4_0_1_0::init ( Report * report ) [static]

Initialize the module.

Set preport to *report. Check the version of lp_solve.

Parameters:

[in] report the Report instance to use

Return values:

true

Reimplemented from Solver_module.

References Solver_module::preport, Report::print(), and version.

Referenced by get_func_pointers().

void WINAPI Sm_lps4_0_1_0::lps_log	(	void *	lp,
		void *	userhandle,
		char *	buf
	)			`[static, private]`

Callback function for lp_solve's log messages.

Callback function for lp_solve's log functionality. Print the supplied log message marked as coming from lp_solve.

References Solver_module::preport, and Report::print().

Referenced by read_lp().

void Sm_lps4_0_1_0::postprocess	(	Lp *	lp,
		const int	status
	)			`[static, private]`

Postprocess lp.

Construct 'last feasible points' if status indicates that lp_solve judges lp->module->lp to be infeasible or unbounded. Postprocess the lp.

When lp_solve determines an lp to be infeasible or unbounded it does not store any information gathered in the simplex algorithm but discards it during the postprocessing. Deriving 'last feasible points' from this information may deliver rigorous bounds to support lp_solve's claim. Calling lp_solve's preprocessing routine explicitly, which does not alter the lp in a harmful way regarding the verification, causes lp_solve not to postprocess the lp after solving. This way the information in the simplex tableau is preserved.

Parameters:

`[in]`	lp	the lp
`[in]`	status	return value of lp_solve solving the lp

References Lp::module, Solver_module::preport, and Report::print().

Referenced by solve_lp().

void Sm_lps4_0_1_0::primal_perturb	(	const Primal_deflation &	d,
		const Lp *	lp
	)			`[static, private]`

Primal perturb lp.

Perturb the lp in the right hand sides of the inequalities and the simple bounds.

Parameters:

`[in]`	d	deflation parameters
`[out]`	lp	contains the base for the deflation

References Primal_deflation::a, Lp::ia, Lp_lp_solve::lp, Lp::module, Lp_lp_solve::mp_le_con, Lp::xl, Primal_deflation::xl, Lp::xu, and Primal_deflation::xu.

Referenced by solve_primal_perturbed().

void Sm_lps4_0_1_0::print_options ( ) [static]

Print supported options.

Print the command line options supported by the solver module.

Reimplemented from Solver_module.

References version.

Referenced by get_func_pointers().

bool Sm_lps4_0_1_0::read_duals ( Lp * lp ) [static, private]

Read dual solution.

Read the dual solution from lp_solve and store it in lp->iy and lp->iz. Lp_solve's convention to determine the sign of the duals is, that the costs must be a linear combination of the gradients of the constraints.

The duals returned by lp_solve, however, are the duals for the original lp, that is the duals for greater equal constraints are multiplied by $-1$ , and all duals are again multiplied by $-1$ if the lp is a maximizing one. As Lurupa stores all linear programs as minimizing and all inequality constraints as less equal undo these multiplications.

Parameters:

[out] lp receives the dual solution

Return values:

	true	if reading the dual solution succeeded,
	false	otherwise, calling lp_solve's `get_sensitivity_rhs` returns false

References Lp::iy, Lp::iz, Lp_lp_solve::lp, Lp::maximize, Lp::module, Lp_lp_solve::mp_eq_con, Lp_lp_solve::mp_le_con, Solver_module::preport, and Report::print().

Referenced by solve_dual_perturbed(), and solve_original().

void Sm_lps4_0_1_0::read_general_data ( Lp * lp ) [static, private]

Read general data from lp_solve's structures.

Read general lp properties from lp_solve's structures and store them in lp. This includes the value representing infinity, the direction of optimization, and the name of the lp.

Parameters:

[out] lp stores the read data

References Lp::infinite, Lp::maximize, Lp::module, and Lp::name.

Referenced by transform_lp().

bool Sm_lps4_0_1_0::read_lp	(	Lp *	lp,
		FILE *	in,
		const double	relative_interval_radius,
		double &	eta
	)			`[static]`

Read lp.

Read an lp from a file into lp_solve and lp. Inflate the lp to an interval valued one if relative_interval_radius is greater than 0, and adjust eta according to the lp's parameters.

Parameters:

`[out]`	lp	receives the lp
`[in]`	in	file pointer to lp
`[in]`	relative_interval_radius	nterval radius to inflate lp parameters to
`[out]`	eta	algorithm parameter to be adjusted

Return values:

	true	if reading and transforming the lp succeeds,
	false	otherwise, reading the lp fails or `transform_lp` returns false

See also:: transform_lp

Reimplemented from Solver_module.

References Lp_lp_solve::lp, lps_log(), Lp::module, and transform_lp().

Referenced by get_func_pointers().

void Sm_lps4_0_1_0::read_lp_mat	(	const int	rows,
		Lp *	lp
	)			`[static, private]`

Read lp_solve's lp_mat structure.

Read lp_solve's lp_mat structure. This stores the left hand sides of the constraints together with the objective function. Split the read coefficients into equality and inequality constraints, transform inequality constraints to all less equal, and the direction of optimization to minimize.

Parameters:

`[in]`	rows	number of rows in constraint matrix
`[out]`	lp	stores the constraints and objective function

References Lp::IA, Lp::IB, Lp::ic, Lp_lp_solve::lp, Lp::maximize, Lp::module, Lp_lp_solve::mp_eq_con, and Lp_lp_solve::mp_le_con.

Referenced by transform_lp().

bool Sm_lps4_0_1_0::read_primals	(	Lp *	lp,
		const int	cols
	)			`[static, private]`

Read primal solution.

Read the primal solution from lp_solve and store it in lp->ix.

Parameters:

`[out]`	lp	receives the primal solution
`[in]`	cols	number of variables in the lp

Return values:

	true	if reading the primal solution succeeds,
	false	otherwise, calling lp_solve's `get_variables` returns false

References Lp::ic, Lp::ix, Lp_lp_solve::lp, Lp::module, Solver_module::preport, and Report::print().

Referenced by solve_original(), and solve_primal_perturbed().

void Sm_lps4_0_1_0::read_right_hand_sides ( Lp * lp ) [static, private]

Read right hand sides of the constraints.

Read the right hand sides of the constraints. Split the read right hand sides into equality and inequality constraints, transform inequality constraints to all less equal. Store the values in lp->ia and lp->ib.

Parameters:

[out] lp stores the right hand sides

References Lp::ia, Lp::ib, Lp_lp_solve::lp, Lp::module, Lp_lp_solve::mp_eq_con, and Lp_lp_solve::mp_le_con.

Referenced by transform_lp().

void Sm_lps4_0_1_0::read_simple_bounds ( Lp * lp ) [static, private]

Read simple bounds.

Read the simple bounds of the variables and store them in lp->xl and lp->xu.

Parameters:

[out] lp stores the simple bounds

References Lp::module, Lp::non_fixed_vars, Lp::xl, and Lp::xu.

Referenced by transform_lp().

void Sm_lps4_0_1_0::resize_lp	(	Lp *	lp,
		const int	cols,
		const int	c_eq,
		const int	c_le
	)			`[static, private]`

Resize Lurupa's data structures according to the lp dimensions.

Resize the vectors and matrices in Lurupa's data structure to the sizes of the lp.

Parameters:

`[out]`	lp	Lurupa's structure with the vectors and matrices to be resized
`[in]`	cols	number of variables in the lp
`[in]`	c_eq	number of equality constraints in the lp
`[in]`	c_le	number of inequality constraints in the lp

References Lp::ia, Lp::IA, Lp::ib, Lp::IB, Lp::ic, Lp::ix, Lp::iy, Lp::iz, Lp::xl, and Lp::xu.

Referenced by transform_lp().

void Sm_lps4_0_1_0::restore_dual ( Lp * lp ) [static]

Restore lp after dual perturbation.

Take the model parameters for the costs from lp and write to lp->module->lp restoring the original model after computation of the lower bound.

Parameters:

[in] lp contains the original parameters

Reimplemented from Solver_module.

References Lp::ic, Lp::maximize, Lp::module, Solver_module::preport, and Report::print().

Referenced by get_func_pointers().

void Sm_lps4_0_1_0::restore_primal ( Lp * lp ) [static]

Restore lp after primal perturbation.

Take the model parameters for the right hand sides and the simple bounds from lp and write to lp->module->lp restoring the original model after computation of the upper bound.

Parameters:

[in] lp contains the original parameters

Reimplemented from Solver_module.

References Lp::ia, Lp::IA, Lp_lp_solve::lp, Lp::module, Lp_lp_solve::mp_le_con, Solver_module::preport, Report::print(), Lp::xl, and Lp::xu.

Referenced by get_func_pointers().

bool Sm_lps4_0_1_0::set_module_options	(	Lp *	lp,
		int	argc,
		char *	argv[]
	)			`[static]`

Set module options.

Set the specified module options. These are supplied in argc and argv in a command line version. Each option is supplied as one string entry in the string array argv, argc specifies the number of options.

The module supports the following options

'-sm,timeout,n': Set lp_solve's timeout to n seconds.
'-sm,vn': Set lp_solve's verbosity level to n. The available levels are
- v0 NEUTRAL
- v1 CRITICAL
- v2 SEVERE
- v3 IMPORTANT (default)
- v4 NORMAL
- v5 DETAILED
- v6 FULL

Parameters:

`[out]`	lp	lp to set the options for
`[in]`	argc	number of arguments
`[in]`	argv	array of arguments

Return values:

	true	if options are set
	false	otherwise

References Lp::module, Solver_module::preport, and Report::print().

Referenced by get_func_pointers().

bool Sm_lps4_0_1_0::solve_dual_perturbed	(	const VECTOR &	d_c,
		Lp *	lp,
		const int	iteration
	)			`[static]`

Compute solution of dual perturbed lp.

Perturb the lp and solve the new one. Read the dual solution from lp_solve and store it in lp->iy and lp->iz.

Parameters:

`[in]`	d_c	deflation parameter
`[out]`	lp	receives the solver status and the dual solution
`[in]`	iteration	number of the current iteration

Return values:

	true	if `solve_lp` returns true and the solution is read
	false	otherwise, `solve_lp` or `read_duals` returns false

See also:: read_duals, solve_lp

Reimplemented from Solver_module.

References dual_perturb(), Lp::feasibility, Solver_module::preport, Report::print(), read_duals(), solve_lp(), ss_feasible, and ss_infeasible.

Referenced by get_func_pointers().

bool Sm_lps4_0_1_0::solve_lp ( Lp * lp ) [static, private]

Solve lp with lp_solve.

Solve an lp with lp_solve. Store lp_solve's status in lp->feasibility.

Parameters:

[out] lp receives lp_solve's status

Return values:

	true	if lp_solve returns a known status code (i.e., OPTIMAL, INFEASIBLE, UNBOUNDED, TIMEOUT, or FAILURE)
	false	otherwise

References Lp::feasibility, Lp::module, postprocess(), Solver_module::preport, Report::print(), ss_failure, ss_feasible, ss_infeasible, ss_timeout, and ss_unbounded.

Referenced by solve_dual_perturbed(), solve_original(), and solve_primal_perturbed().

bool Sm_lps4_0_1_0::solve_original	(	Lp *	lp,
		double &	optimal_value
	)			`[static]`

Compute solution of unperturbed lp.

Solve the original unperturbed lp with lp_solve and read the primal and dual solution.

Parameters:

`[out]`	lp	receives the solver status and the solution
`[out]`	optimal_value	receives the optimal value

Return values:

	true	if `solve_lp` returns true and the solution is read
	false	otherwise, `solve_lp`, `read_primals`, or `read_duals` returns false

See also:: read_duals, read_primals, solve_lp

Reimplemented from Solver_module.

References Lp::module, Solver_module::preport, Report::print(), read_duals(), read_primals(), and solve_lp().

Referenced by get_func_pointers().

bool Sm_lps4_0_1_0::solve_primal_perturbed	(	const Primal_deflation &	d,
		Lp *	lp,
		const int	iteration
	)			`[static]`

Compute solution of primal perturbed lp.

Perturb the lp and solve the new one. Read the primal solution and store it in lp->ix.

Parameters:

`[in]`	d	deflation parameters
`[out]`	lp	receives the solver status and the primal solution
`[in]`	iteration	number of the current iteration

Return values:

	true	if `solve_lp` returns true and the solution is read
	false	otherwise, `solve_lp` or `read_primals` returns false

See also:: read_primals, solve_lp

Reimplemented from Solver_module.

References Lp::feasibility, Lp::module, Solver_module::preport, primal_perturb(), Report::print(), read_primals(), solve_lp(), ss_feasible, and ss_unbounded.

Referenced by get_func_pointers().

bool Sm_lps4_0_1_0::transform_lp	(	Lp *	lp,
		const double	relative_interval_radius,
		double &	eta
	)			`[static, private]`

Transform lp from lp_solve to Lurupa.

Transform lp from the data structure of lp_solve 4.0.1.0 into the representation used in Lurupa. Adjust algorithm parameters eta according to the lp, and inflate the lp to an interval valued one if relative_interval_radius is greater than 0.

Write the (midpoint) problem with preport if Report::write_vm is set.

Parameters:

`[out]`	lp	receives the transformed data
`[in]`	relative_interval_radius	relative interval radius to inflate lp parameters to
`[out]`	eta	gets adjusted to the model

Return values:

	true	if the transformation succeeds,
	false	otherwise, `lp->module->lp` is not set or `build_constraint_maps` returns false

See also:: adjust_eta, build_constraint_maps, find_free_variables, inflate_lp, read_general_data, read_lp_mat, read_right_hand_sides, read_simple_bounds, resize_lp

References adjust_eta(), build_constraint_maps(), find_free_variables(), Lp::free_variables_size, Report::get_write_vm(), Lp::ia, Lp::IA, Lp::ib, Lp::IB, Lp::ic, inflate_lp(), Lp::module, Lp::name, Solver_module::preport, Report::print(), read_general_data(), read_lp_mat(), read_right_hand_sides(), read_simple_bounds(), resize_lp(), Report::write_matrix(), Report::write_vector(), Lp::xl, and Lp::xu.

Referenced by read_lp(), and set_lp().

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


Static Public Member Functions
static double	get_accuracy ()
	Get accuracy used by lp_solve.
static const char *	get_version ()
	Get module version string.
static bool	init (Report *report)
	Initialize the module.
static void	print_brief_version ()
	Print brief module version.
static void	print_options ()
	Print supported options.
static void	print_version ()
	Print module version.
static bool	read_lp (Lp lp, FILE in, const double relative_interval_radius, double &eta)
	Read lp.
static void	restore_dual (Lp *lp)
	Restore lp after dual perturbation.
static void	restore_primal (Lp *lp)
	Restore lp after primal perturbation.
static bool	set_lp (Lp *lp, const double relative_interval_radius, double &eta)
	Set lp.
static bool	set_module_options (Lp lp, int argc, char argv[])
	Set module options.
static bool	solve_dual_perturbed (const VECTOR &deflation_c, Lp *lp, const int iteration)
	Compute solution of dual perturbed lp.
static bool	solve_original (Lp *lp, double &optimal_value)
	Compute solution of unperturbed lp.
static bool	solve_primal_perturbed (const Primal_deflation &deflation, Lp *lp, const int iteration)
	Compute solution of primal perturbed lp.
Static Private Member Functions
static void	dual_perturb (const VECTOR &d_c, const Lp *lp)
	Dual perturb lp.
static void WINAPI	lps_log (void lp, void userhandle, char *buf)
	Callback function for lp_solve's log messages.
static void	postprocess (Lp *lp, const int status)
	Postprocess lp.
static void	primal_perturb (const Primal_deflation &d, const Lp *lp)
	Primal perturb lp.
static bool	read_duals (Lp *lp)
	Read dual solution.
static bool	read_primals (Lp *lp, const int cols)
	Read primal solution.
static bool	solve_lp (Lp *lp)
	Solve lp with lp_solve.
Lp transforming routines
The following routines read the lp from the data structures of lp_solve 4.0.1.0 and transform it into Lurupa's representation.
static void	adjust_eta (double &eta, const Lp *lp)
	Adjust eta to the lp.
static bool	build_constraint_maps (int &c_eq, int &c_le, const int rows, const int cols, Lp *lp)
	Build mapping between lp_solve's and Lurupa's constraint structures.
static void	find_free_variables (const int vars, Lp *lp)
	Find free variables.
static void	inflate_lp (Lp *lp, const double r)
	Inflate lp parameters.
static void	read_general_data (Lp *lp)
	Read general data from lp_solve's structures.
static void	read_lp_mat (const int rows, Lp *lp)
	Read lp_solve's lp_mat structure.
static void	read_right_hand_sides (Lp *lp)
	Read right hand sides of the constraints.
static void	read_simple_bounds (Lp *lp)
	Read simple bounds.
static void	resize_lp (Lp *lp, const int cols, const int c_eq, const int c_le)
	Resize Lurupa's data structures according to the lp dimensions.
static bool	transform_lp (Lp *lp, const double relative_interval_radius, double &eta)
	Transform lp from lp_solve to Lurupa.