PIPS
|
#include <setjmp.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
#include "genC.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "sc.h"
#include "polyedre.h"
#include "matrix.h"
#include "ri.h"
#include "constants.h"
#include "ri-util.h"
#include "misc.h"
#include "bootstrap.h"
#include "complexity_ri.h"
#include "database.h"
#include "graph.h"
#include "dg.h"
#include "paf_ri.h"
#include "parser_private.h"
#include "property.h"
#include "reduction.h"
#include "text.h"
#include "paf-util.h"
#include "pip.h"
Go to the source code of this file.
Macros | |
#define | PIP_BIN "pip4" |
Name : pip.c Package : pip Author : F. More... | |
#define | PIP_OPTION "-s" |
#define | PIP_IN_FILE "pip_in" |
#define | PIP_OUT_FILE "pip_out" |
#define | INLENGTH 1024 |
Variables for the direct call to PIP version. More... | |
Functions | |
quast | pip_solve_min_with_big (Psysteme ps_dep, Psysteme ps_context, Pvecteur pv_unknowns, char *big) |
========================================================================== More... | |
Pvecteur | vect_add_first (Pvecteur pv1, Pvecteur pv2) |
====================================================================== More... | |
quast | pip_solve (Psysteme ps_dep, Psysteme ps_context, Pvecteur pv_unknowns, int int_or_rat, int min_or_max) |
========================================================================== More... | |
quast | pip_integer_min (Psysteme ps_dep, Psysteme ps_context, Pvecteur pv_unknowns) |
================================================================== More... | |
quast | pip_integer_max (Psysteme ps_dep, Psysteme ps_context, Pvecteur pv_unknowns) |
================================================================== More... | |
quast | pip_rational_min (Psysteme ps_dep, Psysteme ps_context, Pvecteur pv_unknowns) |
================================================================== More... | |
quast | pip_rational_max (Psysteme ps_dep, Psysteme ps_context, Pvecteur pv_unknowns) |
================================================================== More... | |
static int | compare_variables_in_base (Pvecteur *pv1, Pvecteur *pv2) |
function for qsort. More... | |
void | sort_psysteme (Psysteme ps, Pvecteur pv) |
================================================================== More... | |
Variables | |
long int | cross_product |
long int | limit |
int | allocation |
External variables for direct call to PIP. More... | |
int | comptage |
char | inbuff [INLENGTH] |
int | inptr = 256 |
int | proviso = 0 |
int | verbose = 0 |
FILE * | dump = NULL |
Should not be used : put here for Pip copatibility. More... | |
char | dump_name [] = "XXXXXX" |
quast | quast_act |
Global variables More... | |
Pbase | base_var_ref |
Tag for MIN or MAX resolution. More... | |
Pbase | base_ref |
Base of the unknowns. More... | |
Pbase | old_base |
Base of the parameters. More... | |
Pbase | old_base_var |
Base of the unknowns. More... | |
int | ind_min_max |
static Pbase | base_for_sort = (Pbase)NULL |
================================================================== More... | |
#define INLENGTH 1024 |
#define PIP_BIN "pip4" |
Name : pip.c Package : pip Author : F.
Dumontet, A. Platonoff and A. Leservot Date : 30 july 1993 Historic :
Documents: Comments : file containing the functions that resolve a Parametric Integer Programming problem with the PIP solver. Ansi includes
Newgen includes
C3 includes
Pips includes
Macros and functions Used by the old_pip_solve version
function for qsort.
rank_of_variable returns 0 for TCST, hence the strange return
TCST must be last, but given as 0
Definition at line 700 of file pip.c.
References base_for_sort, message_assert, rank_of_variable(), and var_of.
Referenced by sort_psysteme().
==================================================================
Definition at line 637 of file pip.c.
References pip_solve(), PIP_SOLVE_INTEGER, and PIP_SOLVE_MAX.
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
==================================================================
Definition at line 628 of file pip.c.
References pip_solve(), PIP_SOLVE_INTEGER, and PIP_SOLVE_MIN.
Referenced by valuer().
==================================================================
Definition at line 655 of file pip.c.
References pip_solve(), PIP_SOLVE_MAX, and PIP_SOLVE_RATIONAL.
==================================================================
Definition at line 646 of file pip.c.
References pip_solve(), PIP_SOLVE_MIN, and PIP_SOLVE_RATIONAL.
quast pip_solve | ( | Psysteme | ps_dep, |
Psysteme | ps_context, | ||
Pvecteur | pv_unknowns, | ||
int | int_or_rat, | ||
int | min_or_max | ||
) |
==========================================================================
quast pip_solve(Psysteme ps_dep, ps_context, Pvecteur pv_unknowns, int int_or_rat, int min_or_max): Pip resolution. AL 6/12/93
Parameters: ps_dep: system of constraints on the unknowns (and parameters) ps_context: system of constraints on the parameters pv_unknowns: ordered vector of unknowns in "ps_dep" int_or_rat: integer (1) or rational (0) resolution. min_or_max: tag for min or max resolution
Result: a quast giving the value of the unknowns
Call to PIP is direct : no input or output file are produced.
FD variables
Pip variables
Initialization
trace file
Normalize base of system ps_dep
We set the env for the kind of resolution desired (Min or Max)
Computation of the basis (unknowns and parameters) base of ps_dep is the reference for all unknowns and parameters.
Total base of ps_dep
Set PIP variables. Comes from ecrit_probleme2
Prepare to call PIP
Verification de la non vacuite du contexte
We read solution and put it in global quast_act
Definition at line 503 of file pip.c.
References base, base_dup(), base_normalize(), base_ref, base_union(), base_var_ref, converti_psysmin_psysmax(), cross_product, debug(), debug_off, debug_on, expanser(), fprint_psysteme(), fprintf(), get_debug_level(), imprime_quast(), ind_min_max, init_new_base(), integer_sol_edit(), is_not_Nil(), limit, old_base, old_base_var, PIP_SOLVE_INTEGER, PIP_SOLVE_MIN, quast_act, quast_undefined, rational_sol_edit(), sc_to_tableau(), sol_hwm(), sol_init(), sol_reset(), tab_hwm(), tab_init(), tab_reset(), TCST, traiter(), True, UN, user_warning, vect_add_first(), vect_erase_var(), vect_size(), and vect_substract().
Referenced by pip_integer_max(), pip_integer_min(), pip_rational_max(), and pip_rational_min().
quast pip_solve_min_with_big | ( | Psysteme | ps_dep, |
Psysteme | ps_context, | ||
Pvecteur | pv_unknowns, | ||
char * | big | ||
) |
==========================================================================
quast old_pip_solve(Psysteme ps_dep, ps_context, int nb_unknowns, int min_or_max): Pip resolution.
Parameters: ps_dep: system of constraints on the unknowns (and parameters) ps_context: system of constraints on the parameters nb_unknowns: number of unknowns in "ps_dep" min_or_max: tag for min or max resolution
Result: a quast giving the value of the unknowns
Note: The basis of "ps_dep" must contain all the unknowns and the parameters, with first the unknowns in order to allow us to catch them using "nb_unknowns". Obsolete, AP July 31st 95 :
quast old_pip_solve(ps_dep, ps_context, nb_unknowns, min_or_max) Psysteme ps_dep, ps_context; int nb_unknowns; int min_or_max; { Pvecteur pvect; int aux, n, i, res, infinite_num; char *com = "essai";
if(min_or_max == PIP_SOLVE_MIN) { ind_min_max = 0; infinite_num = -1; } else { ps_dep = converti_psysmin_psysmax(ps_dep, nb_unknowns); ind_min_max = 1; infinite_num = vect_size((ps_dep)->base); }
base_var_ref = base_dup((ps_dep)->base); old_base_var = base_dup(base_var_ref); for(i = 1, pvect = base_var_ref; i<nb_unknowns; i++) { pvect = pvect->succ; } base_ref = pvect->succ; pvect->succ = NULL; old_base = base_dup(base_ref);
if(! SC_EMPTY_P(ps_context)) ps_context->base = base_dup(base_ref);
res = ecrit_probleme2(com, ps_dep, ps_context, nb_unknowns, infinite_num, vect_size(base_ref));
n = 1; while(n & 0xff) { int m; m = fork(); while(m == -1) { char answer;
fprintf(stderr, "Fork failed for PIP\n\t Do you want to retry (y/n) ?\n"); scanf("%c\n", &answer); if(answer == 'y') m = fork(); else exit(1); fprintf(stderr, "\n"); } if(m == 0) { execlp(PIP_BIN, PIP_BIN, PIP_OPTION, PIP_IN_FILE, PIP_OUT_FILE, (char *) 0); }
wait(&n); }
if((quayyin = fopen(PIP_OUT_FILE,"r")) == NULL) { fprintf(stderr, "Cannot open file %s\n", PIP_OUT_FILE); exit(1); } aux = quayyparse();
return(quast_act); } ========================================================================== quast old2_pip_solve(Psysteme ps_dep, ps_context, int nb_unknowns, int min_or_max): Pip resolution. AL 6/12/93
Parameters: ps_dep: system of constraints on the unknowns (and parameters) ps_context: system of constraints on the parameters nb_unknowns: number of unknowns in "ps_dep" int_or_rat: integer or rational resolution. min_or_max: tag for min or max resolution
Result: a quast giving the value of the unknowns
Note: The basis of "ps_dep" must contain all the unknowns and the parameters, with first the unknowns in order to allow us to catch them using "nb_unknowns".
Call to PIP is direct : no input or output file are produced. Obsolete, AP July 31st 95 :
quast old2_pip_solve(ps_dep, ps_context, nb_unknowns, min_or_max) Psysteme ps_dep, ps_context; int nb_unknowns, min_or_max; { Pvecteur pvect; int i, infinite_num;
int q, bigparm, ni, nvar, nq, non_vide, nparm, nc, p, xq; char* g; Tableau *ineq, *context, *ctxt;
debug_on("PIP_DEBUG_LEVEL"); debug(5, "pip_solve", "begin\n"); if (get_debug_level()>4) { debug(5, "pip_solve", "Input Psysteme:\n"); fprint_psysteme( stderr, ps_dep ); debug(5, "pip_solve", "Input Context:\n"); fprint_psysteme( stderr, ps_context ); fprintf(stderr, "Number of variables : %d\n", nb_unknowns); } vect_erase_var(&(ps_dep->base), (Variable) TCST); ps_dep->dimension = vect_size((ps_dep)->base); if(min_or_max == PIP_SOLVE_MIN) { ind_min_max = 0; infinite_num = -1; } else { ps_dep = converti_psysmin_psysmax(ps_dep, nb_unknowns); vect_erase_var(&(ps_dep->base), (Variable) TCST); ps_dep->dimension = vect_size((ps_dep)->base); ind_min_max = 1; infinite_num = vect_size((ps_dep)->base); } base_var_ref = base_dup((ps_dep)->base); old_base_var = base_dup(base_var_ref); for(i = 1, pvect = base_var_ref; i<nb_unknowns; i++) { pvect = pvect->succ; } base_ref = pvect->succ; pvect->succ = NULL; old_base = base_dup(base_ref); if(! SC_EMPTY_P(ps_context) ) { ps_context->base = base_dup(base_ref); ps_context->dimension = vect_size( base_ref ); } nvar = nb_unknowns; nparm = ps_dep->dimension - nb_unknowns; ni = (ps_dep->nb_eq * 2) + ps_dep->nb_ineq;; nc = ((ps_context == NULL)? 0 : (ps_context->nb_eq * 2) + ps_context->nb_ineq ); bigparm = infinite_num; nq = 1; debug(5, "pip_solve", "%d %d %d %d %d %d\n", nvar, nparm, ni, nc, bigparm, nq ); limit = 0L; sol_init(); tab_init(); cross_product = 0; g = tab_hwm(); ineq = sc_to_tableau(ps_dep, nb_unknowns); if (ps_context != NULL) { context = sc_to_tableau(ps_context, 0); } else context = NULL; xq = p = sol_hwm(); if (nc) { ctxt = expanser(context, nparm, nc, nparm+1, nparm, 0, 0); traiter( ctxt, NULL, True, UN, nparm, 0, nc, 0, -1 ); non_vide = is_not_Nil(p); sol_reset(p); } else non_vide = True; if ( non_vide ) { traiter( ineq, context, nq, UN, nvar, nparm, ni, nc, bigparm ); q = sol_hwm(); init_new_base(); while((xq = new_sol_edit(xq)) != q); sol_reset(p); } else quast_act = quast_undefined; tab_reset(g); if (get_debug_level()>5) { imprime_quast( stderr, quast_act ); } debug_off(); return(quast_act);
} ====================================================================== quast pip_solve_min_with_big(Psysteme ps_dep, ps_context, int nb_unknowns, char *big): Pip resolution.
Parameters: ps_dep: system of constraints on the unknowns (and parameters) ps_context: system of constraints on the parameters nb_unknowns: number of unknowns in "ps_dep" big: big parameter 's name.
Result: a quast giving the value of the unknowns
Note: The basis of "ps_dep" must contain all the unknowns and the parameters, with first the unknowns in order to allow us to catch them using "nb_unknowns".
Call to PIP is direct : no input or output file are produced.
Note: this function is the same as pip_solve_min() but it has a big parameter given by the use.
FD variables
Pip variables
AC variables for the big parameter
trace file
We set the env for the kind of resolution desired (i.e. Min)
and we get the order of the bi parameter called "big" in the
base of ps_dep
Normalize base of system ps_dep
Computation of the basis (unknowns and parameters) base of ps_dep is the reference for all unknowns and parameters.
Total base of ps_dep
Set PIP variables. Comes from ecrit_probleme2
Prepare to call PIP
Verification de la non vacuite du contexte
We read solution and put it in global quast_act
Definition at line 331 of file pip.c.
References base_dup(), base_normalize(), base_ref, base_to_list(), base_union(), base_var_ref, CAR, CDR, cross_product, debug(), debug_off, debug_on, ENTITY, entity_local_name(), expanser(), fprint_psysteme(), fprintf(), get_debug_level(), imprime_quast(), ind_min_max, init_new_base(), is_not_Nil(), limit, NIL, old_base, old_base_var, PIP_SOLVE_RATIONAL, quast_act, quast_undefined, rational_sol_edit(), sc_to_tableau(), sol_hwm(), sol_init(), sol_reset(), tab_hwm(), tab_init(), tab_reset(), TCST, traiter(), True, UN, vect_add_first(), vect_erase_var(), vect_size(), and vect_substract().
Referenced by analyze_quast(), and search_scc_bdt().
==================================================================
void sort_psysteme(Psysteme ps, Pvecteur pv): sorts the system "ps" according to the vector "pv". In order to avoid any side effects, this vector is duplicated into a base "new_base". When the sorting is done, this new base becomes the basis of this system.
"pv" MUST contain all the variables that appear in "ps". "pv" DOES NOT HAVE TO contain TCST.
modified by FC, 29/12/94. I removed the vect_tri call and the associated memory leaks. sc_vect_sort called instead. maybe the sc base is lost? It depends whether it is pv or not, and what is done with pv by the caller. I would suggest a base_rm.
Definition at line 729 of file pip.c.
References base_dimension, base_dup(), base_for_sort, compare_variables_in_base(), and sc_vect_sort().
Referenced by adg_build_Psysteme(), and adg_dataflowgraph().
======================================================================
Pvecteur vect_add_first( pv1, pv2 ) AL 16 02 94
Suppress all variables of pv1 in pv2 and add pv1 before pv2. Keep pv1 order, not pv2's order!
Definition at line 470 of file pip.c.
References Svecteur::succ, Svecteur::var, vect_dup(), vect_erase_var(), and vect_reversal().
Referenced by pip_solve(), and pip_solve_min_with_big().
int allocation |
External variables for direct call to PIP.
Definition at line 92 of file pip.c.
Referenced by dag_vertex_pred_imagelets(), freia_terapix_call(), tab_alloc(), tab_init(), and tab_reset().
==================================================================
void pip_solve_min(Psysteme ps_dep, ps_context, int nb_unknowns): Pip resolution for the minimum. Obsolete, AP July 31st 95 :
quast pip_solve_min(ps_dep, ps_context, nb_unknowns) Psysteme ps_dep, ps_context; int nb_unknowns; { return(old2_pip_solve(ps_dep, ps_context, nb_unknowns, PIP_SOLVE_MIN)); } ================================================================== void pip_solve_max(Psysteme ps_dep, ps_context, int nb_unknowns): Pip resolution for the maximum. Obsolete, AP July 31st 95 :
quast pip_solve_max(ps_dep, ps_context, nb_unknowns) Psysteme ps_dep, ps_context; int nb_unknowns; { return(old2_pip_solve(ps_dep, ps_context, nb_unknowns, PIP_SOLVE_MAX)); } ================================================================== Useful for the sorting of the variables in the system's Pvecteur.
Definition at line 695 of file pip.c.
Referenced by compare_variables_in_base(), and sort_psysteme().
Pbase base_ref |
Base of the unknowns.
Definition at line 102 of file pip.c.
Referenced by init_new_base(), init_vecteur(), pip_solve(), and pip_solve_min_with_big().
Pbase base_var_ref |
Tag for MIN or MAX resolution.
Definition at line 102 of file pip.c.
Referenced by init_liste_vecteur(), pip_solve(), and pip_solve_min_with_big().
long int cross_product |
Definition at line 91 of file pip.c.
Referenced by choisir_piv(), integrer(), pip_solve(), pip_solve_min_with_big(), pivoter(), tab_display(), and traiter().
FILE* dump = NULL |
int ind_min_max |
Definition at line 103 of file pip.c.
Referenced by ecrit_coeff1(), ecrit_coeff2(), ecrit_coeff_neg2(), ecrit_une_var(), ecrit_une_var_neg(), pip_solve(), and pip_solve_min_with_big().
long int limit |
Definition at line 91 of file pip.c.
Referenced by pip_solve(), and pip_solve_min_with_big().
Pbase old_base |
Base of the parameters.
Definition at line 102 of file pip.c.
Referenced by creer_Psysteme(), pip_solve(), and pip_solve_min_with_big().
Pbase old_base_var |
Base of the unknowns.
Definition at line 102 of file pip.c.
Referenced by pip_solve(), and pip_solve_min_with_big().
quast quast_act |
Global variables
Definition at line 101 of file pip.c.
Referenced by creer_true_quast(), ecrit_resultat(), fait_quast(), pip_solve(), and pip_solve_min_with_big().
int verbose = 0 |
Definition at line 96 of file pip.c.
Referenced by sol_edit(), and sol_nil().