plint.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 "ray_dte.h"
#include "polyedre.h"
#include "matrix.h"
#include "plint.h"

Include dependency graph for plint.c:

Go to the source code of this file.

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

Functions
Psommet	plint_pas (Psommet sys1, Psommet fonct, Pvecteur *lvbase, int *nb_som, int *nbvars, Pbase *b)
	Psommet plint_pas(Psommet sys1, Psommet fonct, Pvecteur * lvbase, int * nb_som, int * nbvars, Pbase *b): Algorithme des congruences decroissantes (Michel Minoux - Programmation mathematique - theorie et algorithmes- tome 2. More...
bool	plint_degen (Psommet *sys, Psommet fonct, int *nb_som, Pvecteur *lvbase, int *nbvars, Pbase *b)
	void plint_degen(Psommet *sys, Psommet fonct, int *nb_som, Pvecteur * lvbase, int nbvars, Pbase * b): Cas de degenerescence au cours de l'algorithme des congruences decroissantes More...
Psysteme	plint (Psysteme first_sys, Psommet fonct, Psolution *sol_fin)
	Psysteme plint(Psysteme first_sys, Psommet fonct, Psolution *sol_fin): resolution d'un systeme lineaire en nombres entiers positifs par l'algorithme general des congruences decroissantes (c.f. More...

Macro Definition Documentation

MALLOC

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

package plint

pour recuperer les declarations des fonctions de conversion de sc en liste de sommets et reciproquement, bien que ca casse le DAG des types de donnees

Definition at line 52 of file plint.c.

Function Documentation

plint()

Psysteme plint	(	Psysteme	first_sys,
		Psommet	fonct,
		Psolution *	sol_fin
	)

Psysteme plint(Psysteme first_sys, Psommet fonct, Psolution *sol_fin): resolution d'un systeme lineaire en nombres entiers positifs par l'algorithme general des congruences decroissantes (c.f.

Programmation Mathematique - tome 2. M.MINOUX (83))

resultat retourne par la fonction :

Psysteme : systeme lineaire donnant la solution de base du systeme ,si celui ci est realisable. Dans ce cas, son cout optimal vaut la valeur (avec le signe - ) de la constante de la fonction economique et la solution de base est exprimee sous la forme d'une Psolution.

NULL : si le systeme initial n'est pas realisable.

Les parametres de la fonction :

Psysteme first_syst : systeme lineaire initial Psommet fonct : fonction economique du programme lineaire

ajout des variables d'ecart

Definition at line 430 of file plint.c.

{
    Psommet sys1 = NULL;
    Psysteme sys2 = NULL;
    Psysteme syst_res = NULL;
    Pvecteur lvbase = NULL;
    int nb_som = 0;
    int nbvars;
    Pbase b = BASE_NULLE;
 
#ifdef TRACE
    Psolution sol = NULL;
 
    printf(" * algorithme des congruences decroissantes global \n");
    printf (" - GOMORY - le nb. de variables du systeme est %d \n",first_sys->dimension);
#endif
    if (first_sys) {
        nbvars = first_sys->dimension;
        b = base_dup(first_sys->base);
        
 
        if ((first_sys->egalites != NULL) || (first_sys->inegalites != NULL))
        {
 
            sys2 =sc_normalize(sc_dup(first_sys));
            if (sys2 != (Psysteme) NULL && syst_smith(sys2))
                sys1 = sys_som_conv(sys2,&nb_som);
 
#ifdef TRACE
            printf (" - GOMORY - le nb. de contraintes est %d \n",nb_som);
#endif
            /* ajout des variables d'ecart   */
            if ((sys1 = eq_in_ineq(&sys1,&nb_som,&lvbase)) != (Psommet) NULL) {
                sys1 = var_ecart_sup(sys1,nb_som,&lvbase,&nbvars,&b);
                sys1 = primal_pivot(sys1,&lvbase,nb_som,fonct);
            }
 
            sys1 = plint_pas(sys1,fonct,&lvbase,&nb_som,&nbvars,&b);
 
            if (sys1 && fonct) {
                *sol_fin = sol_finale(sys1,lvbase,nb_som);
 
#ifdef TRACE
                for (sol = *sol_fin; sol != NULL; sol = sol->succ)
                    printf (" %s == %f; ",noms_var(sol->var),(double)(sol->val / sol->denominateur));
                printf (" \n ");
                printf (" - GOMORY - la fonct. economique vaut %d\n ",vect_coeff(TCST,fonct->vecteur)/fonct->denominateur);
 
#endif
 
            }
            if (sys1 == NULL && fonct != NULL)  fonct->vecteur = NULL;
 
            if ((syst_res = som_sys_conv(sys1)) != NULL) {
                syst_res->base = b;
                syst_res->dimension = nbvars;
            }
        }
        sommets_rm(sys1);
        vect_rm(lvbase);
        sc_rm(sys2);
    }
    return(syst_res);
}

References Ssysteme::base, base_dup(), BASE_NULLE, Ssolution::denominateur, typ_som::denominateur, Ssysteme::dimension, eq_in_ineq(), noms_var(), plint_pas(), primal_pivot(), printf(), sc_dup(), sc_normalize(), sc_rm(), sol_finale(), sommets_rm(), Ssolution::succ, syst_smith(), TCST, Ssolution::val, Ssolution::var, var_ecart_sup(), vect_coeff(), vect_rm(), and typ_som::vecteur.

Referenced by find_eg(), and sys_int_fais().

Here is the call graph for this function:

Here is the caller graph for this function:

plint_degen()

bool plint_degen	(	Psommet *	sys,
		Psommet	fonct,
		int *	nb_som,
		Pvecteur *	lvbase,
		int *	nbvars,
		Pbase *	b
	)

void plint_degen(Psommet *sys, Psommet fonct, int *nb_som, Pvecteur * lvbase, int nbvars, Pbase * b): Cas de degenerescence au cours de l'algorithme des congruences decroissantes

resultat retourne par la fonction :

Le systeme initial est modifie. S'il est vide, c'est que le systeme est non faisable. Sinon on ajoute une contrainte supplementaire permettant la non degenerescence du programme lineaire.

Les parametres de la fonction :

Psommet sys : systeme lineaire Psommet fonct : fonction economique du programme lineaire Pvecteur lvbase: liste des variables de base du systeme int nb_som : nombre de contraintes du systeme int nbvars : nombre de variables du systeme Pbase b : liste des variables du systeme

construction de la liste des variables hors base de cout non nul

construction d'une nouvelle fonction economique pour le systeme dont on a elimine les variables h.base de cout non nul

recherche d'une solution entiere pour ce nouveau systeme

le systeme n'admet aucune solution entiere

ajout inegalite permettant la non-degenerescence du programme lineaire

on recherche la variable pivot et on effectue le pivot

Definition at line 288 of file plint.c.

{
    Psommet fonct2=NULL;
    Psommet eq_coupe=NULL;
    Psommet sys1 = sommets_dupc(*sys);
    Pvecteur eq_for_ndegen=NULL;
    Pvecteur lvhb_de_cnnul=NULL;
    Pvecteur pv=NULL;
    Pvecteur pv2=VECTEUR_NUL;
    Pvecteur explv=NULL;
    Variable var_entrant;
    register int i;
    int exnbv;
    int exnbs = *nb_som;
    bool result = true;
 
#ifdef TRACE
    printf(" ** Gomory - cas de degenerescence \n");
#endif
 
    /* construction de la liste des variables hors base de cout non nul*/
    lvhb_de_cnnul = vect_dup(fonct->vecteur);
 
    for (pv= *lvbase;pv!=NULL;pv=pv->succ)
    {
        vect_chg_coeff(&lvhb_de_cnnul,pv->var,0);
    }
 
    vect_chg_coeff(&lvhb_de_cnnul,TCST,0);
    oter_lvbase(sys1,lvhb_de_cnnul);
    exnbv = *nbvars;
    explv = vect_dup(*lvbase);
 
    /* construction d'une nouvelle fonction economique pour le systeme
       dont on a elimine les variables h.base de cout non nul */
 
    fonct2 = (Psommet)MALLOC(sizeof(Ssommet),SOMMET,"plint_degen");
    fonct2->denominateur = VALUE_ONE;
    fonct2->vecteur = vect_new(vecteur_var(*b),VALUE_ONE);
    for (i =1,pv2 = (*b)->succ ; i< *nbvars && !VECTEUR_NUL_P(pv2); 
         i++, pv2=pv2->succ)
        vect_add_elem(&(fonct2->vecteur),vecteur_var(pv2),VALUE_ONE);
 
    for (pv= lvhb_de_cnnul;pv!=NULL;pv=pv->succ)
   vect_chg_coeff(&(fonct2->vecteur),pv->var,VALUE_ZERO);
  
    vect_chg_coeff(&(fonct2->vecteur),TCST,VALUE_ZERO);
 
    fonct2->eq_sat = (int *)MALLOC(sizeof(int),INTEGER,"plint_degen");
    *(fonct2->eq_sat) = 0;
    fonct2->succ = NULL;
 
    /* recherche d'une solution entiere pour ce nouveau systeme */
    if (sys1 != NULL)
sys1 = plint_pas(sys1,fonct2,lvbase,nb_som,nbvars,b);
  if (sys1 != NULL)
 
    {
#ifdef TRACE
        printf (" -- Gomory degen. - le pb. a une sol. optimale \n ");
#endif
        result = false;
        vect_rm(explv);
    }
    else {
        /* le systeme n'admet aucune solution entiere  */
        *nbvars = exnbv;
        *nb_som = exnbs;
        vect_rm(*lvbase);
        *lvbase = explv;
        /*   ajout inegalite permettant la non-degenerescence du 
             programme lineaire   */
 
        eq_for_ndegen = vect_dup(lvhb_de_cnnul);
        for (pv = eq_for_ndegen; pv!= NULL; pv = pv->succ)
            vect_chg_coeff(&pv,pv->var,VALUE_MONE);
        vect_chg_coeff(&eq_for_ndegen,TCST,VALUE_ONE);
        eq_coupe = (Psommet) MALLOC(sizeof(Ssommet),SOMMET,"plint_degen");
        eq_coupe->vecteur = eq_for_ndegen;
        eq_coupe->eq_sat = (int *)MALLOC(sizeof(int),INTEGER,"plint_degen");
        *(eq_coupe->eq_sat) = -1;
        eq_coupe->denominateur = VALUE_ONE;
        eq_coupe->succ=NULL;
        sommet_add(sys,eq_coupe,nb_som);
 
        *sys = var_ecart_sup(*sys,*nb_som,lvbase,nbvars,b);
 
        /* on recherche la variable pivot et on effectue le pivot  */
        var_entrant = var_pivotd(eq_coupe,fonct);
 
        if (var_entrant != NULL)
        {
 
            pivoter (*sys,eq_coupe,var_entrant,fonct);
            lvbase_ote_no_ligne(1,lvbase);
            lvbase_add(var_entrant,1,lvbase);
        }
        else 
        {
#ifdef TRACE
            printf (" -- Gomory degen. - le pb. n'est pas borne \n");
#endif
            result = false;
            sommets_rm(*sys);
            *sys = NULL;
        }
    }
    vect_rm(lvhb_de_cnnul);
    sommets_rm(sys1);
    sommets_rm(fonct2);
 
    return(result);
}

References typ_som::denominateur, typ_som::eq_sat, lvbase_add(), lvbase_ote_no_ligne(), MALLOC, oter_lvbase(), pivoter(), plint_pas(), printf(), SOMMET, sommet_add(), sommets_dupc(), sommets_rm(), typ_som::succ, Svecteur::succ, TCST, VALUE_MONE, VALUE_ONE, VALUE_ZERO, Svecteur::var, var_ecart_sup(), var_pivotd(), vect_add_elem(), vect_chg_coeff(), vect_dup(), vect_new(), vect_rm(), typ_som::vecteur, VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.

Referenced by plint_pas().

Here is the call graph for this function:

Here is the caller graph for this function:

plint_pas()

Psommet plint_pas	(	Psommet	sys1,
		Psommet	fonct,
		Pvecteur *	lvbase,
		int *	nb_som,
		int *	nbvars,
		Pbase *	b
	)

Psommet plint_pas(Psommet sys1, Psommet fonct, Pvecteur * lvbase, int * nb_som, int * nbvars, Pbase *b): Algorithme des congruences decroissantes (Michel Minoux - Programmation mathematique - theorie et algorithmes- tome 2.

Dunod. p22. )

resultat retourne par la fonction :

Psommet : systeme lineaire modifie

Les parametres de la fonction :

Psommet sys1 : systeme lineaire Psommet fonct : fonction economique du programme lineaire Pvecteur lvbase: liste des variables de base du systeme int nb_som : nombre de contraintes du systeme int nbvars : nombre de variables du systeme Pbase *b : liste des variables du systeme

test de degenerescence

recherche d'une variable de base non entiere, puis ajout d'une coupe de Gomory

il n'y a plus de variable non entiere

on effectue un pas de l'algorithme dual du simplexe

ajout des variables d'ecart

la solution est entiere mais pas positive

on a une solution positive

cas de degenerescence

on a une sol. entiere et positive a la fin de

l'execution de l'algorithme dual du simplexe

on a une solution entiere et positive a la fin

de l'execution de l'algorithme primal du simplexe

Definition at line 73 of file plint.c.

{
 
    double d1;
    int no_som =0;
    Variable var2 = 0;
    Value in1;
    bool non_fin = true;
    bool non_stop = true;
    bool degenere = false;
 
#ifdef TRACE
 
    Psysteme sys =NULL;
    printf(" * algorithme de GOMORY  \n");
#endif
 
    sys1 = primal_pivot(sys1,lvbase,*nb_som,fonct);
 
    if (sys1!=NULL && fonct != NULL)
    {
        if ((sol_entiere(sys1,*lvbase,*nb_som) == false) || 
            (sol_positive(sys1,*lvbase,*nb_som) == false) || const_negative(sys1))
        {
 
 
            while ((sys1 != NULL) && 
                   (dual_pivot_pas(&sys1,lvbase,*nb_som,fonct,nbvars,b) == true));
            if (sys1 != NULL && fonct != NULL)
            {
                if ((sol_entiere(sys1,*lvbase,*nb_som)==false))
                {
                    Value f0 = VALUE_ZERO,fden;
 
                    while (non_fin)
                    {
                        f0 = value_uminus(vect_coeff(TCST,fonct->vecteur));
                        fden = fonct->denominateur;
                        d1 = VALUE_TO_DOUBLE(f0) / VALUE_TO_DOUBLE(fden);
                        in1 = value_div(f0,fden);
 
                        /* test de degenerescence */
                        if ((d1 != VALUE_TO_DOUBLE(in1)) || 
                            value_zero_p(in1) ||
                            (cout_nul(fonct,*lvbase,*nbvars,*b) ==
                             false) || degenere) {
                            degenere = false;
 
                            while (non_stop)
                            {
                                Psommet eq_gom = NULL;
                                Psommet eq_coup = NULL;
 
                                /* recherche d'une variable de base non entiere,
                                   puis ajout d'une coupe de Gomory  */
 
                                if (((eq_gom = gomory_eq(&sys1,*lvbase,*nb_som,&no_som,&var2)) != NULL) && (sys1 !=NULL)) {
                                    if ((eq_coup = gomory_trait_eq(eq_gom,var2)) != NULL)
                                        sommet_add(&sys1,eq_coup,nb_som);
                                    else {
                                        sommets_rm(sys1);
                                        sys1 = NULL;
                                        non_fin = false;
                                        non_stop = false;
                                    }
#ifdef TRACE
                                    sys = som_sys_conv(sys1);
                                    sc_fprint(stdout,sys,noms_var);
#endif
                                }
                                else {
                                    /* il n'y a plus de variable non entiere */
                                    non_stop = false ;
                                    non_fin = false;
                                }
                                if ((sys1 != NULL) && non_stop )
                                {
                                    /* on effectue un pas de l'algorithme dual du simplexe */
                                    /* ajout des variables d'ecart   */
                                    sys1 = var_ecart_sup (sys1,*nb_som,lvbase,nbvars,b);
                                    if (dual_pivot_pas(&sys1,lvbase,*nb_som,fonct,nbvars,b) != false) {
                                        if  (sol_entiere(sys1,*lvbase,*nb_som) == true) {
                                            /* la solution est entiere mais pas positive */
                                            if (ligne_pivot(sys1,*nb_som,&no_som) != NULL) {
                                                while ((sys1 != NULL)
                                                       && (dual_pivot_pas(&sys1,lvbase,*nb_som,fonct,nbvars,b) == true))
                                                    ;
 
                                                if ((sol_entiere(sys1,*lvbase,*nb_som) == true) && (sol_positive(sys1,*lvbase,*nb_som) == true))
                                                {
#ifdef TRACE
                                                    printf(" - Gomory - on a une solution optimale \n");
#endif
                                                    non_fin = false;
                                                    non_stop = false;
                                                }
                                                else {
                                                    if (sys1 == NULL) {
                                                        non_fin = false;
                                                        non_stop = false;
                                                    }
                                                }
                                            }
                                            else {
#ifdef TRACE                                    
                                                printf (" - Gomory - on a une solution optimale \n");
#endif
                                                non_fin = false;
                                                non_stop = false;
                                            }
                                        }
                                    }
                                    else {
                                        /* on a une solution positive */
                                        if (sys1 == NULL)
                                        {
                                            non_stop = false;
                                            non_fin = false;
                                        }
                                        else {
                                            if (sol_entiere(sys1,*lvbase,*nb_som) == true)
                                            {
#ifdef TRACE
                                                printf (" -  Gomory - on a une solution entiere \n");
#endif
                                                non_stop = false;
                                                non_fin = false;
                                            }
                                        }
                                    }
                                }
#ifdef TRACE
                                sys = som_sys_conv(sys1);
                                sc_fprint(stdout,sys,noms_var);
#endif
                            }
                        }
                        else
                        {
                            /* cas de degenerescence   */
                            degenere = true;
                            if (plint_degen(&sys1,fonct,nb_som,lvbase,nbvars,b) == false)
                            {
                                if (sys1!= NULL)
                                {
#ifdef TRACE
                                    printf (" - Gomory - on a une solution reelle \n");
                                    sys = som_sys_conv(sys1);
                                    sc_fprint(stdout,sys,noms_var);
#endif
                                }
                                non_fin = false;
                            }
                        }
                    }
                }
                else {
                    /* on a une sol. entiere et positive a la fin de */
                    /* l'execution de l'algorithme dual du simplexe  */
 
#ifdef TRACE
                    printf (" - Gomory - on a une solution  \n");
#endif
                }
            }
#ifdef TRACE
            else printf (" - Gomory - le systeme est non realisable - fin !!\n");
#endif
        }
        else {
            /* on a une solution entiere et positive a la fin */
            /* de l'execution de l'algorithme primal du simplexe */
#ifdef TRACE
            printf (" - Gomory - on a une solution optimale \n");
            sys = som_sys_conv(sys1);
            sc_fprint(stdout,sys,noms_var);
#endif
 
        }
    }
    else {
#ifdef TRACE
        printf (" -  Gomory - pas de sol. reelle ==> pas de sol. entiere \n");
#endif
    }
    return (sys1);
}

References const_negative(), cout_nul(), typ_som::denominateur, dual_pivot_pas(), false, gomory_eq(), gomory_trait_eq(), ligne_pivot(), noms_var(), plint_degen(), primal_pivot(), printf(), sc_fprint(), sol_entiere(), sol_positive(), sommet_add(), sommets_rm(), TCST, value_div, VALUE_TO_DOUBLE, value_uminus, VALUE_ZERO, value_zero_p, var_ecart_sup(), vect_coeff(), and typ_som::vecteur.

Referenced by plint(), and plint_degen().

Here is the call graph for this function:

Here is the caller graph for this function: