Esolver


Detailed Description

Here we define an interface to solve LP's (QSexact_solver) and MIP's exactly.
History:
Revision 0.1


Files

file  base_QSopt_ex.h
file  eg_exutil.c
file  eg_exutil.h
file  exact.c
file  exact.h
file  QSopt_ex.h

EXutilStatics

Variables asociated with the EXutilApproximate function, we use them as static to save some time in intialization

void EXutilDoClear (void)
 Clear all memory related to the static variables.
void EXutilDoInit (void)
 Initialize the static variables at start-up.
static mpq_t cvl
 rational remainder used in the continued fraction method
static mpz_t Z [7]
 Array of integers used in the continued fraction method.

Defines

#define EX_STATUS_BESTFRAC   128U
 status for integer variable among our set of selected integer variables. This status is not defined while calling cut callbacks.
#define EX_STATUS_BESTFRAC   128U
 status for integer variable among our set of selected integer variables. This status is not defined while calling cut callbacks.
#define EX_STATUS_BESTFRAC   128U
 status for integer variable among our set of selected integer variables. This status is not defined while calling cut callbacks.
#define EX_STATUS_FIX_LB   64U
 status for integer variable fixed at its lower bound. This status is not defined while calling cut callbacks.
#define EX_STATUS_FIX_LB   64U
 status for integer variable fixed at its lower bound. This status is not defined while calling cut callbacks.
#define EX_STATUS_FIX_LB   64U
 status for integer variable fixed at its lower bound. This status is not defined while calling cut callbacks.
#define EX_STATUS_FIX_UB   32U
 status for integer variable fixed at its upper bound. This status is not defined while calling cut callbacks.
#define EX_STATUS_FIX_UB   32U
 status for integer variable fixed at its upper bound. This status is not defined while calling cut callbacks.
#define EX_STATUS_FIX_UB   32U
 status for integer variable fixed at its upper bound. This status is not defined while calling cut callbacks.
#define EX_STATUS_INT   4U
 status for variables that are integer
#define EX_STATUS_INT   4U
 status for variables that are integer
#define EX_STATUS_INT   4U
 status for variables that are integer
#define EX_STATUS_LB   8U
 status for variables that bounded from below
#define EX_STATUS_LB   8U
 status for variables that bounded from below
#define EX_STATUS_LB   8U
 status for variables that bounded from below
#define EX_STATUS_LGC   1U
 status for variables that are logicals
#define EX_STATUS_LGC   1U
 status for variables that are logicals
#define EX_STATUS_LGC   1U
 status for variables that are logicals
#define EX_STATUS_STR   2U
 status for variables that are structural
#define EX_STATUS_STR   2U
 status for variables that are structural
#define EX_STATUS_STR   2U
 status for variables that are structural
#define EX_STATUS_UB   16U
 status for variables that bounded from above
#define EX_STATUS_UB   16U
 status for variables that bounded from above
#define EX_STATUS_UB   16U
 status for variables that bounded from above
#define EX_UTIL_VERBOSE   100
 verbosity level
#define EX_UTIL_VERBOSE   100
 verbosity level
#define EX_UTIL_VERBOSE   100
 verbosity level
#define EXutilIidToStr(iid, QSlp, QSinv_map)
 given a variable in internal number, return a pointer to its name.
#define EXutilIidToStr(iid, QSlp, QSinv_map)
 given a variable in internal number, return a pointer to its name.
#define EXutilIidToStr(iid, QSlp, QSinv_map)
 given a variable in internal number, return a pointer to its name.
#define EXutilInnProd(dim, a, b, v, w, rop)
 given two vectors (a,b) and (v,w), compute its inner product and store it into rop.
#define EXutilInnProd(dim, a, b, v, w, rop)
 given two vectors (a,b) and (v,w), compute its inner product and store it into rop.
#define EXutilInnProd(dim, a, b, v, w, rop)
 given two vectors (a,b) and (v,w), compute its inner product and store it into rop.
#define EXutilL1Norm(dim, a, rop)
 Compute the L_1 norm of a given vector.
#define EXutilL1Norm(dim, a, rop)
 Compute the L_1 norm of a given vector.
#define EXutilL1Norm(dim, a, rop)
 Compute the L_1 norm of a given vector.
#define EXutilNzSz(dim, a, rop)
 Compute the number of non-zeros in a given vector.
#define EXutilNzSz(dim, a, rop)
 Compute the number of non-zeros in a given vector.
#define EXutilNzSz(dim, a, rop)
 Compute the number of non-zeros in a given vector.
#define mpq_CroundExp(op, exp)
 round to $+\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from above.
#define mpq_CroundExp(op, exp)
 round to $+\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from above.
#define mpq_CroundExp(op, exp)
 round to $+\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from above.
#define mpq_FracPart(rop, op1)
 asign to the first number the fractional part of the second, i.e. $ rop = op1 - \lfloor op1 \rfloor $.
#define mpq_FracPart(rop, op1)
 asign to the first number the fractional part of the second, i.e. $ rop = op1 - \lfloor op1 \rfloor $.
#define mpq_FracPart(rop, op1)
 asign to the first number the fractional part of the second, i.e. $ rop = op1 - \lfloor op1 \rfloor $.
#define mpq_FroundExp(op, exp)
 round to $-\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from bellow.
#define mpq_FroundExp(op, exp)
 round to $-\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from bellow.
#define mpq_FroundExp(op, exp)
 round to $-\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from bellow.
#define mpq_IsInteger(op)
 test if the given number is integer.
#define mpq_IsInteger(op)
 test if the given number is integer.
#define mpq_IsInteger(op)
 test if the given number is integer.
#define mpq_TroundExp(op, exp)
 round to $0$ the given number to the closest fraction of the form $a/2^{exp}$ towards zero.
#define mpq_TroundExp(op, exp)
 round to $0$ the given number to the closest fraction of the form $a/2^{exp}$ towards zero.
#define mpq_TroundExp(op, exp)
 round to $0$ the given number to the closest fraction of the form $a/2^{exp}$ towards zero.
#define QS_EXACT_MAX_ITER   12
 This constant define the maximum number of try's for the exact solver with mpf_t numbers while incrementing the precision.
#define QS_EXACT_MAX_ITER   12
 This constant define the maximum number of try's for the exact solver with mpf_t numbers while incrementing the precision.
#define QS_EXACT_MAX_ITER   12
 This constant define the maximum number of try's for the exact solver with mpf_t numbers while incrementing the precision.
#define QScopy_array_dbl_mpq(array)
 create a copy of a double array into mpq_t array.
#define QScopy_array_dbl_mpq(array)
 create a copy of a double array into mpq_t array.
#define QScopy_array_dbl_mpq(array)
 create a copy of a double array into mpq_t array.
#define QScopy_array_mpf_mpq(array)
 create a copy of a mpf_t array into mpq_t array.
#define QScopy_array_mpf_mpq(array)
 create a copy of a mpf_t array into mpq_t array.
#define QScopy_array_mpf_mpq(array)
 create a copy of a mpf_t array into mpq_t array.
#define QScopy_array_mpq_dbl(array)
 create a copy of a mpq_t array into a double array.
#define QScopy_array_mpq_dbl(array)
 create a copy of a mpq_t array into a double array.
#define QScopy_array_mpq_dbl(array)
 create a copy of a mpq_t array into a double array.
#define QScopy_array_mpq_mpf(array)
 create a copy of a mpq_t array into a mpf_t array.
#define QScopy_array_mpq_mpf(array)
 create a copy of a mpq_t array into a mpf_t array.
#define QScopy_array_mpq_mpf(array)
 create a copy of a mpq_t array into a mpf_t array.
#define QSEXACT_SAVE_INT   0
 If enabled, save the intermediate problems created by the functions QScopy_prob_mpq_dbl and QScopy_prob_mpq_mpf.
#define QSEXACT_SAVE_INT   0
 If enabled, save the intermediate problems created by the functions QScopy_prob_mpq_dbl and QScopy_prob_mpq_mpf.
#define QSEXACT_SAVE_INT   0
 If enabled, save the intermediate problems created by the functions QScopy_prob_mpq_dbl and QScopy_prob_mpq_mpf.
#define QSEXACT_SAVE_OPTIMAL   0
 If enabled, save the last problem proved to be optimal, and its solution.
#define QSEXACT_SAVE_OPTIMAL   0
 If enabled, save the last problem proved to be optimal, and its solution.
#define QSEXACT_SAVE_OPTIMAL   0
 If enabled, save the last problem proved to be optimal, and its solution.
#define QSexact_set_precision(precision)   mpf_QSset_precision(precision)
 Set the number of bits to use with mpf_t type numbers and change all internal constants as needed.
#define QSexact_set_precision(precision)   mpf_QSset_precision(precision)
 Set the number of bits to use with mpf_t type numbers and change all internal constants as needed.
#define QSexact_set_precision(precision)   mpf_QSset_precision(precision)
 Set the number of bits to use with mpf_t type numbers and change all internal constants as needed.

Functions

void EXutilApproximate (mpq_t dest, mpq_t ori, unsigned const max_den)
 Approximate using continued fractions method a given rational $\frac{a}{b} $ with another rational $\frac{a'}{b'}$ that satisfy that $ b' < max_den^2 $ and also $|\frac{a}{b} - \frac{a'}{b'}|\leq\frac1{max_den^2}$.
int EXutilExpandLogicals (mpq_QSdata *const act_lp, mpq_t *const vector, mpq_t rhs, mpq_ILLlp_rows *const lprows)
 Given a vector in QSopt external form, and a row description of the related LP, re-write the vector using only real variables, we do that by substracting the equation defining the logical variable multiplied by the coefficient of the logical variable in the vector to the vector.
int EXutilIntegralize (const unsigned n, mpq_t *const a, mpq_t b, mpq_t maxabs)
 given a cut ax <=> b, write it in integer form ,i.e. set all a,b to integer in such a way that a_i and b are all relativelly prime.
void EXutilNicefy (mpq_QSdata *const act_prob, const unsigned char *const var_stat, const unsigned max_den, mpq_t *a, mpq_t b, int const sense)
 Given an inequality, we try to re-write so that no denominator is bigger than the square of the given number, and ensuring validity. for coefficients that can't be `nacified' we leave them intact. the process imply adding multiples of the bounds on variables, and at the end, nicify the rhs of the inequality.
void EXutilOverEstimate (mpq_t dest, mpq_t ori, unsigned const max_den)
 Overestimate the given coefficient by another rational that is representble with denominators not bigger than max_den^2.
int EXutilSimplify (const unsigned n, mpq_t *const a, mpq_t b)
 given a cut ax <=> b, write it in normalized form ,i.e. set all a,b to integer in such a way that a_i and b are all relativelly prime, and divide them all over the maximum such (a_i,b) (so that the infinity norm of (a,b) is one.
static void infeasible_output (mpq_QSdata *p_mpq, mpq_t *const y, mpq_t *y_mpq)
 print into screen (if enable) a message indicating that we have successfully prove infeasibility, and save (if y is non NULL ) the dual ray solution provided in y_mpq.
void mpq_GomoryCoeff (mpq_t rop, mpq_t coef, unsigned const is_int, int const bound, unsigned const cut_mlt, mpq_t b_frac)
 compute the gomory coefficient of the variable given the original coefficient, the multiplier, and all relevant information.
int mpq_grab_cache (mpq_QSdata *p, int status)
void mpq_ILLfct_check_dfeasible (mpq_lpinfo *lp, mpq_feas_info *fs, const mpq_t ftol)
void mpq_ILLfct_check_pfeasible (mpq_lpinfo *lp, mpq_feas_info *fs, const mpq_t ftol)
void mpq_ILLfct_compute_dobj (mpq_lpinfo *lp)
void mpq_ILLfct_compute_dz (mpq_lpinfo *lp)
void mpq_ILLfct_compute_phaseI_piz (mpq_lpinfo *lp)
void mpq_ILLfct_compute_piz (mpq_lpinfo *lp)
void mpq_ILLfct_compute_xbz (mpq_lpinfo *lp)
void mpq_ILLfct_set_status_values (mpq_lpinfo *lp, int pstatus, int dstatus, int ptype, int dtype)
void mpq_ILLfct_set_variable_type (mpq_lpinfo *lp)
static void optimal_output (mpq_QSdata *p_mpq, mpq_t *const x, mpq_t *const y, mpq_t *x_mpq, mpq_t *y_mpq)
 print into screen (if enable) a message indicating that we have successfully solved the problem at optimality, and save (if x and y are non NULL respectivelly) the optimal primal/dual solution provided in x_mpq and y_mpq.
dbl_QSdataQScopy_prob_mpq_dbl (mpq_QSdata *p, const char *newname)
 Copy an exact problem (mpq_QSdata) to a regular double version of the problem (dbl_QSdata).
mpf_QSdataQScopy_prob_mpq_mpf (mpq_QSdata *p, const char *newname)
 Copy an exact problem (mpq_QSdata) to a regular double version of the problem (dbl_QSdata).
int QSexact_basis_dualstatus (mpq_QSdata *p_mpq, QSbasis *basis, char *result, mpq_t *dobjval, const int msg_lvl)
 test whether given basis is dual feasible in rational arithmetic.
int QSexact_basis_optimalstatus (mpq_QSdata *p_mpq, QSbasis *basis, char *result, const int msg_lvl)
 test whether given basis is primal and dual feasible in rational arithmetic.
static int QSexact_basis_status (mpq_QSdata *p_mpq, int *status, QSbasis *const basis, const int msg_lvl, int *const simplexalgo)
 get the status for a given basis in rational arithmetic, it should also leave everything set to get primal/dual solutions when needed.
int QSexact_infeasible_test (mpq_QSdata *p, mpq_t *d_sol)
 Check if the given dual vector is a proof of infeasibility for the given exact problem.
int QSexact_optimal_test (mpq_QSdata *p, mpq_t *p_sol, mpq_t *d_sol, QSbasis *basis)
 Test if a given primal/dual solution is feasible and has the same objective value.
int QSexact_print_sol (mpq_QSdata *p, EGioFile_t *out_f)
 Print into a file the optimal solution.
int QSexact_solver (mpq_QSdata *p_mpq, mpq_t *const x, mpq_t *const y, QSbasis *const basis, int simplexalgo, int *status)
 Given an mpq_QSdata problem, solve it exactly.
int QSexact_verify (mpq_QSdata *p_mpq, QSbasis *basis, int useprestep, double *dbl_p_sol, double *dbl_d_sol, char *result, mpq_t *dobjval, const int msg_lvl)
 test whether given basis is dual feasible in rational arithmetic. if wanted it will first directly test the corresponding approximate dual and primal solution (corrected via dual variables for bounds and primal variables for slacks if possible) for optimality before performing the dual feasibility test on the more expensive exact basic solution.
void QSexact_write_row (EGioFile_t *out_f, mpq_ILLlpdata *lp, int row)
 Write a given row from the LP into the given stream, in exact arithmetic.
void QSexactClear (void)
 This function must be called at the end of the program to free all internal data used in the QSexact structures, once this function is called any operation on EGxxx mpq_xxx mpf_xx QSxx may fail.
void QSexactStart (void)
 Initializator for global data, this is needed mainly for defining constants in extended floating point precision and for rational precision. This call should be done BEFORE any mpq_xxx mpf_xxx QSxx EGxx call.

Variables

int __QSexact_setup
 indicate if the global data needed for QSexact has been initialized, if zero, initialization routine should be called. This is provided to allow syncronization between libraries
int __QSexact_setup
 indicate if the global data needed for QSexact has been initialized, if zero, initialization routine should be called. This is provided to allow syncronization between libraries
int __QSexact_setup = 0
 indicate if the global data needed for QSexact has been initialized, if zero, initialization routine should be called. This is provided to allow syncronization between libraries
int __QSexact_setup
 indicate if the global data needed for QSexact has been initialized, if zero, initialization routine should be called. This is provided to allow syncronization between libraries
static const char __sp [81]
 Used as separator while printing output to the screen (controled by enabling simplex_display in the mpq_QSdata.
mpq_t mpq_ILL_MAXDOUBLE
mpq_t mpq_ILL_MINDOUBLE


Define Documentation

#define EX_STATUS_BESTFRAC   128U

status for integer variable among our set of selected integer variables. This status is not defined while calling cut callbacks.

Definition at line 19807 of file base_QSopt_ex.h.

#define EX_STATUS_BESTFRAC   128U

status for integer variable among our set of selected integer variables. This status is not defined while calling cut callbacks.

Definition at line 64 of file eg_exutil.h.

#define EX_STATUS_BESTFRAC   128U

status for integer variable among our set of selected integer variables. This status is not defined while calling cut callbacks.

Definition at line 20331 of file QSopt_ex.h.

#define EX_STATUS_FIX_LB   64U

status for integer variable fixed at its lower bound. This status is not defined while calling cut callbacks.

Definition at line 19802 of file base_QSopt_ex.h.

#define EX_STATUS_FIX_LB   64U

status for integer variable fixed at its lower bound. This status is not defined while calling cut callbacks.

Definition at line 59 of file eg_exutil.h.

#define EX_STATUS_FIX_LB   64U

status for integer variable fixed at its lower bound. This status is not defined while calling cut callbacks.

Definition at line 20326 of file QSopt_ex.h.

#define EX_STATUS_FIX_UB   32U

status for integer variable fixed at its upper bound. This status is not defined while calling cut callbacks.

Definition at line 19797 of file base_QSopt_ex.h.

#define EX_STATUS_FIX_UB   32U

status for integer variable fixed at its upper bound. This status is not defined while calling cut callbacks.

Definition at line 54 of file eg_exutil.h.

#define EX_STATUS_FIX_UB   32U

status for integer variable fixed at its upper bound. This status is not defined while calling cut callbacks.

Definition at line 20321 of file QSopt_ex.h.

#define EX_STATUS_INT   4U

status for variables that are integer

Definition at line 19784 of file base_QSopt_ex.h.

#define EX_STATUS_INT   4U

status for variables that are integer

Definition at line 41 of file eg_exutil.h.

#define EX_STATUS_INT   4U

status for variables that are integer

Definition at line 20308 of file QSopt_ex.h.

#define EX_STATUS_LB   8U

status for variables that bounded from below

Definition at line 19788 of file base_QSopt_ex.h.

#define EX_STATUS_LB   8U

status for variables that bounded from below

Definition at line 45 of file eg_exutil.h.

#define EX_STATUS_LB   8U

status for variables that bounded from below

Definition at line 20312 of file QSopt_ex.h.

Referenced by EXutilNicefy().

#define EX_STATUS_LGC   1U

status for variables that are logicals

Definition at line 19776 of file base_QSopt_ex.h.

#define EX_STATUS_LGC   1U

status for variables that are logicals

Definition at line 33 of file eg_exutil.h.

#define EX_STATUS_LGC   1U

status for variables that are logicals

Definition at line 20300 of file QSopt_ex.h.

#define EX_STATUS_STR   2U

status for variables that are structural

Definition at line 19780 of file base_QSopt_ex.h.

#define EX_STATUS_STR   2U

status for variables that are structural

Definition at line 37 of file eg_exutil.h.

#define EX_STATUS_STR   2U

status for variables that are structural

Definition at line 20304 of file QSopt_ex.h.

#define EX_STATUS_UB   16U

status for variables that bounded from above

Definition at line 19792 of file base_QSopt_ex.h.

#define EX_STATUS_UB   16U

status for variables that bounded from above

Definition at line 49 of file eg_exutil.h.

#define EX_STATUS_UB   16U

status for variables that bounded from above

Definition at line 20316 of file QSopt_ex.h.

Referenced by EXutilNicefy().

#define EX_UTIL_VERBOSE   100

verbosity level

Definition at line 19825 of file base_QSopt_ex.h.

#define EX_UTIL_VERBOSE   100

verbosity level

Definition at line 82 of file eg_exutil.h.

#define EX_UTIL_VERBOSE   100

verbosity level

Definition at line 20349 of file QSopt_ex.h.

Referenced by EXutilExpandLogicals().

#define EXutilIidToStr ( iid,
QSlp,
QSinv_map   ) 

Value:

({\
  mpq_QSdata*const __EXlp = (QSlp);\
  const int __EXeid = (QSinv_map)[(iid)];\
  (__EXeid >= __EXlp->qslp->nstruct) ? __EXlp->qslp->rownames[__EXeid - __EXlp->qslp->nstruct] : __EXlp->qslp->colnames[__EXeid];})
given a variable in internal number, return a pointer to its name.

Parameters:
iid internal ordering number.
QSlp pointer to the mpq_QSdata structure containing the LP.
QSinv_map pointer to an array containing the inverse map from internal numbering to external numbering as in EXmipinfo_t::inv_map.
Returns:
pointer to its name.
Note:
If the variable is a slack variable, it return the name of the inequality.

Definition at line 20040 of file base_QSopt_ex.h.

#define EXutilIidToStr ( iid,
QSlp,
QSinv_map   ) 

Value:

({\
  mpq_QSdata*const __EXlp = (QSlp);\
  const int __EXeid = (QSinv_map)[(iid)];\
  (__EXeid >= __EXlp->qslp->nstruct) ? __EXlp->qslp->rownames[__EXeid - __EXlp->qslp->nstruct] : __EXlp->qslp->colnames[__EXeid];})
given a variable in internal number, return a pointer to its name.

Parameters:
iid internal ordering number.
QSlp pointer to the mpq_QSdata structure containing the LP.
QSinv_map pointer to an array containing the inverse map from internal numbering to external numbering as in EXmipinfo_t::inv_map.
Returns:
pointer to its name.
Note:
If the variable is a slack variable, it return the name of the inequality.

Definition at line 297 of file eg_exutil.h.

#define EXutilIidToStr ( iid,
QSlp,
QSinv_map   ) 

Value:

({\
  mpq_QSdata*const __EXlp = (QSlp);\
  const int __EXeid = (QSinv_map)[(iid)];\
  (__EXeid >= __EXlp->qslp->nstruct) ? __EXlp->qslp->rownames[__EXeid - __EXlp->qslp->nstruct] : __EXlp->qslp->colnames[__EXeid];})
given a variable in internal number, return a pointer to its name.

Parameters:
iid internal ordering number.
QSlp pointer to the mpq_QSdata structure containing the LP.
QSinv_map pointer to an array containing the inverse map from internal numbering to external numbering as in EXmipinfo_t::inv_map.
Returns:
pointer to its name.
Note:
If the variable is a slack variable, it return the name of the inequality.

Definition at line 20564 of file QSopt_ex.h.

#define EXutilInnProd ( dim,
a,
b,
v,
w,
rop   ) 

Value:

do{\
  register unsigned __EXuti = (dim);\
  mpq_mul(rop,b,w);\
  while(__EXuti--) mpq_EGlpNumAddInnProdTo(rop,(a)[__EXuti],(v)[__EXuti]);\
  } while(0);
given two vectors (a,b) and (v,w), compute its inner product and store it into rop.

Parameters:
dim dimmension of the a and v part of the vector.
a first part of the first vector.
b second part of the first vector.
v first part of the second vector.
w second part of the second vector.
rop where we store the result.
Note:
we may take a == v and/or b == w.

Definition at line 19838 of file base_QSopt_ex.h.

#define EXutilInnProd ( dim,
a,
b,
v,
w,
rop   ) 

Value:

do{\
  register unsigned __EXuti = (dim);\
  mpq_mul(rop,b,w);\
  while(__EXuti--) mpq_EGlpNumAddInnProdTo(rop,(a)[__EXuti],(v)[__EXuti]);\
  } while(0);
given two vectors (a,b) and (v,w), compute its inner product and store it into rop.

Parameters:
dim dimmension of the a and v part of the vector.
a first part of the first vector.
b second part of the first vector.
v first part of the second vector.
w second part of the second vector.
rop where we store the result.
Note:
we may take a == v and/or b == w.

Definition at line 95 of file eg_exutil.h.

#define EXutilInnProd ( dim,
a,
b,
v,
w,
rop   ) 

Value:

do{\
  register unsigned __EXuti = (dim);\
  mpq_mul(rop,b,w);\
  while(__EXuti--) mpq_EGlpNumAddInnProdTo(rop,(a)[__EXuti],(v)[__EXuti]);\
  } while(0);
given two vectors (a,b) and (v,w), compute its inner product and store it into rop.

Parameters:
dim dimmension of the a and v part of the vector.
a first part of the first vector.
b second part of the first vector.
v first part of the second vector.
w second part of the second vector.
rop where we store the result.
Note:
we may take a == v and/or b == w.

Definition at line 20362 of file QSopt_ex.h.

#define EXutilL1Norm ( dim,
a,
rop   ) 

Value:

do{\
  mpq_t*const  __EXuta = (a);\
  mpq_t __qtmp__;\
  register unsigned __EXuti = (dim);\
  mpq_init(__qtmp__);\
  mpq_set_ui(rop,0UL,1UL);\
  while(__EXuti--){\
    mpq_abs(__qtmp__,__EXuta[__EXuti]);\
    mpq_add(rop,rop,__qtmp__);}mpq_clear(__qtmp__);}while(0)
Compute the L_1 norm of a given vector.

Parameters:
dim size of the a vector.
a vector where we are operating.
rop where to retirn the L1 norm value

Definition at line 19860 of file base_QSopt_ex.h.

#define EXutilL1Norm ( dim,
a,
rop   ) 

Value:

do{\
  mpq_t*const  __EXuta = (a);\
  mpq_t __qtmp__;\
  register unsigned __EXuti = (dim);\
  mpq_init(__qtmp__);\
  mpq_set_ui(rop,0UL,1UL);\
  while(__EXuti--){\
    mpq_abs(__qtmp__,__EXuta[__EXuti]);\
    mpq_add(rop,rop,__qtmp__);}mpq_clear(__qtmp__);}while(0)
Compute the L_1 norm of a given vector.

Parameters:
dim size of the a vector.
a vector where we are operating.
rop where to retirn the L1 norm value

Definition at line 117 of file eg_exutil.h.

#define EXutilL1Norm ( dim,
a,
rop   ) 

Value:

do{\
  mpq_t*const  __EXuta = (a);\
  mpq_t __qtmp__;\
  register unsigned __EXuti = (dim);\
  mpq_init(__qtmp__);\
  mpq_set_ui(rop,0UL,1UL);\
  while(__EXuti--){\
    mpq_abs(__qtmp__,__EXuta[__EXuti]);\
    mpq_add(rop,rop,__qtmp__);}mpq_clear(__qtmp__);}while(0)
Compute the L_1 norm of a given vector.

Parameters:
dim size of the a vector.
a vector where we are operating.
rop where to retirn the L1 norm value

Definition at line 20384 of file QSopt_ex.h.

#define EXutilNzSz ( dim,
a,
rop   ) 

Value:

do{\
  register unsigned __EXuti = (dim);\
  rop = 0;\
  while(__EXuti--) if(mpz_cmp_ui(mpq_numref((a)[__EXuti]),0UL)) rop++;}while(0)
Compute the number of non-zeros in a given vector.

Parameters:
dim size of the a vector.
a vector where we are operating.
rop where to return the number of non-zeros (it should be an integer variable, not a pointer to such a variable)

Definition at line 19850 of file base_QSopt_ex.h.

#define EXutilNzSz ( dim,
a,
rop   ) 

Value:

do{\
  register unsigned __EXuti = (dim);\
  rop = 0;\
  while(__EXuti--) if(mpz_cmp_ui(mpq_numref((a)[__EXuti]),0UL)) rop++;}while(0)
Compute the number of non-zeros in a given vector.

Parameters:
dim size of the a vector.
a vector where we are operating.
rop where to return the number of non-zeros (it should be an integer variable, not a pointer to such a variable)

Definition at line 107 of file eg_exutil.h.

#define EXutilNzSz ( dim,
a,
rop   ) 

Value:

do{\
  register unsigned __EXuti = (dim);\
  rop = 0;\
  while(__EXuti--) if(mpz_cmp_ui(mpq_numref((a)[__EXuti]),0UL)) rop++;}while(0)
Compute the number of non-zeros in a given vector.

Parameters:
dim size of the a vector.
a vector where we are operating.
rop where to return the number of non-zeros (it should be an integer variable, not a pointer to such a variable)

Definition at line 20374 of file QSopt_ex.h.

#define mpq_CroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_cdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $+\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from above.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 19920 of file base_QSopt_ex.h.

#define mpq_CroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_cdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $+\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from above.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 177 of file eg_exutil.h.

#define mpq_CroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_cdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $+\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from above.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 20444 of file QSopt_ex.h.

#define mpq_FracPart ( rop,
op1   ) 

Value:

do{\
  mpz_fdiv_r (mpq_numref (rop), mpq_numref (op1), mpq_denref (op1));\
  mpz_set (mpq_denref (rop), mpq_denref (op1));\
  mpq_canonicalize((rop));\
} while(0)
asign to the first number the fractional part of the second, i.e. $ rop = op1 - \lfloor op1 \rfloor $.

Parameters:
rop where to retunr our result.
op1 number for wich we want to compute its fractional part

Definition at line 19889 of file base_QSopt_ex.h.

#define mpq_FracPart ( rop,
op1   ) 

Value:

do{\
  mpz_fdiv_r (mpq_numref (rop), mpq_numref (op1), mpq_denref (op1));\
  mpz_set (mpq_denref (rop), mpq_denref (op1));\
  mpq_canonicalize((rop));\
} while(0)
asign to the first number the fractional part of the second, i.e. $ rop = op1 - \lfloor op1 \rfloor $.

Parameters:
rop where to retunr our result.
op1 number for wich we want to compute its fractional part

Definition at line 146 of file eg_exutil.h.

#define mpq_FracPart ( rop,
op1   ) 

Value:

do{\
  mpz_fdiv_r (mpq_numref (rop), mpq_numref (op1), mpq_denref (op1));\
  mpz_set (mpq_denref (rop), mpq_denref (op1));\
  mpq_canonicalize((rop));\
} while(0)
asign to the first number the fractional part of the second, i.e. $ rop = op1 - \lfloor op1 \rfloor $.

Parameters:
rop where to retunr our result.
op1 number for wich we want to compute its fractional part

Definition at line 20413 of file QSopt_ex.h.

Referenced by mpq_GomoryCoeff().

#define mpq_FroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_fdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $-\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from bellow.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 19907 of file base_QSopt_ex.h.

#define mpq_FroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_fdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $-\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from bellow.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 164 of file eg_exutil.h.

#define mpq_FroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_fdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $-\infty$ the given number to the closest fraction of the form $a/2^{exp}$ from bellow.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 20431 of file QSopt_ex.h.

#define mpq_IsInteger ( op   ) 

Value:

({\
  (mpz_cmp(mpq_denref(op),mpz_oneLpNum)==0);})
test if the given number is integer.

Parameters:
op number to test.
Returns:
one if the nummber is integer, zero- otherwise.

Definition at line 19899 of file base_QSopt_ex.h.

#define mpq_IsInteger ( op   ) 

Value:

({\
  (mpz_cmp(mpq_denref(op),mpz_oneLpNum)==0);})
test if the given number is integer.

Parameters:
op number to test.
Returns:
one if the nummber is integer, zero- otherwise.

Definition at line 156 of file eg_exutil.h.

#define mpq_IsInteger ( op   ) 

Value:

({\
  (mpz_cmp(mpq_denref(op),mpz_oneLpNum)==0);})
test if the given number is integer.

Parameters:
op number to test.
Returns:
one if the nummber is integer, zero- otherwise.

Definition at line 20423 of file QSopt_ex.h.

Referenced by mpq_GomoryCoeff().

#define mpq_TroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_tdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $0$ the given number to the closest fraction of the form $a/2^{exp}$ towards zero.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 19933 of file base_QSopt_ex.h.

#define mpq_TroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_tdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $0$ the given number to the closest fraction of the form $a/2^{exp}$ towards zero.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 190 of file eg_exutil.h.

#define mpq_TroundExp ( op,
exp   ) 

Value:

do{\
      mpz_t __ztmp__;\
      mpz_init(__ztmp__);\
      mpz_mul_2exp(__ztmp__,mpq_numref((op)),(exp));\
      mpz_tdiv_q(mpq_numref((op)),__ztmp__,mpq_denref((op)));\
      mpz_mul_2exp(mpq_denref((op)),mpz_oneLpNum,(exp));\
      mpq_canonicalize((op));mpz_clear(__ztmp__);}while(0)
round to $0$ the given number to the closest fraction of the form $a/2^{exp}$ towards zero.

Parameters:
op number to round.
exp exponent to use in the fraction

Definition at line 20457 of file QSopt_ex.h.

#define QS_EXACT_MAX_ITER   12

This constant define the maximum number of try's for the exact solver with mpf_t numbers while incrementing the precision.

Definition at line 19644 of file base_QSopt_ex.h.

#define QS_EXACT_MAX_ITER   12

This constant define the maximum number of try's for the exact solver with mpf_t numbers while incrementing the precision.

Definition at line 383 of file exact.h.

#define QS_EXACT_MAX_ITER   12

This constant define the maximum number of try's for the exact solver with mpf_t numbers while incrementing the precision.

Definition at line 20168 of file QSopt_ex.h.

Referenced by QSexact_solver().

#define QScopy_array_dbl_mpq ( array   ) 

Value:

({ \
  double*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpq_t*__lres = mpq_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(__larray[__lsz] == dbl_ILL_MAXDOUBLE)\
      mpq_set(__lres[__lsz],mpq_ILL_MAXDOUBLE);\
    else if(__larray[__lsz] == dbl_ILL_MINDOUBLE)\
      mpq_set(__lres[__lsz],mpq_ILL_MINDOUBLE);\
    else mpq_EGlpNumSet(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a double array into mpq_t array.

Parameters:
array original array of double values (note that this array must have been allocated with dbl_EGlpNumAllocArray for this function to work).

Definition at line 19596 of file base_QSopt_ex.h.

#define QScopy_array_dbl_mpq ( array   ) 

Value:

({ \
  double*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpq_t*__lres = mpq_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(__larray[__lsz] == dbl_ILL_MAXDOUBLE)\
      mpq_set(__lres[__lsz],mpq_ILL_MAXDOUBLE);\
    else if(__larray[__lsz] == dbl_ILL_MINDOUBLE)\
      mpq_set(__lres[__lsz],mpq_ILL_MINDOUBLE);\
    else mpq_EGlpNumSet(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a double array into mpq_t array.

Parameters:
array original array of double values (note that this array must have been allocated with dbl_EGlpNumAllocArray for this function to work).

Definition at line 335 of file exact.h.

#define QScopy_array_dbl_mpq ( array   ) 

Value:

({ \
  double*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpq_t*__lres = mpq_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(__larray[__lsz] == dbl_ILL_MAXDOUBLE)\
      mpq_set(__lres[__lsz],mpq_ILL_MAXDOUBLE);\
    else if(__larray[__lsz] == dbl_ILL_MINDOUBLE)\
      mpq_set(__lres[__lsz],mpq_ILL_MINDOUBLE);\
    else mpq_EGlpNumSet(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a double array into mpq_t array.

Parameters:
array original array of double values (note that this array must have been allocated with dbl_EGlpNumAllocArray for this function to work).

Definition at line 20120 of file QSopt_ex.h.

Referenced by QSexact_solver(), and QSexact_verify().

#define QScopy_array_mpf_mpq ( array   ) 

Value:

({ \
  mpf_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpq_t*__lres = mpq_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpf_cmp(__larray[__lsz],mpf_ILL_MAXDOUBLE)==0)\
      mpq_set(__lres[__lsz],mpq_ILL_MAXDOUBLE);\
    else if(mpf_cmp(__larray[__lsz],mpf_ILL_MINDOUBLE)==0)\
      mpq_set(__lres[__lsz],mpq_ILL_MINDOUBLE);\
    mpq_set_f(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpf_t array into mpq_t array.

Parameters:
array original array of double values (note that this array must have been allocated with __EGlpNumAllocArray for this function to work).

Definition at line 19614 of file base_QSopt_ex.h.

#define QScopy_array_mpf_mpq ( array   ) 

Value:

({ \
  mpf_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpq_t*__lres = mpq_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpf_cmp(__larray[__lsz],mpf_ILL_MAXDOUBLE)==0)\
      mpq_set(__lres[__lsz],mpq_ILL_MAXDOUBLE);\
    else if(mpf_cmp(__larray[__lsz],mpf_ILL_MINDOUBLE)==0)\
      mpq_set(__lres[__lsz],mpq_ILL_MINDOUBLE);\
    mpq_set_f(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpf_t array into mpq_t array.

Parameters:
array original array of double values (note that this array must have been allocated with __EGlpNumAllocArray for this function to work).

Definition at line 353 of file exact.h.

#define QScopy_array_mpf_mpq ( array   ) 

Value:

({ \
  mpf_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpq_t*__lres = mpq_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpf_cmp(__larray[__lsz],mpf_ILL_MAXDOUBLE)==0)\
      mpq_set(__lres[__lsz],mpq_ILL_MAXDOUBLE);\
    else if(mpf_cmp(__larray[__lsz],mpf_ILL_MINDOUBLE)==0)\
      mpq_set(__lres[__lsz],mpq_ILL_MINDOUBLE);\
    mpq_set_f(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpf_t array into mpq_t array.

Parameters:
array original array of double values (note that this array must have been allocated with __EGlpNumAllocArray for this function to work).

Definition at line 20138 of file QSopt_ex.h.

Referenced by QSexact_solver().

#define QScopy_array_mpq_dbl ( array   ) 

Value:

({ \
  mpq_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  double*__lres = dbl_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpq_equal(__larray[__lsz],mpq_ILL_MAXDOUBLE))\
      __lres[__lsz] = dbl_ILL_MAXDOUBLE;\
    else if(mpq_equal(__larray[__lsz],mpq_ILL_MINDOUBLE))\
      __lres[__lsz] = dbl_ILL_MINDOUBLE;\
    else __lres[__lsz] = mpq_get_d(__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpq_t array into a double array.

Parameters:
array mpq_t array from where we will create the values.

Definition at line 19561 of file base_QSopt_ex.h.

#define QScopy_array_mpq_dbl ( array   ) 

Value:

({ \
  mpq_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  double*__lres = dbl_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpq_equal(__larray[__lsz],mpq_ILL_MAXDOUBLE))\
      __lres[__lsz] = dbl_ILL_MAXDOUBLE;\
    else if(mpq_equal(__larray[__lsz],mpq_ILL_MINDOUBLE))\
      __lres[__lsz] = dbl_ILL_MINDOUBLE;\
    else __lres[__lsz] = mpq_get_d(__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpq_t array into a double array.

Parameters:
array mpq_t array from where we will create the values.

Definition at line 300 of file exact.h.

#define QScopy_array_mpq_dbl ( array   ) 

Value:

({ \
  mpq_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  double*__lres = dbl_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpq_equal(__larray[__lsz],mpq_ILL_MAXDOUBLE))\
      __lres[__lsz] = dbl_ILL_MAXDOUBLE;\
    else if(mpq_equal(__larray[__lsz],mpq_ILL_MINDOUBLE))\
      __lres[__lsz] = dbl_ILL_MINDOUBLE;\
    else __lres[__lsz] = mpq_get_d(__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpq_t array into a double array.

Parameters:
array mpq_t array from where we will create the values.

Definition at line 20085 of file QSopt_ex.h.

Referenced by QScopy_prob_mpq_dbl().

#define QScopy_array_mpq_mpf ( array   ) 

Value:

({ \
  mpq_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpf_t*__lres = mpf_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpq_equal(__larray[__lsz],mpq_ILL_MAXDOUBLE))\
      mpf_set(__lres[__lsz], mpf_ILL_MAXDOUBLE);\
    else if(mpq_equal(__larray[__lsz],mpq_ILL_MINDOUBLE))\
      mpf_set(__lres[__lsz], mpf_ILL_MINDOUBLE);\
    else mpf_set_q(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpq_t array into a mpf_t array.

Parameters:
array mpq_t array from where we will create the values.

Definition at line 19578 of file base_QSopt_ex.h.

#define QScopy_array_mpq_mpf ( array   ) 

Value:

({ \
  mpq_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpf_t*__lres = mpf_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpq_equal(__larray[__lsz],mpq_ILL_MAXDOUBLE))\
      mpf_set(__lres[__lsz], mpf_ILL_MAXDOUBLE);\
    else if(mpq_equal(__larray[__lsz],mpq_ILL_MINDOUBLE))\
      mpf_set(__lres[__lsz], mpf_ILL_MINDOUBLE);\
    else mpf_set_q(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpq_t array into a mpf_t array.

Parameters:
array mpq_t array from where we will create the values.

Definition at line 317 of file exact.h.

#define QScopy_array_mpq_mpf ( array   ) 

Value:

({ \
  mpq_t*__larray = (array);\
  register unsigned __lsz = __EGlpNumArraySize(__larray);\
  mpf_t*__lres = mpf_EGlpNumAllocArray(__lsz);\
  while(__lsz--)\
  {\
    if(mpq_equal(__larray[__lsz],mpq_ILL_MAXDOUBLE))\
      mpf_set(__lres[__lsz], mpf_ILL_MAXDOUBLE);\
    else if(mpq_equal(__larray[__lsz],mpq_ILL_MINDOUBLE))\
      mpf_set(__lres[__lsz], mpf_ILL_MINDOUBLE);\
    else mpf_set_q(__lres[__lsz],__larray[__lsz]);\
  }\
  __lres;})
create a copy of a mpq_t array into a mpf_t array.

Parameters:
array mpq_t array from where we will create the values.

Definition at line 20102 of file QSopt_ex.h.

Referenced by QScopy_prob_mpq_mpf().

#define QSEXACT_SAVE_INT   0

If enabled, save the intermediate problems created by the functions QScopy_prob_mpq_dbl and QScopy_prob_mpq_mpf.

Definition at line 19477 of file base_QSopt_ex.h.

#define QSEXACT_SAVE_INT   0

If enabled, save the intermediate problems created by the functions QScopy_prob_mpq_dbl and QScopy_prob_mpq_mpf.

Definition at line 216 of file exact.h.

#define QSEXACT_SAVE_INT   0

If enabled, save the intermediate problems created by the functions QScopy_prob_mpq_dbl and QScopy_prob_mpq_mpf.

Definition at line 20001 of file QSopt_ex.h.

#define QSEXACT_SAVE_OPTIMAL   0

If enabled, save the last problem proved to be optimal, and its solution.

Definition at line 19472 of file base_QSopt_ex.h.

#define QSEXACT_SAVE_OPTIMAL   0

If enabled, save the last problem proved to be optimal, and its solution.

Definition at line 211 of file exact.h.

#define QSEXACT_SAVE_OPTIMAL   0

If enabled, save the last problem proved to be optimal, and its solution.

Definition at line 19996 of file QSopt_ex.h.

#define QSexact_set_precision ( precision   )     mpf_QSset_precision(precision)

Set the number of bits to use with mpf_t type numbers and change all internal constants as needed.

Definition at line 19638 of file base_QSopt_ex.h.

#define QSexact_set_precision ( precision   )     mpf_QSset_precision(precision)

Set the number of bits to use with mpf_t type numbers and change all internal constants as needed.

Definition at line 377 of file exact.h.

#define QSexact_set_precision ( precision   )     mpf_QSset_precision(precision)

Set the number of bits to use with mpf_t type numbers and change all internal constants as needed.

Definition at line 20162 of file QSopt_ex.h.

Referenced by main(), and QSexact_solver().


Function Documentation

void EXutilApproximate ( mpq_t  dest,
mpq_t  ori,
unsigned const   max_den 
)

Approximate using continued fractions method a given rational $\frac{a}{b} $ with another rational $\frac{a'}{b'}$ that satisfy that $ b' < max_den^2 $ and also $|\frac{a}{b} - \frac{a'}{b'}|\leq\frac1{max_den^2}$.

Parameters:
ori original coefficient that we want to represent as a/b with b <= max_den^2.
dest we return here the resulting number.
max_den maximum allowed denominator in the new representation.

Definition at line 262 of file eg_exutil.c.

References cvl, and Z.

Referenced by EXutilNicefy(), and EXutilOverEstimate().

void EXutilDoClear ( void   ) 

Clear all memory related to the static variables.

Definition at line 50 of file eg_exutil.c.

References cvl, and Z.

Referenced by QSexactClear().

void EXutilDoInit ( void   ) 

Initialize the static variables at start-up.

Definition at line 39 of file eg_exutil.c.

References cvl, and Z.

Referenced by QSexactStart().

int EXutilExpandLogicals ( mpq_QSdata *const   act_lp,
mpq_t *const   vector,
mpq_t  rhs,
mpq_ILLlp_rows *const   lprows 
)

Given a vector in QSopt external form, and a row description of the related LP, re-write the vector using only real variables, we do that by substracting the equation defining the logical variable multiplied by the coefficient of the logical variable in the vector to the vector.

Parameters:
act_lp lp where we are working.
vector vector of length at least nrows + nstruct where we want to replace all logical coefficients.
lprows row description of the given LP.
rhs if we look at vector,rhs as an inequality, then we eliminate the slack coefficient form the inequality as a whole.
Returns:
zero on success, non-zero otherwise.

Definition at line 220 of file eg_exutil.c.

References mpq_ILLlpdata::A, cvl, EX_UTIL_VERBOSE, mpq_ILLmatrix::matbeg, mpq_ILLmatrix::matval, mpq_ILLlpdata::nrows, mpq_ILLlpdata::nstruct, mpq_qsdata::qslp, mpq_ILLlpdata::rhs, mpq_ILLlp_rows::rowbeg, mpq_ILLlp_rows::rowcnt, mpq_ILLlp_rows::rowind, mpq_ILLlpdata::rowmap, mpq_ILLlpdata::rownames, and mpq_ILLlp_rows::rowval.

int EXutilIntegralize ( const unsigned  n,
mpq_t *const   a,
mpq_t  b,
mpq_t  maxabs 
)

given a cut ax <=> b, write it in integer form ,i.e. set all a,b to integer in such a way that a_i and b are all relativelly prime.

Parameters:
n size of the a vector.
a RHS of the inequality
b LHS of the inequality.
maxabs return the maximum absolute value among all resulting a_i,b.
Returns:
zero on success, non-zero otherwise.

Definition at line 63 of file eg_exutil.c.

Referenced by EXutilSimplify().

void EXutilNicefy ( mpq_QSdata *const   act_prob,
const unsigned char *const   var_stat,
const unsigned  max_den,
mpq_t *  a,
mpq_t  b,
int const   sense 
)

Given an inequality, we try to re-write so that no denominator is bigger than the square of the given number, and ensuring validity. for coefficients that can't be `nacified' we leave them intact. the process imply adding multiples of the bounds on variables, and at the end, nicify the rhs of the inequality.

Parameters:
max_den the square of this value is the maximum denominator allowed.
a hand side of the inequality.
sense sense of the inequality, it should be either 'L' or 'G'.
b right hand side of the inequality.
act_prob LP from where we draw the bounds on the variables.
var_stat status (as defined in EXmipinfo_t::var_stat) for all variables in the LP, in the internal QSopt ordering.
Note:
The length of the a vector is at least nstruct, and we assume that entry a[k] corresnpond to the coefficient associated with the k-th structural variable inside.

Definition at line 368 of file eg_exutil.c.

References EX_STATUS_LB, EX_STATUS_UB, EXutilApproximate(), mpq_ILLlpdata::lower, mpq_ILL_MAXDOUBLE, mpq_ILL_MINDOUBLE, mpq_ILLlpdata::nstruct, mpq_qsdata::qslp, mpq_ILLlpdata::structmap, and mpq_ILLlpdata::upper.

Here is the call graph for this function:

void EXutilOverEstimate ( mpq_t  dest,
mpq_t  ori,
unsigned const   max_den 
)

Overestimate the given coefficient by another rational that is representble with denominators not bigger than max_den^2.

Parameters:
ori original coefficient that we want to represent as a/b with b <= max_den^2.
dest we return here the resulting number, note that we always insure that the returned value is bigger than the original value.
max_den maximum allowed denominator in the new representation.

Definition at line 352 of file eg_exutil.c.

References cvl, and EXutilApproximate().

Here is the call graph for this function:

int EXutilSimplify ( const unsigned  n,
mpq_t *const   a,
mpq_t  b 
)

given a cut ax <=> b, write it in normalized form ,i.e. set all a,b to integer in such a way that a_i and b are all relativelly prime, and divide them all over the maximum such (a_i,b) (so that the infinity norm of (a,b) is one.

Parameters:
n size of the a vector.
a RHS of the inequality
b LHS of the inequality.
Returns:
zero on success, non-zero otherwise.

Definition at line 105 of file eg_exutil.c.

References EXutilIntegralize().

Referenced by main().

Here is the call graph for this function:

static void infeasible_output ( mpq_QSdata p_mpq,
mpq_t *const   y,
mpq_t *  y_mpq 
) [static]

print into screen (if enable) a message indicating that we have successfully prove infeasibility, and save (if y is non NULL ) the dual ray solution provided in y_mpq.

Parameters:
p_mpq the problem data.
y where to store the optimal dual solution (if not null).
y_mpq the optimal dual solution.

Definition at line 947 of file exact.c.

References __sp, and mpq_qsdata::simplex_display.

Referenced by QSexact_solver().

void mpq_GomoryCoeff ( mpq_t  rop,
mpq_t  coef,
unsigned const   is_int,
int const   bound,
unsigned const   cut_mlt,
mpq_t  b_frac 
)

compute the gomory coefficient of the variable given the original coefficient, the multiplier, and all relevant information.

Parameters:
rop Where we return the gomory coefficient. (it should be different location than the original coefficient).
coef original coefficient in the equality that we are using to derive the gomory cut.
is_int this is either zero (indicating that the variable asociated with this coefficient is continuous) or one (indicating that the variable asociated with this coeffcient is integer).
bound indicate if this variable was complemented to its lower bound (then L) or to its upper bound (then U), any other value will generate an error.
cut_mlt multiplier to use to the coefficient (and thus the effective coefficient would be coef*cut_mlt).
b_frac fractional part of the RHS in the equation (after complementing variables).

Definition at line 126 of file eg_exutil.c.

References mpq_FracPart, and mpq_IsInteger.

int mpq_grab_cache ( mpq_QSdata p,
int  status 
)

Definition at line 2090 of file mpq_qsopt.c.

References mpq_qsdata::basis, mpq_qsdata::cache, mpq_ILLlp_basis::cstat, ILL_SAFE_MALLOC, mpq_qsdata::lp, mpq_ILLlib_cache_solution(), mpq_ILLlp_cache_alloc(), mpq_ILLlp_cache_free(), mpq_ILLlp_cache_init(), mpq_SZERO_TOLER, mpq_ILLlp_cache::nrows, mpq_ILLlpdata::nrows, mpq_ILLlp_cache::nstruct, mpq_ILLlpdata::nstruct, mpq_lpinfo::O, mpq_ILLlpdata::objsense, QS_COL_BSTAT_BASIC, QS_COL_BSTAT_LOWER, QS_COL_BSTAT_UPPER, mpq_qsdata::qslp, mpq_ILLlp_cache::rc, STAT_LOWER, STAT_UPPER, mpq_ILLlpdata::structmap, mpq_ILLlp_cache::val, VFIXED, mpq_lpinfo::vstat, and mpq_lpinfo::vtype.

Referenced by mpq_opt_work(), and QSexact_basis_status().

Here is the call graph for this function:

void mpq_ILLfct_check_dfeasible ( mpq_lpinfo lp,
mpq_feas_info fs,
const mpq_t  ftol 
)

Definition at line 1294 of file mpq_fct.c.

References mpq_lpinfo::dfeas, mpq_feas_info::dstatus, DUAL_FEASIBLE, mpq_lpinfo::dz, mpq_lpinfo::nbaz, mpq_lpinfo::nnbasic, STAT_LOWER, STAT_UPPER, STAT_ZERO, mpq_feas_info::totinfeas, VARTIFICIAL, VFIXED, mpq_lpinfo::vstat, and mpq_lpinfo::vtype.

Referenced by mpq_dual_phaseI_step(), mpq_dual_phaseII_step(), mpq_ILLbasis_get_cinitial(), mpq_ILLsimplex(), mpq_ILLsimplex_retest_dsolution(), mpq_ILLsimplex_retest_psolution(), mpq_monitor_iter(), mpq_primal_phaseII_step(), QSexact_basis_dualstatus(), QSexact_basis_optimalstatus(), and QSexact_basis_status().

void mpq_ILLfct_check_pfeasible ( mpq_lpinfo lp,
mpq_feas_info fs,
const mpq_t  ftol 
)

Definition at line 1201 of file mpq_fct.c.

References mpq_lpinfo::baz, mpq_lpinfo::bfeas, ILL_IFTRACE, mpq_lpinfo::lz, mpq_INFTY, mpq_NINFTY, mpq_lpinfo::nrows, PRIMAL_FEASIBLE, mpq_feas_info::pstatus, QSE_WLVL, mpq_feas_info::totinfeas, mpq_lpinfo::uz, and mpq_lpinfo::xbz.

Referenced by mpq_dual_phaseII_step(), mpq_ILLbasis_get_cinitial(), mpq_ILLsimplex(), mpq_ILLsimplex_retest_dsolution(), mpq_ILLsimplex_retest_psolution(), mpq_primal_phaseI_step(), mpq_primal_phaseII_step(), QSexact_basis_optimalstatus(), and QSexact_basis_status().

void mpq_ILLfct_compute_dobj ( mpq_lpinfo lp  ) 

Definition at line 194 of file mpq_fct.c.

References mpq_lpinfo::bz, mpq_lpinfo::dobjval, mpq_lpinfo::dz, mpq_lpinfo::lz, mpq_lpinfo::nbaz, mpq_lpinfo::nnbasic, mpq_lpinfo::nrows, mpq_lpinfo::objval, mpq_lpinfo::piz, STAT_LOWER, STAT_UPPER, mpq_lpinfo::uz, and mpq_lpinfo::vstat.

Referenced by mpq_dual_phaseII_step(), mpq_ILLsimplex(), mpq_ILLsimplex_retest_dsolution(), mpq_monitor_iter(), and QSexact_basis_dualstatus().

void mpq_ILLfct_compute_dz ( mpq_lpinfo lp  ) 

Definition at line 293 of file mpq_fct.c.

References mpq_lpinfo::cz, mpq_lpinfo::dz, mpq_lpinfo::matbeg, mpq_lpinfo::matcnt, mpq_lpinfo::matind, mpq_lpinfo::matval, mpq_lpinfo::nbaz, mpq_lpinfo::nnbasic, and mpq_lpinfo::piz.

Referenced by mpq_dual_phaseI_step(), mpq_dual_phaseII_step(), mpq_ILLbasis_get_cinitial(), mpq_ILLfct_unroll_coef_change(), mpq_ILLsimplex(), mpq_ILLsimplex_retest_dsolution(), mpq_ILLsimplex_retest_psolution(), mpq_primal_phaseII_step(), QSexact_basis_dualstatus(), QSexact_basis_optimalstatus(), and QSexact_basis_status().

void mpq_ILLfct_compute_phaseI_piz ( mpq_lpinfo lp  ) 

Definition at line 360 of file mpq_fct.c.

References mpq_lpinfo::bfeas, mpq_svector::coef, mpq_svector::indx, mpq_lpinfo::nrows, mpq_lpinfo::pIpiz, mpq_lpinfo::srhs, and mpq_lpinfo::ssoln.

Referenced by mpq_ILLsimplex_retest_psolution(), mpq_primal_phaseI_step(), and QSexact_basis_status().

void mpq_ILLfct_compute_piz ( mpq_lpinfo lp  ) 

Definition at line 269 of file mpq_fct.c.

References mpq_lpinfo::baz, mpq_svector::coef, mpq_lpinfo::cz, mpq_svector::indx, mpq_lpinfo::nrows, mpq_lpinfo::piz, mpq_lpinfo::srhs, and mpq_lpinfo::ssoln.

Referenced by mpq_dual_phaseI_step(), mpq_dual_phaseII_step(), mpq_ILLbasis_get_cinitial(), mpq_ILLfct_unroll_coef_change(), mpq_ILLsimplex(), mpq_ILLsimplex_retest_dsolution(), mpq_ILLsimplex_retest_psolution(), mpq_primal_phaseII_step(), QSexact_basis_dualstatus(), QSexact_basis_optimalstatus(), and QSexact_basis_status().

void mpq_ILLfct_compute_xbz ( mpq_lpinfo lp  ) 

Definition at line 220 of file mpq_fct.c.

References mpq_lpinfo::bz, mpq_svector::coef, mpq_svector::indx, mpq_lpinfo::lz, mpq_lpinfo::matbeg, mpq_lpinfo::matcnt, mpq_lpinfo::matind, mpq_lpinfo::matval, mpq_lpinfo::nbaz, mpq_lpinfo::nnbasic, mpq_lpinfo::nrows, mpq_lpinfo::srhs, mpq_lpinfo::ssoln, STAT_LOWER, STAT_UPPER, mpq_lpinfo::uz, mpq_lpinfo::vstat, and mpq_lpinfo::xbz.

Referenced by mpq_dual_phaseII_step(), mpq_ILLbasis_get_cinitial(), mpq_ILLfct_unroll_bound_change(), mpq_ILLsimplex(), mpq_ILLsimplex_retest_dsolution(), mpq_ILLsimplex_retest_psolution(), mpq_primal_phaseI_step(), mpq_primal_phaseII_step(), QSexact_basis_optimalstatus(), and QSexact_basis_status().

void mpq_ILLfct_set_status_values ( mpq_lpinfo lp,
int  pstatus,
int  dstatus,
int  ptype,
int  dtype 
)

Definition at line 1416 of file mpq_fct.c.

References mpq_lpinfo::basisstat, DUAL_FEASIBLE, mpq_lp_status_info::dual_feasible, mpq_lp_status_info::dual_infeasible, DUAL_INFEASIBLE, DUAL_UNBOUNDED, mpq_lp_status_info::dual_unbounded, mpq_lpinfo::nbchange, mpq_lpinfo::ncchange, mpq_lp_status_info::optimal, PHASEI, PHASEII, PRIMAL_FEASIBLE, mpq_lp_status_info::primal_feasible, mpq_lp_status_info::primal_infeasible, PRIMAL_INFEASIBLE, PRIMAL_UNBOUNDED, mpq_lp_status_info::primal_unbounded, and mpq_lpinfo::probstat.

Referenced by mpq_dual_phaseI_step(), mpq_dual_phaseII_step(), mpq_ILLsimplex(), mpq_monitor_iter(), mpq_primal_phaseI_step(), mpq_primal_phaseII_step(), mpq_terminate_simplex(), QSexact_basis_dualstatus(), QSexact_basis_optimalstatus(), and QSexact_basis_status().

void mpq_ILLfct_set_variable_type ( mpq_lpinfo lp  ) 

Definition at line 129 of file mpq_fct.c.

References CLASS_LOGICAL, CLASS_STRUCT, mpq_lpinfo::lz, mpq_lpinfo::matbeg, mpq_lpinfo::matcnt, mpq_lpinfo::matind, mpq_INFTY, mpq_NINFTY, mpq_lpinfo::ncols, mpq_lpinfo::O, mpq_ILLlpdata::rowmap, mpq_lpinfo::uz, VARTIFICIAL, VBOUNDED, mpq_lpinfo::vclass, VFIXED, VFREE, VLOWER, mpq_lpinfo::vtype, and VUPPER.

Referenced by mpq_ILLsimplex(), QSexact_basis_dualstatus(), QSexact_basis_optimalstatus(), and QSexact_basis_status().

static void optimal_output ( mpq_QSdata p_mpq,
mpq_t *const   x,
mpq_t *const   y,
mpq_t *  x_mpq,
mpq_t *  y_mpq 
) [static]

print into screen (if enable) a message indicating that we have successfully solved the problem at optimality, and save (if x and y are non NULL respectivelly) the optimal primal/dual solution provided in x_mpq and y_mpq.

Parameters:
p_mpq the problem data.
x where to store the optimal primal solution (if not null).
y where to store the optimal dual solution (if not null).
x_mpq the optimal primal solution.
y_mpq the optimal dual solution.

Definition at line 976 of file exact.c.

References __sp, and mpq_qsdata::simplex_display.

Referenced by QSexact_solver().

dbl_QSdata * QScopy_prob_mpq_dbl ( mpq_QSdata p,
const char *  newname 
)

Copy an exact problem (mpq_QSdata) to a regular double version of the problem (dbl_QSdata).

Definition at line 155 of file exact.c.

References dbl_QSadd_ranged_rows(), dbl_QScreate_prob(), dbl_QSfree_prob(), dbl_QSnew_col(), dbl_QSset_param(), dbl_QSset_param_EGlpNum(), dbl_QSwrite_prob(), mpq_QSget_bounds(), mpq_QSget_colcount(), mpq_QSget_obj(), mpq_QSget_objsense(), mpq_QSget_param(), mpq_QSget_param_EGlpNum(), mpq_QSget_ranged_rows(), mpq_QSget_rowcount(), QS_PARAM_DUAL_PRICING, QS_PARAM_OBJLLIM, QS_PARAM_OBJULIM, QS_PARAM_PRIMAL_PRICING, QS_PARAM_SIMPLEX_DISPLAY, QS_PARAM_SIMPLEX_MAX_ITERATIONS, QS_PARAM_SIMPLEX_MAX_TIME, QS_PARAM_SIMPLEX_SCALING, and QScopy_array_mpq_dbl.

Referenced by main(), QSexact_solver(), and QSexact_verify().

Here is the call graph for this function:

mpf_QSdata * QScopy_prob_mpq_mpf ( mpq_QSdata p,
const char *  newname 
)

Copy an exact problem (mpq_QSdata) to a regular double version of the problem (dbl_QSdata).

Definition at line 270 of file exact.c.

References mpf_QSadd_ranged_rows(), mpf_QScreate_prob(), mpf_QSfree_prob(), mpf_QSnew_col(), mpf_QSset_param(), mpf_QSset_param_EGlpNum(), mpf_QSwrite_prob(), mpq_QSget_bounds(), mpq_QSget_colcount(), mpq_QSget_obj(), mpq_QSget_objsense(), mpq_QSget_param(), mpq_QSget_param_EGlpNum(), mpq_QSget_ranged_rows(), mpq_QSget_rowcount(), QS_PARAM_DUAL_PRICING, QS_PARAM_OBJLLIM, QS_PARAM_OBJULIM, QS_PARAM_PRIMAL_PRICING, QS_PARAM_SIMPLEX_DISPLAY, QS_PARAM_SIMPLEX_MAX_ITERATIONS, QS_PARAM_SIMPLEX_MAX_TIME, QS_PARAM_SIMPLEX_SCALING, and QScopy_array_mpq_mpf.

Referenced by QSexact_solver().

Here is the call graph for this function:

int QSexact_basis_dualstatus ( mpq_QSdata p_mpq,
QSbasis basis,
char *  result,
mpq_t *  dobjval,
const int  msg_lvl 
)

test whether given basis is dual feasible in rational arithmetic.

Parameters:
p_mpq the problem data.
basis basis to be tested.
result where to store whether given basis is dual feasible.
dobjval where to store dual solution value in case of dual feasibility (if not NULL).
msg_lvl message level.

Definition at line 1188 of file exact.c.

References mpq_feas_info::dstatus, ILL_IFFREE, mpq_build_internal_lpinfo(), mpq_free_internal_lpinfo(), mpq_ILLbasis_factor(), mpq_ILLbasis_load(), mpq_ILLfct_check_dfeasible(), mpq_ILLfct_compute_dobj(), mpq_ILLfct_compute_dz(), mpq_ILLfct_compute_piz(), mpq_ILLfct_set_status_values(), mpq_ILLfct_set_variable_type(), mpq_ILLlp_cache_free(), mpq_ILLlp_rows_clear(), mpq_ILLlp_sinfo_free(), mpq_init_internal_lpinfo(), mpq_QSload_basis(), PHASEII, mpq_feas_info::pstatus, QS_LP_MODIFIED, and mpq_feas_info::totinfeas.

Referenced by QSexact_verify().

Here is the call graph for this function:

int QSexact_basis_optimalstatus ( mpq_QSdata p_mpq,
QSbasis basis,
char *  result,
const int  msg_lvl 
)

test whether given basis is primal and dual feasible in rational arithmetic.

Parameters:
p_mpq the problem data.
basis basis to be tested.
result where to store whether given basis is primal and dual feasible.
msg_lvl message level.

Definition at line 1101 of file exact.c.

References mpq_feas_info::dstatus, ILL_IFFREE, mpq_build_internal_lpinfo(), mpq_free_internal_lpinfo(), mpq_ILLbasis_factor(), mpq_ILLbasis_load(), mpq_ILLfct_check_dfeasible(), mpq_ILLfct_check_pfeasible(), mpq_ILLfct_compute_dz(), mpq_ILLfct_compute_piz(), mpq_ILLfct_compute_xbz(), mpq_ILLfct_set_status_values(), mpq_ILLfct_set_variable_type(), mpq_ILLlp_cache_free(), mpq_ILLlp_rows_clear(), mpq_ILLlp_sinfo_free(), mpq_init_internal_lpinfo(), mpq_QSload_basis(), PHASEII, mpq_feas_info::pstatus, QS_LP_MODIFIED, and mpq_feas_info::totinfeas.

Here is the call graph for this function:

static int QSexact_basis_status ( mpq_QSdata p_mpq,
int *  status,
QSbasis *const   basis,
const int  msg_lvl,
int *const   simplexalgo 
) [static]

get the status for a given basis in rational arithmetic, it should also leave everything set to get primal/dual solutions when needed.

Definition at line 1005 of file exact.c.

References mpq_feas_info::dstatus, ILL_IFFREE, mpq_build_internal_lpinfo(), mpq_free_internal_lpinfo(), mpq_grab_cache(), mpq_ILLbasis_factor(), mpq_ILLbasis_load(), mpq_ILLfct_check_dfeasible(), mpq_ILLfct_check_pfeasible(), mpq_ILLfct_compute_dz(), mpq_ILLfct_compute_phaseI_piz(), mpq_ILLfct_compute_piz(), mpq_ILLfct_compute_xbz(), mpq_ILLfct_set_status_values(), mpq_ILLfct_set_variable_type(), mpq_ILLlp_cache_free(), mpq_ILLlp_rows_clear(), mpq_ILLlp_sinfo_free(), mpq_init_internal_lpinfo(), mpq_QSload_basis(), PHASEII, PRIMAL_PHASEI, PRIMAL_SIMPLEX, mpq_feas_info::pstatus, QS_LP_INFEASIBLE, QS_LP_MODIFIED, QS_LP_OPTIMAL, QS_LP_UNBOUNDED, QS_LP_UNSOLVED, and mpq_feas_info::totinfeas.

Referenced by QSexact_solver().

Here is the call graph for this function:

int QSexact_infeasible_test ( mpq_QSdata p,
mpq_t *  d_sol 
)

Check if the given dual vector is a proof of infeasibility for the given exact problem.

Parameters:
p pointer to the problem data structure.
d_sol array of length at least nrows with the suposed proof of infeasibility.
Returns:
zero if the given dual vector is indeed a proof of infeasibility for the problem, non zero otherwise.
Description:
Note that for infeasibility, we just need to proof that the problem

\[ \begin{array}{ll} \min & 0\\ s.t. & Ax = b\\ & l\leq x\leq b\\ \end{array} \]

is infeasible, but it's dual is

\[ \begin{array}{ll} \max & by - ud_u + ld_l\\ s.t. & A^ty +Id_l - Id_u = 0\\ & d_u,d_l\geq0\\ \end{array} \]

wich is always feasible (provided $y\geq0$ (set $ (y,d_u,d_l)=0$), and thus we just need to check whether the objective value is $\neq 0$ and we have a proof of infeasibility for the primal. That's what this function perform as a test.

Definition at line 821 of file exact.c.

References __QS_SB_VERB, mpq_ILLlpdata::A, DEBUG, mpq_ILLlpdata::lower, mpq_qsdata::lp, mpq_ILLmatrix::matbeg, mpq_ILLmatrix::matcnt, mpq_ILLmatrix::matind, mpq_ILLmatrix::matval, mpq_ILL_MAXDOUBLE, mpq_ILL_MINDOUBLE, mpq_ILLlpdata::ncols, mpq_ILLlpdata::nrows, mpq_lpinfo::O, QS_LP_INFEASIBLE, mpq_qsdata::qstatus, mpq_ILLlpdata::rhs, mpq_qsdata::simplex_display, and mpq_ILLlpdata::upper.

Referenced by QSexact_solver().

int QSexact_optimal_test ( mpq_QSdata p,
mpq_t *  p_sol,
mpq_t *  d_sol,
QSbasis basis 
)

Test if a given primal/dual solution is feasible and has the same objective value.

Parameters:
p original problem.
p_sol primal solution candidate.
d_sol dual solution candidate.
basis Basis for wich the current primal/dual vector is a solution.
Returns:
one if the given primal/dual solution is optimal, zero otherwise.
Description:
The input problem has the form

\[ \begin{array}{l}\min cx\\ s.t. \begin{array}{lcl}Ax&=&b\end{array}\\ l\leq x\leq u\end{array} \]

where some of the bounds can be $\infty$ or $-\infty$. Note that from this the dual problem is allways feasible (we treat $\infty$ as a suitable large number) because it looks like

\[ \begin{array}{l}\max by + d_uu-d_ll\\ s.t. \begin{array}{lcl}A^ty-Id_l+Id_u & =& c \end{array}\\ d_u,d_l\geq0\end{array} \]

thus we just need to check primal feasibility and complementary slackness (just to be sure we also check that both dual and primal objective values coincide.

If the optimality test is true (i.e. the basis and the given solution, wich might have been modified inside the function) then this function store the optimal solution into the cache of the problem.

Note:
We assume that p_sol and d_sol have the right size for the problem. and moreover, we assume that the problem already has the logical variables added in (to transform it into standard form), this allow us to fix somewhat the primal vector solution to try to get an optimality certificate.

Definition at line 391 of file exact.c.

References __QS_SB_VERB, mpq_ILLlpdata::A, mpq_ILLlpdata::colnames, qsbasis::cstat, DEBUG, mpq_ILLlpdata::lower, mpq_qsdata::lp, mpq_ILLmatrix::matbeg, mpq_ILLmatrix::matcnt, mpq_ILLmatrix::matind, mpq_ILLmatrix::matval, mpq_ILLlp_cache_alloc(), mpq_ILLlp_cache_free(), mpq_ILLlp_cache_init(), mpq_QSload_basis(), mpq_QSwrite_prob(), mpq_ILLlpdata::ncols, mpq_ILLlpdata::nrows, qsbasis::nrows, mpq_ILLlpdata::nstruct, qsbasis::nstruct, mpq_lpinfo::O, mpq_ILLlpdata::obj, mpq_ILLlpdata::objsense, QS_COL_BSTAT_BASIC, QS_COL_BSTAT_FREE, QS_COL_BSTAT_LOWER, QS_COL_BSTAT_UPPER, QS_LP_OPTIMAL, QS_MIN, QS_ROW_BSTAT_BASIC, QS_ROW_BSTAT_LOWER, QS_ROW_BSTAT_UPPER, QSexact_print_sol(), mpq_ILLlpdata::rhs, mpq_ILLlpdata::rowmap, mpq_ILLlpdata::rownames, qsbasis::rstat, mpq_qsdata::simplex_display, mpq_ILLlpdata::structmap, and mpq_ILLlpdata::upper.

Referenced by QSexact_solver(), and QSexact_verify().

Here is the call graph for this function:

int QSexact_print_sol ( mpq_QSdata p,
EGioFile_t *  out_f 
)

Print into a file the optimal solution.

Parameters:
p original problem.
out_f file where to write the solution.
Returns:
zero on success, non-zero otherwise.

Definition at line 51 of file exact.c.

References mpq_QSget_colcount(), mpq_QSget_objval(), mpq_QSget_pi_array(), mpq_QSget_rc_array(), mpq_QSget_rowcount(), mpq_QSget_slack_array(), mpq_QSget_status(), mpq_QSget_x_array(), QS_LP_ABORTED, QS_LP_INFEASIBLE, QS_LP_ITER_LIMIT, QS_LP_MODIFIED, QS_LP_OPTIMAL, QS_LP_TIME_LIMIT, QS_LP_UNBOUNDED, and QS_LP_UNSOLVED.

Referenced by main(), and QSexact_optimal_test().

Here is the call graph for this function:

int QSexact_solver ( mpq_QSdata p_mpq,
mpq_t *const   x,
mpq_t *const   y,
QSbasis *const   basis,
int  simplexalgo,
int *  status 
)

Given an mpq_QSdata problem, solve it exactly.

Parameters:
x if not null, we store here the primal solution to the problem (if it exist).
y if not null, we store here the dual solution to the problem,
p_mpq problem to solve exactly.
status pointer to the integer where we will return the status of the problem, either optimal, infeasible, or unbounded (we could also return time out).
simplexalgo whether to use primal or dual simplex while solving to optimality the problem.
basis if not null, use the given basis to start the iteration of simplex, and store here the optimal basis (if found).
Returns:
zero on success, non-zero otherwise.

Definition at line 1441 of file exact.c.

References __QS_SB_VERB, __sp, mpf_qsdata::basis, mpf_lpinfo::basisid, qsbasis::cstat, dbl_ILLeditor_solve(), dbl_QSfree_prob(), dbl_QSget_basis(), dbl_QSget_infeas_array(), dbl_QSget_itcnt(), dbl_QSget_pi_array(), dbl_QSget_status(), dbl_QSget_x_array(), dbl_QSload_basis(), dbl_QSopt_primal(), DEBUG, DUAL_PHASEII, DUAL_SIMPLEX, mpf_qsdata::factorok, ILL_IFFREE, infeasible_output(), mpf_qsdata::lp, mpf_ILLeditor_solve(), mpf_ILLlp_basis_free(), mpf_QSfree_basis(), mpf_QSfree_prob(), mpf_QSget_basis(), mpf_QSget_infeas_array(), mpf_QSget_itcnt(), mpf_QSget_pi_array(), mpf_QSget_status(), mpf_QSget_x_array(), mpf_QSload_basis(), mpf_QSopt_primal(), mpf_QSwrite_prob(), mpq_ILLeditor_solve(), mpq_QSfree_basis(), mpq_QSget_infeas_array(), mpq_QSget_pi_array(), mpq_QSget_status(), mpq_QSget_x_array(), mpq_QSload_basis(), mpq_QSset_param(), mpq_QSwrite_prob(), qsbasis::nrows, qsbasis::nstruct, optimal_output(), precision, PRIMAL_PHASEI, PRIMAL_SIMPLEX, QS_EXACT_MAX_ITER, QS_LP_INFEASIBLE, QS_LP_OBJ_LIMIT, QS_LP_OPTIMAL, QS_LP_UNBOUNDED, QS_LP_UNSOLVED, QS_PARAM_SIMPLEX_MAX_ITERATIONS, QScopy_array_dbl_mpq, QScopy_array_mpf_mpq, QScopy_prob_mpq_dbl(), QScopy_prob_mpq_mpf(), QSexact_basis_status(), QSexact_infeasible_test(), QSexact_optimal_test(), QSexact_set_precision, qsbasis::rstat, mpf_qsdata::simplex_display, dbl_qsdata::simplex_display, and mpq_qsdata::simplex_display.

Referenced by main().

Here is the call graph for this function:

int QSexact_verify ( mpq_QSdata p_mpq,
QSbasis basis,
int  useprestep,
double *  dbl_p_sol,
double *  dbl_d_sol,
char *  result,
mpq_t *  dobjval,
const int  msg_lvl 
)

test whether given basis is dual feasible in rational arithmetic. if wanted it will first directly test the corresponding approximate dual and primal solution (corrected via dual variables for bounds and primal variables for slacks if possible) for optimality before performing the dual feasibility test on the more expensive exact basic solution.

Parameters:
p_mpq the problem data.
basis basis to be tested.
useprestep whether to directly test approximate primal and dual solution first.
dbl_p_sol approximate primal solution to use in prestep (NULL in order to compute it by dual simplex in double precision with given starting basis).
dbl_d_sol approximate dual solution to use in prestep (NULL in order to compute it by dual simplex in double precision with given starting basis).
result where to store whether given basis is dual feasible.
dobjval where to store dual solution value in case of dual feasibility (if not NULL).
msg_lvl message level.

Definition at line 1292 of file exact.c.

References dbl_ILLeditor_solve(), dbl_QSfree_prob(), dbl_QSget_basis(), dbl_QSget_pi_array(), dbl_QSget_status(), dbl_QSget_x_array(), dbl_QSload_basis(), DUAL_SIMPLEX, mpq_QSget_objval(), mpq_qsdata::name, mpq_ILLlpdata::ncols, dbl_ILLlpdata::ncols, mpq_ILLlpdata::nrows, dbl_ILLlpdata::nrows, NULL, QS_LP_OPTIMAL, QScopy_array_dbl_mpq, QScopy_prob_mpq_dbl(), QSexact_basis_dualstatus(), QSexact_optimal_test(), mpq_qsdata::qslp, and dbl_qsdata::qslp.

Here is the call graph for this function:

void QSexact_write_row ( EGioFile_t *  out_f,
mpq_ILLlpdata lp,
int  row 
)

Write a given row from the LP into the given stream, in exact arithmetic.

void QSexactClear ( void   ) 

This function must be called at the end of the program to free all internal data used in the QSexact structures, once this function is called any operation on EGxxx mpq_xxx mpf_xx QSxx may fail.

Definition at line 1826 of file exact.c.

References __QSexact_setup, dbl_ILLend(), EXutilDoClear(), float128_ILLend(), fp20_ILLend(), ldbl_ILLend(), mpf_ILLend(), and mpq_ILLend().

Referenced by main().

Here is the call graph for this function:

void QSexactStart ( void   ) 

Initializator for global data, this is needed mainly for defining constants in extended floating point precision and for rational precision. This call should be done BEFORE any mpq_xxx mpf_xxx QSxx EGxx call.

Definition at line 1804 of file exact.c.

References __QSexact_setup, dbl_ILLstart(), EXutilDoInit(), float128_ILLstart(), fp20_ILLstart(), ldbl_ILLstart(), mpf_ILLstart(), and mpq_ILLstart().

Referenced by main().

Here is the call graph for this function:


Variable Documentation

int __QSexact_setup

indicate if the global data needed for QSexact has been initialized, if zero, initialization routine should be called. This is provided to allow syncronization between libraries

Definition at line 1802 of file exact.c.

int __QSexact_setup

indicate if the global data needed for QSexact has been initialized, if zero, initialization routine should be called. This is provided to allow syncronization between libraries

Definition at line 1802 of file exact.c.

int __QSexact_setup = 0

indicate if the global data needed for QSexact has been initialized, if zero, initialization routine should be called. This is provided to allow syncronization between libraries

Definition at line 1802 of file exact.c.

int __QSexact_setup

indicate if the global data needed for QSexact has been initialized, if zero, initialization routine should be called. This is provided to allow syncronization between libraries

Definition at line 1802 of file exact.c.

Referenced by QSexactClear(), and QSexactStart().

const char __sp[81] [static]

Initial value:

  "================================================================================"
Used as separator while printing output to the screen (controled by enabling simplex_display in the mpq_QSdata.

Definition at line 935 of file exact.c.

Referenced by infeasible_output(), optimal_output(), and QSexact_solver().

mpq_t cvl [static]

rational remainder used in the continued fraction method

Definition at line 36 of file eg_exutil.c.

Referenced by EXutilApproximate(), EXutilDoClear(), EXutilDoInit(), EXutilExpandLogicals(), and EXutilOverEstimate().

mpq_t mpq_ILL_MAXDOUBLE

Definition at line 96 of file mpq_lpdata.c.

mpq_t mpq_ILL_MINDOUBLE

Definition at line 97 of file mpq_lpdata.c.

mpz_t Z[7] [static]

Array of integers used in the continued fraction method.

Definition at line 34 of file eg_exutil.c.

Referenced by EXutilApproximate(), EXutilDoClear(), and EXutilDoInit().


Generated on Thu Mar 29 09:49:02 2012 for QSopt_ex by  doxygen 1.4.7