Sm_lps3_2 Class Reference

Solver module for lp_solve 3.2. More...

#include "Sm_lps3_2.h"

Inheritance diagram for Sm_lps3_2:

Collaboration diagram for Sm_lps3_2:

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 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 primal_perturb (const Primal_deflation &d, const Lp *lp)

Primal perturb lp.

static void read_duals (Lp *lp)

Read dual solution.

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

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 3.2 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 (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, const int rows)

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 3.2.

Member Function Documentation

void Sm_lps3_2::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_lps3_2::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_lps3_2::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, Lp::module, and Lp_lp_solve::mp_parts.

Referenced by solve_dual_perturbed().

void Sm_lps3_2::find_free_variables	(	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.

Adjust the number of variables vars to reflect the actual count of variables and not include the split variables used in lp_solve to represent free variables.

Parameters:

`[in,out]`	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_lp_solve::lp, Lp::module, and Lp_lp_solve::mp_parts.

Referenced by transform_lp().

double Sm_lps3_2::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_lps3_2::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_lps3_2::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_lps3_2::init ( Report * report ) [static]

Initialize the module.

Set preport to *report.

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 Sm_lps3_2::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_lp_solve::mp_parts, Lp::xl, Primal_deflation::xl, Lp::xu, and Primal_deflation::xu.

Referenced by solve_primal_perturbed().

void Sm_lps3_2::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().

void Sm_lps3_2::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

References Lp::feasibility, Lp::iy, Lp::iz, Lp_lp_solve::lp, Lp::maximize, Lp::module, Lp_lp_solve::mp_eq_con, Lp_lp_solve::mp_le_con, and ss_infeasible.

Referenced by solve_dual_perturbed(), and solve_original().

void Sm_lps3_2::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_lps3_2::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	interval 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, `transform_lp` returns false

See also:: transform_lp

Reimplemented from Solver_module.

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

Referenced by get_func_pointers().

void Sm_lps3_2::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, Lp_lp_solve::mp_le_con, and Lp_lp_solve::mp_parts.

Referenced by transform_lp().

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

Read primal solution.

Read the primal solution from lp_solve and store it in lp->ix. If the lp seems to be unbounded construct the last primal feasible point and read this. Join the solution parts of split variables.

Parameters:

`[out]`	lp	receives the primal solution
`[in]`	rows	number of rows in constraint matrix

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

Referenced by solve_original(), and solve_primal_perturbed().

void Sm_lps3_2::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, Lp_lp_solve::mp_le_con, Solver_module::preport, and Report::print().

Referenced by transform_lp().

void Sm_lps3_2::read_simple_bounds	(	Lp *	lp,
		const int	rows
	)			`[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
`[in]`	rows	number of rows in lp_solve's constraint matrix

References Lp::infinite, Lp_lp_solve::lp, Lp::module, Lp_lp_solve::mp_parts, Lp::non_fixed_vars, Lp::xl, and Lp::xu.

Referenced by transform_lp().

void Sm_lps3_2::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_lps3_2::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_lp_solve::lp, Lp::maximize, Lp::module, Lp_lp_solve::mp_parts, Solver_module::preport, and Report::print().

Referenced by get_func_pointers().

void Sm_lps3_2::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, Lp_lp_solve::mp_parts, Solver_module::preport, Report::print(), Lp::xl, and Lp::xu.

Referenced by get_func_pointers().

bool Sm_lps3_2::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` returns false

See also:: 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_lps3_2::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, or FAILURE)
	false	otherwise

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

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

bool Sm_lps3_2::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` 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_lps3_2::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` returns false

See also:: 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_lps3_2::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 3.2 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	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	primal_perturb (const Primal_deflation &d, const Lp *lp)
	Primal perturb lp.
static void	read_duals (Lp *lp)
	Read dual solution.
static void	read_primals (Lp *lp, const int rows)
	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 3.2 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 (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, const int rows)
	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.