This module provides makers to construct a program, as well as functions to solve and print programs.

In case you want to construct a program from complicated iterators (whose types you don't know, or simply don't want to bother with), we provide four makers.

There are four functions to solve a program, one for each program concept.

The solution process can customized by passing an object of the class

CGAL::Quadratic_program_options

Programs can be written to an output stream in MPSFormat, using one of the following four functions.

Classes
class	CGAL::Quadratic_program_options
	This is a class used for passing options to the linear and quadratic programming solvers. More...

Enumerations
enum	CGAL::Quadratic_program_pricing_strategy { CGAL::QP_CHOOSE_DEFAULT, CGAL::QP_PARTIAL_DANTZIG, CGAL::QP_DANTZIG, CGAL::QP_PARTIAL_FILTERED_DANTZIG, CGAL::QP_FILTERED_DANTZIG, CGAL::QP_BLAND }
	This is an enumeration type containing the values `QP_CHOOSE_DEFAULT`, `QP_DANTZIG`, `QP_PARTIAL_DANTZIG`, `QP_FILTERED_DANTZIG`, `QP_PARTIAL_FILTERED_DANTZIG`, and`QP_BLAND`. More...

Functions
template<LinearProgram >
void	CGAL::print_linear_program (std::ostream &out, const LinearProgram &lp, const std::string &problem_name=std::string("MY_MPS"))
	This function writes a linear program to an output stream (in `MPSFormat`). More...

template<NonnegativeLinearProgram >
void	CGAL::print_nonnegative_linear_program (std::ostream &out, const NonnegativeLinearProgram &lp, const std::string &problem_name=std::string("MY_MPS"))
	This function writes a nonnegative linear program to an output stream (in `MPSFormat`). More...

template<NonnegativeQuadraticProgram >
void	CGAL::print_nonnegative_quadratic_program (std::ostream &out, const NonnegativeQuadraticProgram &qp, const std::string &problem_name=std::string("MY_MPS"))
	This function writes a nonnegative quadratic program to an output stream (in `MPSFormat`). More...

template<QuadraticProgram >
void	CGAL::print_quadratic_program (std::ostream &out, const QuadraticProgram &qp, const std::string &problem_name=std::string("MY_MPS"))
	This function writes a quadratic program to an output stream (in `MPSFormat`). More...

template<LinearProgram , ET >
Quadratic_program_solution< ET >	CGAL::solve_linear_program (const LinearProgram &lp, const ET &, const Quadratic_program_options &options=Quadratic_program_options())
	This function solves a linear program, using some exact Integral Domain `ET` for its computations. More...

template<NonnegativeLinearProgram , ET >
Quadratic_program_solution< ET >	CGAL::solve_nonnegative_linear_program (const NonnegativeLinearProgram &lp, const ET &, const Quadratic_program_options &options=Quadratic_program_options())
	This function solves a nonnegative linear program, using some exact Integral Domain `ET` for its computations. More...

template<NonnegativeQuadraticProgram , ET >
Quadratic_program_solution< ET >	CGAL::solve_nonnegative_quadratic_program (const NonnegativeQuadraticProgram &qp, const ET &, const Quadratic_program_options &options=Quadratic_program_options())
	This function solves a nonnegative quadratic program, using some exact Integral Domain `ET` for its computations. More...

template<QuadraticProgram , ET >
Quadratic_program_solution< ET >	CGAL::solve_quadratic_program (const QuadraticProgram &qp, const ET &, const Quadratic_program_options &options=Quadratic_program_options())
	This function solves a quadratic program, using some exact Integral Domain `ET` for its computations. More...

template<typename A_it , typename B_it , typename R_it , typename FL_it , typename L_it , typename FU_it , typename U_it , typename C_it >
Linear_program_from_iterators < A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it >	CGAL::make_linear_program_from_iterators (int n, int m, const A_it &a, const B_it &b, const R_it &r, const FL_it &fl, const L_it &l, const FU_it &fu, const U_it &u, const C_it &c, std::iterator_traits< C_it >::value_type c0=std::iterator_traits< C_it >::value_type(0))
	This template function creates an instance of `Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it>` from given iterators. More...

template<A_it , B_it , R_it , C_it >
Nonnegative_linear_program_from_iterators < A_it, B_it, R_it, C_it >	CGAL::make_nonnegative_linear_program_from_iterators (int n, int m, const A_it &a, const B_it &b, const R_it &r, const C_it &c, std::iterator_traits< C_it >::value_type c0=std::iterator_traits< C_it >::value_type(0))
	This template function creates an instance of `Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>` from given iterators. More...

template<A_it , B_it , R_it , D_it , C_it >
Nonnegative_quadratic_program_from_iterators < A_it, B_it, R_it, D_it, C_it >	CGAL::make_nonnegative_quadratic_program_from_iterators (int n, int m, const A_it &a, const B_it &b, const R_it &r, const D_it &d, const C_it &c, std::iterator_traits< C_it >::value_type c0=std::iterator_traits< C_it >::value_type(0))
	This template function creates an instance of `Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it, C_it>` from given iterators. More...

template<typename A_it , typename B_it , typename R_it , typename FL_it , typename L_it , typename FU_it , typename U_it , typename D_it , typename C_it >
Quadratic_program_from_iterators < A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it >	CGAL::make_quadratic_program_from_iterators (int n, int m, const A_it &a, const B_it &b, const R_it &r, const FL_it &fl, const L_it &l, const FU_it &fu, const U_it &u, const D_it &d, const C_it &c, std::iterator_traits< C_it >::value_type c0=std::iterator_traits< C_it >::value_type(0))
	This template function creates an instance of `Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it>` from given iterators. More...

Enumeration Type Documentation

enum CGAL::Quadratic_program_pricing_strategy

This is an enumeration type containing the values QP_CHOOSE_DEFAULT, QP_DANTZIG, QP_PARTIAL_DANTZIG, QP_FILTERED_DANTZIG, QP_PARTIAL_FILTERED_DANTZIG, andQP_BLAND.

It indicates the pricing strategy to be used in solving a linear or quadratic program. This strategy determines how the solver gets from one intermediate solution to the next during any of its iterations.

Here we briefly describe when to choose which strategy.

See Also: Quadratic_program_options

#include <CGAL/QP_options.h>

Enumerator
QP_CHOOSE_DEFAULT	This is the default value of the pricing strategy in `Quadratic_program_options`, and it lets the solver choose the strategy that it thinks is most appropriate for the problem at hand. There are only few reasons to deviate from this default, but you are free to experiment, of course.
QP_PARTIAL_DANTZIG	If the input type is not `double`, this is usually the best choice for linear and quadratic programs of medium size.
QP_DANTZIG	If the input type is not `double`, this can sometimes make a difference (be faster or slowe) than `QP_PARTIAL_DANTZIG` for problems with a high variable/constraint or constraint/variable ratio.
QP_PARTIAL_FILTERED_DANTZIG	If the input type is `double`, this is usually the best choice for linear and quadratic programs of medium size. If the input type is not `double`, this choice is equivalent to `QP_PARTIAL_DANTZIG`. Note: filtered strategies may in rare cases fail due to double exponent overflows, see Section Exponent Overflow in Double Using Floating-Point Filters. In this case, the slower fallback option is the non-filtered variant `QP_PARTIAL_DANTZIG` of this strategy.
QP_FILTERED_DANTZIG	If the input type is `double`, this can sometimes make a difference (be faster or slowe) than `QP_PARTIAL_FILTERED_DANTZIG` for problems with a high variable/constraint or constraint/variable ratio. If the input type is not `double`, this choice is equivalent to `QP_DANTZIG`. Note Filtered strategies may in rare cases fail due to double exponent overflows, see Section Exponent Overflow in Double Using Floating-Point Filters. In this case, the slower fallback option is the non-filtered variant `QP_DANTZIG` of this strategy.
QP_BLAND	This is hardly ever the most efficient choice, but it is guaranteed to avoid internal cycling of the solution algorithm, see Section The Solver Internally Cycles.

Function Documentation

template<typename A_it , typename B_it , typename R_it , typename FL_it , typename L_it , typename FU_it , typename U_it , typename C_it >

Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it> CGAL::make_linear_program_from_iterators	(	int	n,
		int	m,
		const A_it &	a,
		const B_it &	b,
		const R_it &	r,
		const FL_it &	fl,
		const L_it &	l,
		const FU_it &	fu,
		const U_it &	u,
		const C_it &	c,
		std::iterator_traits< C_it >::value_type	c0 = `std::iterator_traits< C_it >::value_type(0)`
	)

This template function creates an instance of Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it> from given iterators.

This function can be useful if the types of these iterators are too complicated (or of too little interest for you) to write them down explicitly.

Returns: an instance of Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it>, constructed from the given iterators.

Example

The following example demonstrates the typical usage of makers with the simpler function make_nonnegative_linear_program_from_iterators().

QP_solver/solve_convex_hull_containment_lp2.h

QP_solver/convex_hull_containment2.cpp

See Also: Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it>

#include <CGAL/QP_models.h>

template<A_it , B_it , R_it , C_it >

Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it> CGAL::make_nonnegative_linear_program_from_iterators	(	int	n,
		int	m,
		const A_it &	a,
		const B_it &	b,
		const R_it &	r,
		const C_it &	c,
		std::iterator_traits< C_it >::value_type	c0 = `std::iterator_traits< C_it >::value_type(0)`
	)

This template function creates an instance of Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it> from given iterators.

This function can be useful if the types of these iterators are too complicated (or of too little interest for you) to write them down explicitly.

Returns: an instance of Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>, constructed from the given iterators.

Example

QP_solver/solve_convex_hull_containment_lp2.h

QP_solver/convex_hull_containment2.cpp

See Also: Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>

#include <CGAL/QP_models.h>

Examples:: QP_solver/solve_convex_hull_containment_lp2.h, and QP_solver/solve_convex_hull_containment_lp3.h.

template<A_it , B_it , R_it , D_it , C_it >

Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it, C_it> CGAL::make_nonnegative_quadratic_program_from_iterators	(	int	n,
		int	m,
		const A_it &	a,
		const B_it &	b,
		const R_it &	r,
		const D_it &	d,
		const C_it &	c,
		std::iterator_traits< C_it >::value_type	c0 = `std::iterator_traits< C_it >::value_type(0)`
	)

This template function creates an instance of Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it, C_it> from given iterators.

This function can be useful if the types of these iterators are too complicated (or of too little interest for you) to write them down explicitly.

Returns: an instance of Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it,C_it>, constructed from the given iterators.

Example

The following example demonstrates the typical usage of makers with the simpler function make_nonnegative_linear_program_from_iterators().

QP_solver/solve_convex_hull_containment_lp2.h

QP_solver/convex_hull_containment2.cpp

See Also: Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it, C_it>

#include <CGAL/QP_models.h>

template<typename A_it , typename B_it , typename R_it , typename FL_it , typename L_it , typename FU_it , typename U_it , typename D_it , typename C_it >

Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it> CGAL::make_quadratic_program_from_iterators	(	int	n,
		int	m,
		const A_it &	a,
		const B_it &	b,
		const R_it &	r,
		const FL_it &	fl,
		const L_it &	l,
		const FU_it &	fu,
		const U_it &	u,
		const D_it &	d,
		const C_it &	c,
		std::iterator_traits< C_it >::value_type	c0 = `std::iterator_traits< C_it >::value_type(0)`
	)

This template function creates an instance of Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it> from given iterators.

This function can be useful if the types of these iterators are too complicated (or of too little interest for you) to write them down explicitly.

Returns: an instance of Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it>, constructed from the given iterators.

Example

The following example demonstrates the typical usage of makers with the simpler function make_nonnegative_linear_program_from_iterators().

QP_solver/solve_convex_hull_containment_lp2.h

QP_solver/convex_hull_containment2.cpp

See Also: Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it>

#include <CGAL/QP_models.h>

template<LinearProgram >

void CGAL::print_linear_program	(	std::ostream &	out,
		const LinearProgram &	lp,
		const std::string &	problem_name = `std::string("MY_MPS")`
	)

This function writes a linear program to an output stream (in MPSFormat).

The time complexity is \( \Theta (mn)\), even if the program is very sparse.

It writes the linear program lp to out in MPSFormat. The name of the program will be the one provided by problem_name.

Requirements

Output operators are defined for all entry types of lp.

Example

QP_solver/print_first_lp.cpp

See Also: The concept LinearProgram

#include <CGAL/QP_functions.h>

Examples:: QP_solver/print_first_lp.cpp.

template<NonnegativeLinearProgram >

void CGAL::print_nonnegative_linear_program	(	std::ostream &	out,
		const NonnegativeLinearProgram &	lp,
		const std::string &	problem_name = `std::string("MY_MPS")`
	)

This function writes a nonnegative linear program to an output stream (in MPSFormat).

The time complexity is \( \Theta (mn)\), even if the program is very sparse.

Writes the nonnegative linear program lp to out in MPSFormat. The name of the program will be the one provided by problem_name.

Requirements

Output operators are defined for all entry types of lp.

Example

QP_solver/print_first_nonnegative_lp.cpp

See Also: The concept NonnegativeLinearProgram

#include <CGAL/QP_functions.h>

Examples:: QP_solver/print_first_nonnegative_lp.cpp.

template<NonnegativeQuadraticProgram >

void CGAL::print_nonnegative_quadratic_program	(	std::ostream &	out,
		const NonnegativeQuadraticProgram &	qp,
		const std::string &	problem_name = `std::string("MY_MPS")`
	)

This function writes a nonnegative quadratic program to an output stream (in MPSFormat).

The time complexity is \( \Theta (n^2 + mn)\), even if the program is very sparse.

Writes the nonnegative quadratic program qp to out in MPSFormat. The name of the program will be the one provided by problem_name.

Requirements

Output operators are defined for all entry types of qp.

Example

QP_solver/print_first_nonnegative_qp.cpp

See Also: The concept NonnegativeQuadraticProgram

#include <CGAL/QP_functions.h>

Examples:: QP_solver/print_first_nonnegative_qp.cpp, and QP_solver/print_first_qp.cpp.

template<QuadraticProgram >

void CGAL::print_quadratic_program	(	std::ostream &	out,
		const QuadraticProgram &	qp,
		const std::string &	problem_name = `std::string("MY_MPS")`
	)

This function writes a quadratic program to an output stream (in MPSFormat).

The time complexity is \( \Theta (n^2 + mn)\), even if the program is very sparse.

Writes the quadratic program qp to out in MPSFormat. The name of the program will be the one provided by problem_name.

Requirements

Output operators are defined for all entry types of qp.

Example

QP_solver/print_first_qp.cpp

See Also: The concept QuadraticProgram

#include <CGAL/QP_functions.h>

template<LinearProgram , ET >

Quadratic_program_solution<ET> CGAL::solve_linear_program	(	const LinearProgram &	lp,
		const ET &	,
		const Quadratic_program_options &	options = `Quadratic_program_options()`
	)

This function solves a linear program, using some exact Integral Domain ET for its computations.

Various options may be provided, see Quadratic_program_options.

Requirements

ET is a model of the concepts IntegralDomain and RealEmbeddable; it must be an exact type, and all entries of qp are convertible to ET.

Here are some recommended combinations of input type (the type of the qp entries) and ET.

input type	ET
`double`	`MP_Float`, `Gmpzf`, or `Gmpq`
`int`	`MP_Float`, or `Gmpz`
any exact type `NT`	`NT`

Note: By default, this function performs a large number of runtime-checks to ensure consistency during the solution process. However, these checks slow down the computations by a considerable factor. For maximum efficiency, it is advisable to define the macros CGAL_QP_NO_ASSERTIONS or NDEBUG.

Returns: the solution of the linear program lp, solved with exact number type ET.

Example

QP_solver/first_lp.cpp

See Also: Quadratic_program<NT>; Quadratic_program_from_mps<NT>; Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it>

#include <CGAL/QP_functions.h>

Examples:: QP_solver/first_lp.cpp, QP_solver/first_lp_from_iterators.cpp, QP_solver/first_lp_from_mps.cpp, and QP_solver/invert_matrix.cpp.

template<NonnegativeLinearProgram , ET >

Quadratic_program_solution<ET> CGAL::solve_nonnegative_linear_program	(	const NonnegativeLinearProgram &	lp,
		const ET &	,
		const Quadratic_program_options &	options = `Quadratic_program_options()`
	)

This function solves a nonnegative linear program, using some exact Integral Domain ET for its computations.

Various options may be provided, see Quadratic_program_options.

Requirements

ET is a model of the concepts IntegralDomain and RealEmbeddable; it must be an exact type, and all entries of qp are convertible to ET.

Here are some recommended combinations of input type (the type of the qp entries) and ET.

input type	ET
`double`	`MP_Float`, `Gmpzf`, or `Gmpq`
`int`	`MP_Float`, or `Gmpz`
any exact type `NT`	`NT`

Note: By default, this function performs a large number of runtime-checks to ensure consistency during the solution process. However, these checks slow down the computations by a considerable factor. For maximum efficiency, it is advisable to define the macros CGAL_QP_NO_ASSERTIONS or NDEBUG.

Returns: the solution of the nonnegative linear program lp, solved with exact number type ET.

Example

QP_solver/first_nonnegative_lp.cpp

The models of NonnegativeLinearProgram\:

See Also: Quadratic_program<NT>; Quadratic_program_from_mps<NT>; Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>

#include <CGAL/QP_functions.h>

Examples:: QP_solver/cycling.cpp, QP_solver/first_nonnegative_lp.cpp, QP_solver/first_nonnegative_lp_from_iterators.cpp, QP_solver/first_nonnegative_lp_from_mps.cpp, QP_solver/infeasibility_certificate.cpp, QP_solver/optimality_certificate.cpp, QP_solver/solve_convex_hull_containment_lp.h, QP_solver/solve_convex_hull_containment_lp2.h, QP_solver/solve_convex_hull_containment_lp3.h, and QP_solver/unboundedness_certificate.cpp.

template<NonnegativeQuadraticProgram , ET >

Quadratic_program_solution<ET> CGAL::solve_nonnegative_quadratic_program	(	const NonnegativeQuadraticProgram &	qp,
		const ET &	,
		const Quadratic_program_options &	options = `Quadratic_program_options()`
	)

This function solves a nonnegative quadratic program, using some exact Integral Domain ET for its computations.

Various options may be provided, see Quadratic_program_options.

Requirements

ET is a model of the concepts IntegralDomain and RealEmbeddable; it must be an exact type, and all entries of qp are convertible to ET.

Here are some recommended combinations of input type (the type of the qp entries) and ET.

input type	ET
`double`	`MP_Float`, `Gmpzf`, or `Gmpq`
`int`	`MP_Float`, or `Gmpz`
any exact type `NT`	`NT`

Note: By default, this function performs a large number of runtime-checks to ensure consistency during the solution process. However, these checks slow down the computations by a considerable factor. For maximum efficiency, it is advisable to define the macros CGAL_QP_NO_ASSERTIONS or NDEBUG.

Returns: the solution of the nonnegative quadratic program qp, solved with exact number type ET.

Example

QP_solver/first_nonnegative_qp.cpp

The models of NonnegativeQuadraticProgram\:

See Also: Quadratic_program<NT>; Quadratic_program_from_mps<NT>; Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it, C_it>

#include <CGAL/QP_functions.h>

Examples:: QP_solver/first_nonnegative_qp.cpp, QP_solver/first_nonnegative_qp_from_iterators.cpp, and QP_solver/first_nonnegative_qp_from_mps.cpp.

template<QuadraticProgram , ET >

Quadratic_program_solution<ET> CGAL::solve_quadratic_program	(	const QuadraticProgram &	qp,
		const ET &	,
		const Quadratic_program_options &	options = `Quadratic_program_options()`
	)

This function solves a quadratic program, using some exact Integral Domain ET for its computations.

Various options may be provided, see Quadratic_program_options.

Requirements

ET is a model of the concepts IntegralDomain and RealEmbeddable; it must be an exact type, and all entries of qp are convertible to ET.

Here are some recommended combinations of input type (the type of the qp entries) and ET.

input type	ET
`double`	`MP_Float`, `Gmpzf`, or `Gmpq`
`int`	`MP_Float`, or `Gmpz`
any exact type `NT`	`NT`

Note: By default, this function performs a large number of runtime-checks to ensure consistency during the solution process. However, these checks slow down the computations by a considerable factor. For maximum efficiency, it is advisable to define the macros CGAL_QP_NO_ASSERTIONS or NDEBUG.

Returns: the solution of the quadratic program qp, solved with exact number type ET.

Example

QP_solver/first_qp.cpp

The models of QuadraticProgram\:

See Also: Quadratic_program<NT>; Quadratic_program_from_mps<NT>; Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it>

#include <CGAL/QP_functions.h>

Examples:: QP_solver/first_qp.cpp, QP_solver/first_qp_basic_constraints.cpp, QP_solver/first_qp_from_iterators.cpp, and QP_solver/first_qp_from_mps.cpp.

Classes

Enumerations

Functions

Enumeration Type Documentation

Function Documentation

Example

Example

Example

Example

Requirements

Example

Requirements

Example

Requirements

Example

Requirements

Example

Requirements

Example

Requirements

Example

Requirements

Example

Requirements

Example