plgomory.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "sommet.h"
#include "matrix.h"
#include "plint.h"

Include dependency graph for plgomory.c:

Go to the source code of this file.

Macros
#define	MALLOC(s, t, f)   malloc((unsigned)(s))
	package plint More...

Functions
Psommet	gomory_trait_eq (Psommet eq, Variable var)
	Psommet gomory_trait_eq(Psommet eq, Variable var): Cette fonction utilise une contrainte du systeme en vue d'obtenir une coupe de Gomory servant a rendre entiere une des variables du systeme. More...
Psommet	gomory_eq (Psommet *sys, Pvecteur lvbase, int nb_som, int *no_som, Variable *var)
	Psommet gomory_eq(Psommet *sys, Pvecteur lvbase, int nb_som, int * no_som, Variable * var): Recherche d'une contrainte dont la variable de base est non entiere. More...

Macro Definition Documentation

MALLOC

#define MALLOC	(		s,
			t,
			f
	)		malloc((unsigned)(s))

package plint

Definition at line 45 of file plgomory.c.

Function Documentation

gomory_eq()

Psommet gomory_eq	(	Psommet *	sys,
		Pvecteur	lvbase,
		int	nb_som,
		int *	no_som,
		Variable *	var
	)

Psommet gomory_eq(Psommet *sys, Pvecteur lvbase, int nb_som, int * no_som, Variable * var): Recherche d'une contrainte dont la variable de base est non entiere.

resultat retourne par la fonction :

Psommet : contrainte dont la variable de base est non entiere

Les parametres de la fonction :

Psommet sys : systeme lineaire Pvecteur lvbase: liste des variables de base du systeme int nb_som : nombre de contraintes du systeme int no_som : place de la contrainte dans le systeme (no de la ligne) Variable var: variable non entiere

on a trouve une variable de base non entiere

on choisit celle de plus grand denominateur

Definition at line 153 of file plgomory.c.

{
    Psommet eq=NULL;
    Psommet result= NULL;
    int nb_som1 = nb_som;
    Value a;
    Value max = VALUE_ZERO;
    Variable v1 = NULL;
    bool borne = true;
 
#ifdef TRACE
    printf(" **  Gomory - recherche d'une variable non_entiere \n");
#endif
    *var = NULL;
 
    for (eq = *sys ;eq != NULL && borne; eq=eq->succ) {
        Value b0,den2;
 
        if ((borne = test_borne(eq))) {
            if (((v1 = find_vbase(eq,lvbase))) !=  NULL) {
                den2 = vect_coeff(v1,eq->vecteur);
                b0 = value_uminus(vect_coeff(TCST,eq->vecteur));
 
                /* on a trouve une variable de base non entiere   */
                /* on choisit celle de plus grand denominateur     */
 
                if (value_notzero_p(value_mod(b0,den2))) { 
                    Value p1=eq->denominateur;
                    Value p2 = value_abs(b0);
                    Value p3 = pgcd(p2,p1);
 
                    a = value_div(p1,p3);
                    value_absolute(a);
                    if (value_gt(a,max)) {
                        max = a;
                        *var = v1;
                        *no_som = nb_som1;
                        result = eq;
                    }
                }
            }
            nb_som1 --;
        }
        else {
#ifdef TRACE    
            printf (" --  le systeme est non borne !!! \n ");
#endif
            sommets_rm(*sys);
            *sys = NULL;
        }
    }
    if (value_notzero_p(max))
        return (result);
    else
        return (NULL);
}

References eq, find_vbase(), max, pgcd, printf(), sommets_rm(), Scontrainte::succ, TCST, test_borne(), value_abs, value_absolute, value_div, value_gt, value_mod, value_notzero_p, value_uminus, VALUE_ZERO, vect_coeff(), and Scontrainte::vecteur.

Referenced by plint_pas().

Here is the call graph for this function:

Here is the caller graph for this function:

gomory_trait_eq()

Psommet gomory_trait_eq	(	Psommet	eq,
		Variable	var
	)

Psommet gomory_trait_eq(Psommet eq, Variable var): Cette fonction utilise une contrainte du systeme en vue d'obtenir une coupe de Gomory servant a rendre entiere une des variables du systeme.

resultat retourne par la fonction :

Psommet : inegalite correspondant a la coupe qu'il faut ajouter au systeme pour rendre la variable entiere

Les parametres de la fonction :

Psommet eq : contrainte du systeme dont la variable de base est non entiere Variable var : variable de base non entiere

calcul du determinant D

calcul de la coupe de Gomory

calcul de lambda = coefficient multiplicateur permettant d'obtenir la coupe optimale

optimisation de la coupe de Gomory

Definition at line 62 of file plgomory.c.

{
    Psommet ps1 = NULL;
    Pvecteur pv1,pv2;
    Value in1;
    Value b0;
    Value lambda = VALUE_ONE;
    int sgn_op= 1;
    Value d = VALUE_ONE;
 
#ifdef TRACE
    printf(" ** Gomory - ajout d'une eq. verifiant les cond. de Gomory \n");
#endif
 
    if (eq != NULL && var != NULL)
    {
        /* calcul du determinant D      */
        Value p1, p2,tmp;
        p1 = vect_coeff(var,eq->vecteur);
        value_absolute(p1);
        p2 =vect_pgcd_all(eq->vecteur);
        value_absolute(p2);
 
        d = value_div(p1,p2);
 
        /* calcul de la coupe de Gomory */
        ps1= (Psommet)MALLOC(sizeof(Ssommet),SOMMET,"gomory_trait_eq");
        ps1->eq_sat = (int *)MALLOC(sizeof(int),INTEGER,"gomory_trait_eq");
        pv1 = vect_dup(eq->vecteur);
        ps1->denominateur = VALUE_ONE;
        *(ps1->eq_sat) = -1;
        ps1->succ = NULL;
        vect_chg_coeff(&pv1,var,VALUE_ZERO);
        ps1->vecteur = pv1;
        tmp = vect_coeff(var,eq->vecteur);
        sgn_op = -value_sign(tmp);
        if (value_notzero_p(d)) {
            for (pv2=pv1;pv2 != NULL; pv2= pv2->succ) {
                if (sgn_op==-1)
                    value_oppose(pv2->val);
                value_modulus(pv2->val,d);
                if (value_neg_p(pv2->val))
                    value_addto(pv2->val,d);
            }
        }
        b0 = vect_coeff(TCST,pv1);
        value_absolute(b0);
 
        /* calcul de lambda = coefficient multiplicateur permettant
           d'obtenir la coupe optimale          */
 
        if (value_notzero_p(b0)) {
            in1 = value_div(d,b0);
            lambda = value_zero_p(value_mod(d,b0))? (in1-1) : in1;
            if (value_zero_p(lambda)) 
                lambda = VALUE_ONE;
        }
 
        /* optimisation de la coupe de Gomory   */
        if (value_gt(lambda,VALUE_ONE))
            for (pv2 = pv1;pv2!= NULL; pv2=pv2->succ)
            {
                value_product(pv2->val,lambda);
                value_modulus(pv2->val,d);
            }
 
        vect_chg_sgn(pv1);
 
        ps1->vecteur = vect_clean(ps1->vecteur);
    }
    return (ps1);
}

References typ_som::denominateur, eq, typ_som::eq_sat, MALLOC, printf(), SOMMET, typ_som::succ, Svecteur::succ, TCST, Svecteur::val, value_absolute, value_addto, value_div, value_gt, value_mod, value_modulus, value_neg_p, value_notzero_p, VALUE_ONE, value_oppose, value_product, value_sign, VALUE_ZERO, value_zero_p, vect_chg_coeff(), vect_chg_sgn(), vect_clean(), vect_coeff(), vect_dup(), vect_pgcd_all(), Scontrainte::vecteur, and typ_som::vecteur.

Referenced by plint_pas().

Here is the call graph for this function:

Here is the caller graph for this function: