Thread View: comp.sources.reviewed
1 messages
1 total messages
Started by Michel Berkelaar
Wed, 05 Aug 1992 22:49
v02i022: lp_solve - linear problem solver, Part01/02
Author: Michel Berkelaar
Date: Wed, 05 Aug 1992 22:49
Date: Wed, 05 Aug 1992 22:49
2088 lines
61678 bytes
61678 bytes
Submitted-by: Michel Berkelaar <michel@es.ele.tue.nl>
Posting-number: Volume 2, Issue 22
Archive-name: lp_solve/part01
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 1 (of 2)."
# Contents: lp_solve lp_solve/CHANGELOG lp_solve/INSTALL
# lp_solve/MANIFEST lp_solve/Makefile lp_solve/README
# lp_solve/defines.h lp_solve/dual.c lp_solve/ex1.lp
# lp_solve/ex1.out lp_solve/ex2.lp lp_solve/ex2.out lp_solve/ex3.lp
# lp_solve/ex3.out lp_solve/ex4.lp lp_solve/ex4.out lp_solve/ex5.out
# lp_solve/globals.h lp_solve/lex.l lp_solve/lp.y
# lp_solve/lp_solve.1 lp_solve/lp_solve.man lp_solve/main.c
# lp_solve/patchlevel.h lp_solve/proto.h lp_solve/tran.c
# lp_solve/write.c
# Wrapped by michel@varda.es.ele.tue.nl on Fri Jun 19 09:05:16 1992
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test ! -d lp_solve ; then
echo shar: Creating directory \"lp_solve\"
mkdir lp_solve
fi
if test -f lp_solve/CHANGELOG -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/CHANGELOG\"
else
echo shar: Extracting \"lp_solve/CHANGELOG\" \(371 characters\)
sed "s/^X//" >lp_solve/CHANGELOG <<'END_OF_lp_solve/CHANGELOG'
XChanged after first review for comp.sources.reviewed:
X
X- Bug with row singletons and assignment fixed.
X- Makefile fixed.
X- Formatted man page (lp_solve.man) added + target to generate it in the
X Makefile
X- install signal handler after reading the input to avoid dumping core
X- changed names of some examples to make them uniform
X- added correct results for all examples
END_OF_lp_solve/CHANGELOG
if test 371 -ne `wc -c <lp_solve/CHANGELOG`; then
echo shar: \"lp_solve/CHANGELOG\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/INSTALL -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/INSTALL\"
else
echo shar: Extracting \"lp_solve/INSTALL\" \(395 characters\)
sed "s/^X//" >lp_solve/INSTALL <<'END_OF_lp_solve/INSTALL'
XThis package should install easily on any computer with ANSI C support and
XPOSIX compatible include files. You need lex and yacc as well. Flex and bison
Xcan help you out, but no support is included.
X
XJust have a look in the Makefile and change:
X
XCFLAGS
XLIBS
XINSTALLDIR
XMANDIR
X
Xwhen you don't like the defaults.
X
Xtype make and try some of the examples.
X
XReport problems to:
X
Xmichel@es.ele.tue.nl
END_OF_lp_solve/INSTALL
if test 395 -ne `wc -c <lp_solve/INSTALL`; then
echo shar: \"lp_solve/INSTALL\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/MANIFEST -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/MANIFEST\"
else
echo shar: Extracting \"lp_solve/MANIFEST\" \(1843 characters\)
sed "s/^X//" >lp_solve/MANIFEST <<'END_OF_lp_solve/MANIFEST'
Xtotal 164
X-rw-r--r-- 1 michel none 371 Jun 17 09:01 CHANGELOG
X-rw-r--r-- 1 michel none 395 Apr 10 14:24 INSTALL
X-rw-r--r-- 1 michel none 1843 Jun 17 09:02 MANIFEST
X-rw-r--r-- 1 michel none 1373 Jun 12 13:50 Makefile
X-rw-r--r-- 1 michel none 1618 Jun 12 14:01 README
X-rw-r--r-- 1 michel none 1761 Jun 12 13:39 defines.h
X-rw-r--r-- 1 michel none 2805 Jul 4 1991 dual.c
X-rw-r--r-- 1 michel none 56 Jun 12 13:59 ex1.lp
X-rw-r--r-- 1 michel none 100 Jun 12 14:02 ex1.out
X-rw-r--r-- 1 michel none 50 Jun 27 1991 ex2.lp
X-rw-r--r-- 1 michel none 100 Jun 12 14:02 ex2.out
X-rw-r--r-- 1 michel none 47 Jun 27 1991 ex3.lp
X-rw-r--r-- 1 michel none 100 Jun 12 14:02 ex3.out
X-rw-r--r-- 1 michel none 4816 Jul 3 1991 ex4.lp
X-rw-r--r-- 1 michel none 1531 Jun 12 14:02 ex4.out
X-rw-r--r-- 1 michel none 8873 Jun 12 13:26 ex5.lp
X-rw-r--r-- 1 michel none 3833 Jun 12 14:02 ex5.out
X-rw-r--r-- 1 michel none 1284 Jul 5 1991 globals.h
X-rw-r--r-- 1 michel none 1477 Jul 3 1991 lex.l
X-rw-r--r-- 1 michel none 2744 Jun 12 13:08 lp.y
X-rw-r--r-- 1 michel none 3747 Jun 17 08:57 lp_solve.1
X-rw-r--r-- 1 michel none 4622 Jun 17 08:58 lp_solve.man
X-rw-r--r-- 1 michel none 4961 Jun 12 13:47 main.c
X-rw-r--r-- 1 michel none 25 Jun 12 13:29 patchlevel.h
X-rw-r--r-- 1 michel none 2241 Jun 12 14:55 proto.h
X-rw-r--r-- 1 michel none 13928 Jun 12 13:22 read.c
X-rw-r--r-- 1 michel none 18876 Jun 12 13:48 solve.c
X-rw-r--r-- 1 michel none 1231 Jul 4 1991 tran.c
X-rw-r--r-- 1 michel none 1465 Jul 4 1991 write.c
END_OF_lp_solve/MANIFEST
if test 1843 -ne `wc -c <lp_solve/MANIFEST`; then
echo shar: \"lp_solve/MANIFEST\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/Makefile -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/Makefile\"
else
echo shar: Extracting \"lp_solve/Makefile\" \(1373 characters\)
sed "s/^X//" >lp_solve/Makefile <<'END_OF_lp_solve/Makefile'
XMYSOURCES= main.c solve.c read.c write.c tran.c dual.c
XYSOURCE= y.tab.c
XYOBJECT= ${YSOURCE:.c=.o}
XLSOURCE= lex.yy.c
XOBJECTS= ${MYSOURCES:.c=.o} ${YOBJECT}
XINCLUDES= globals.h defines.h proto.h
XTARGET= lp_solve
XMANPAGE= ${TARGET}.1
X
X# -ll and -lm seems to be enough on most machines.
XLIBS= -ll -lm
X
X# change this when you like. They are only used with make install.
XINSTALLDIR=/usr/local/bin
XMANDIR=/usr/local/man/man1
X
X# for performance reasons be sure to add all possible floating point support
X# This is ANSI C code following POSIX standards, be sure to tell your compiler
X# when necessary.
X# default
X#CFLAGS= -O
X#Apollo 68040 based: 425[est], DN5500
XCFLAGS= -O -Acpu,mathlib
X#Apollo 680[23]0 based: DN[234]XXX
X#CFLAGS= -O -Acpu,mathchip
X# debugging
X#CFLAGS= -g
X
X# choose a C compiler. On Sun, you probably want to use gcc
XCC= cc
X
X${TARGET} : ${OBJECTS}
X ${CC} -o ${TARGET} ${CFLAGS} ${OBJECTS} ${LIBS}
X
X${OBJECTS} : ${INCLUDES}
X
Xmain.o : patchlevel.h
X
X
X${LSOURCE} : lex.l
X lex lex.l
X
X${YSOURCE} : lp.y
X yacc lp.y
X
X${YOBJECT} : ${LSOURCE}
X
Xinstall:
X cp ${TARGET} ${INSTALLDIR}
X cp ${MANPAGE} ${MANDIR}
X
Xclean:
X /bin/rm -f ${OBJECTS} ${TARGET} TAGS ${LSOURCE} ${YSOURCE}
X
X# the following definitions can be practical if you have the tools
X
XTAGS:
X etags *.[chly]
X
Xproto.h:
X mkproto ${MYSOURCES} > proto.h
X
X${TARGET}.man: ${MANPAGE}
X nroff -man ${MANPAGE} > ${TARGET}.man
END_OF_lp_solve/Makefile
if test 1373 -ne `wc -c <lp_solve/Makefile`; then
echo shar: \"lp_solve/Makefile\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/README -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/README\"
else
echo shar: Extracting \"lp_solve/README\" \(1618 characters\)
sed "s/^X//" >lp_solve/README <<'END_OF_lp_solve/README'
XCONTENTS:
X
XThis package contains the ANSI C sources for a very efficient (mixed integer)
Xlinear problem solver. To compile without warnings, you need ANSI include
Xfiles as well. Its base is a sparse matrix dual simplex LP solver. MILP
Xproblems are solved with a branch-and-bound iteration over LP solutions.
X
XIt uses a lex and yacc parser to read a human-friendly algebraic input format.
X
XThe author has used the program to solve LP problems up to about 30000
Xvariables and 50000 constraints (on a 22 MFLOPS HP9000/750).
X
X
XVECTOR PROCESSORS:
X
XFor alliant users, there are pragmas in dual.c which allow to compile it in
Xvector mode. This reduces the cpu usage with 40% on a FX/8. Do not compile any
Xof the other files with vector optimization; this will just slow things down.
XIt should easily be possible to use vector capabilities of other computers.
X
X
XKNOWN BUGS / PROBLEMS
X
XThe program does not store simple bounds on variables in the main matrix.
XTherefore, simple problems like:
X
Xx + y;
Xx < 1;
Xy < 1;
X
Xdefine an empty matrix. This sometimes causes the program to crash. All
Xreal-life problems do not have this property, fortunately.
X
XFUTURE ENHANCEMENTS:
X
XThe program lacks two things:
X
X- matrix optimization as preprocessing
X- matrix normalization to increase numerical stability
X
XContributions are welcome.
X
X
XAUTHOR:
X
XFor any comment on the sources, contact: michel@es.ele.tue.nl
X
X
X
XINSTALL:
X
XLook into file INSTALL for installation hints.
X
X
XTESTING:
X
XAfter a succesful build, run:
X
Xlp_solve < ex[12345].lp
X
XThe results should be close to (floating point accuracy is important) the
Xresults in ex[12345].out.
X
END_OF_lp_solve/README
if test 1618 -ne `wc -c <lp_solve/README`; then
echo shar: \"lp_solve/README\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/defines.h -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/defines.h\"
else
echo shar: Extracting \"lp_solve/defines.h\" \(1761 characters\)
sed "s/^X//" >lp_solve/defines.h <<'END_OF_lp_solve/defines.h'
X#include <stdio.h>
X#include <math.h>
X#include <stdlib.h>
X#include <string.h>
X
X#define HASH_SIZE 10000
X#define ETA_START_SIZE 10000 /* start size of array Eta. Realloced if needed */
X#define FNAMLEN 64
X#define NAMELEN 25
X#define MAXSTRL (NAMELEN-1)
X#define STD_ROW_NAME_PREFIX "r_"
X
X#define FALSE 0
X#define TRUE 1
X
X#define LE 0
X#define EQ 1
X#define GE 2
X#define OF 3
X
X#define abs(x) ((x) < 0 ? -(x) : (x))
X
X#define CALLOC(ptr, nr, type) if(!(ptr = calloc((size_t)(nr),\
X sizeof(type)))) { fprintf(stderr, "calloc failed\n"); exit(1); }
X
X#define MALLOC(ptr, nr, type) if(!(ptr = malloc((size_t)((nr) * \
X sizeof(type))))) { fprintf(stderr, "malloc failed\n"); exit(1); }
X
X#define FREE(ptr) free(ptr);ptr=NULL;
X
X#define INFINITE 1.0e12
X#define EPSB 0.0001
X#define EPSEL 1.0e-8
X#define EPSD 0.0001
X#define EPSILON 0.01 /* to determine if float is an int */
X
Xtypedef char nstring[NAMELEN];
X
Xtypedef struct _column
X{
X int row;
X float value;
X struct _column *next ;
X} column;
X
Xtypedef struct _bound
X{
X double upbo;
X double lowbo;
X} bound;
X
Xtypedef struct _hashelem
X{
X nstring colname;
X struct _hashelem *next;
X struct _column *col;
X struct _bound *bnd;
X int must_be_int;
X} hashelem;
X
Xtypedef struct _rside /* contains relational operator and rhs value */
X{
X double value;
X struct _rside *next;
X short relat;
X} rside;
X
X/* structure or final data-storage */
X
Xtypedef struct _matrec
X{
X int rownr;
X double value;
X} matrec;
X
Xtypedef struct _tmp_store_struct
X{
X nstring name;
X int row;
X double value;
X double rhs_value;
X short relat;
X} tmp_store_struct;
X
Xtypedef struct _intrec
X{
X int varnr;
X struct _intrec *next;
X}
Xintrec;
END_OF_lp_solve/defines.h
if test 1761 -ne `wc -c <lp_solve/defines.h`; then
echo shar: \"lp_solve/defines.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/dual.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/dual.c\"
else
echo shar: Extracting \"lp_solve/dual.c\" \(2805 characters\)
sed "s/^X//" >lp_solve/dual.c <<'END_OF_lp_solve/dual.c'
X#include "defines.h"
X#include "globals.h"
X
X#ifdef alliant
X#pragma global safe (Eta_rownr, Eta_value)
X#pragma global assoc
X#endif
X
Xvoid rowdual(int *rownr)
X{
X int i;
X double f, g, minrhs;
X short artifs;
X
X#ifdef alliant
X#pragma safe (Rhs, Upbo, Bas)
X#endif
X
X if (Verbose)
X printf("rowdual\n");
X (*rownr) = 0;
X minrhs = -EPSB;
X i = 0;
X artifs = FALSE;
X while (i < Rows && !artifs)
X {
X i++;
X f = Upbo[Bas[i]];
X if (f == 0 && Rhs[i] != 0)
X {
X artifs = TRUE;
X (*rownr) = i;
X }
X else
X {
X if (Rhs[i] < f - Rhs[i])
X g = Rhs[i];
X else
X g = f - Rhs[i];
X if (g < minrhs)
X {
X minrhs = g;
X (*rownr) = i;
X }
X }
X }
X} /* rowdual */
X
X
Xshort coldual(int *numeta,
X int *rownr,
X int *colnr,
X short *minit,
X double *prow,
X double *drow)
X{
X int i, j, r, varnr;
X double theta, quot, pivot, d, f, g;
X
X#ifdef alliant
X#pragma safe (Rhs, Upbo, Bas, Cend, Endetacol, prow, drow, Basis, Lower)
X#endif
X
X if (Verbose)
X printf("coldual\n");
X if (!(*minit))
X {
X for (i = 0; i <= Rows; i++)
X {
X prow[i] = 0;
X drow[i] = 0;
X }
X drow[0] = 1;
X prow[(*rownr)] = 1;
X for (i = (*numeta); i >= 1; i--)
X {
X d = 0;
X f = 0;
X r = Eta_rownr[Endetacol[i] - 1];
X for (j = Endetacol[i - 1]; j < Endetacol[i]; j++)
X {
X /* this is where the program consumes most cpu time */
X f = f + prow[Eta_rownr[j]] * Eta_value[j];
X d = d + drow[Eta_rownr[j]] * Eta_value[j];
X }
X if (abs(f) < EPSEL)
X prow[r] = 0;
X else
X prow[r] = f;
X if (abs(d) < EPSEL)
X drow[r] = 0;
X else
X drow[r] = d;
X }
X for (i = 1; i <= Columns; i++)
X {
X varnr = Rows + i;
X if (!Basis[varnr])
X {
X d = -Extrad * drow[0];
X f = 0;
X for (j = Cend[i - 1]; j < Cend[i]; j++)
X {
X d += drow[Mat[j].rownr] * Mat[j].value;
X f += prow[Mat[j].rownr] * Mat[j].value;
X }
X drow[varnr] = d;
X prow[varnr] = f;
X }
X }
X
X#ifdef alliant
X#pragma loop novector
X#endif
X
X for (i = 0; i <= Sum; i++)
X {
X if (abs(prow[i]) < EPSEL)
X prow[i] = 0;
X if (abs(drow[i]) < EPSD)
X drow[i] = 0;
X }
X }
X if (Rhs[(*rownr)] > Upbo[Bas[(*rownr)]])
X g = -1;
X else
X g = 1;
X pivot = 0;
X (*colnr) = 0;
X theta = INFINITE;
X for (i = 1; i <= Sum; i++)
X {
X if (Lower[i])
X d = prow[i] * g;
X else
X d = -prow[i] * g;
X if (d < 0)
X if (!Basis[i])
X if (Upbo[i] > 0)
X {
X if (Lower[i])
X quot = -drow[i] / (double) d;
X else
X quot = drow[i] / (double) d;
X if (quot < theta)
X {
X theta = quot;
X pivot = d;
X (*colnr) = i;
X }
X else
X if (quot == theta)
X if (abs(d) > abs(pivot))
X {
X pivot = d;
X (*colnr) = i;
X }
X }
X }
X return ((*colnr) > 0);
X} /* coldual */
END_OF_lp_solve/dual.c
if test 2805 -ne `wc -c <lp_solve/dual.c`; then
echo shar: \"lp_solve/dual.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex1.lp -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex1.lp\"
else
echo shar: Extracting \"lp_solve/ex1.lp\" \(56 characters\)
sed "s/^X//" >lp_solve/ex1.lp <<'END_OF_lp_solve/ex1.lp'
X-x1 + 2 x2;
X2x1 + x2 < 5;
X-4 x1 + 4 x2 <5;
X
Xint x2,x1;
X
END_OF_lp_solve/ex1.lp
if test 56 -ne `wc -c <lp_solve/ex1.lp`; then
echo shar: \"lp_solve/ex1.lp\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex1.out -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex1.out\"
else
echo shar: Extracting \"lp_solve/ex1.out\" \(100 characters\)
sed "s/^X//" >lp_solve/ex1.out <<'END_OF_lp_solve/ex1.out'
XValue of objective function: 3
Xx1 1
Xx2 2
END_OF_lp_solve/ex1.out
if test 100 -ne `wc -c <lp_solve/ex1.out`; then
echo shar: \"lp_solve/ex1.out\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex2.lp -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex2.lp\"
else
echo shar: Extracting \"lp_solve/ex2.lp\" \(50 characters\)
sed "s/^X//" >lp_solve/ex2.lp <<'END_OF_lp_solve/ex2.lp'
X8 x1 + 15 x2;
X10 x1 + 21 x2 < 156;
X2x1 + x2 < 22;
END_OF_lp_solve/ex2.lp
if test 50 -ne `wc -c <lp_solve/ex2.lp`; then
echo shar: \"lp_solve/ex2.lp\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex2.out -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex2.out\"
else
echo shar: Extracting \"lp_solve/ex2.out\" \(100 characters\)
sed "s/^X//" >lp_solve/ex2.out <<'END_OF_lp_solve/ex2.out'
XValue of objective function: 119.63
Xx1 9.5625
Xx2 2.875
END_OF_lp_solve/ex2.out
if test 100 -ne `wc -c <lp_solve/ex2.out`; then
echo shar: \"lp_solve/ex2.out\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex3.lp -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex3.lp\"
else
echo shar: Extracting \"lp_solve/ex3.lp\" \(47 characters\)
sed "s/^X//" >lp_solve/ex3.lp <<'END_OF_lp_solve/ex3.lp'
X3 x1 + 13 x2;
X2x1 + 9x2 < 40;
X11x1 - 8x2 < 82;
END_OF_lp_solve/ex3.lp
if test 47 -ne `wc -c <lp_solve/ex3.lp`; then
echo shar: \"lp_solve/ex3.lp\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex3.out -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex3.out\"
else
echo shar: Extracting \"lp_solve/ex3.out\" \(100 characters\)
sed "s/^X//" >lp_solve/ex3.out <<'END_OF_lp_solve/ex3.out'
XValue of objective function: 58.8
Xx1 9.2
Xx2 2.4
END_OF_lp_solve/ex3.out
if test 100 -ne `wc -c <lp_solve/ex3.out`; then
echo shar: \"lp_solve/ex3.out\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex4.lp -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex4.lp\"
else
echo shar: Extracting \"lp_solve/ex4.lp\" \(4816 characters\)
sed "s/^X//" >lp_solve/ex4.lp <<'END_OF_lp_solve/ex4.lp'
X- Sd' - Sc' - Sb' - Sa' - Ssub4' - Ssub4 - Ssub3' - Ssub2' - Ssub1' - Sint13' - Sint13 - SF7 - SF6 - SF5 - SF4 - SF3 - SF2 - SF1 - 180 T_max;
XTd' - td' = 0;
XTF3 - tF3 - Td' > 0;
XTF6 - tF6 - Td' > 0;
XTF7 - tF7 - Td' > 0;
XTsub1' - tsub1' - Td' > 0;
XTsub3' - tsub3' - Td' > 0;
XSd' > 1;
XSd' < 3;
Xtd' + 2.58783 Sd' + -0.226304 SF3 + -0.226304 SF6 + -0.226304 SF7 + -0.226304 Ssub1' + -0.226304 Ssub3' > 5.50783;
Xtd' + 1.10907 Sd' + -0.145481 SF3 + -0.145481 SF6 + -0.145481 SF7 + -0.145481 Ssub1' + -0.145481 Ssub3' > 3.85146;
Xtd' + 0.616149 Sd' + -0.107764 SF3 + -0.107764 SF6 + -0.107764 SF7 + -0.107764 Ssub1' + -0.107764 Ssub3' > 3.07849;
XTc' - tc' = 0;
XTF3 - tF3 - Tc' > 0;
XTF4 - tF4 - Tc' > 0;
XTF7 - tF7 - Tc' > 0;
XSc' > 1;
XSc' < 3;
Xtc' + 1.59016 Sc' + -0.226304 SF3 + -0.226304 SF4 + -0.226304 SF7 > 3.75259;
Xtc' + 0.681495 Sc' + -0.145481 SF3 + -0.145481 SF4 + -0.145481 SF7 > 2.72309;
Xtc' + 0.378608 Sc' + -0.107764 SF3 + -0.107764 SF4 + -0.107764 SF7 > 2.24266;
XTb' - tb' = 0;
XTF2 - tF2 - Tb' > 0;
XTF6 - tF6 - Tb' > 0;
XTF7 - tF7 - Tb' > 0;
XTsub2' - tsub2' - Tb' > 0;
XSb' > 1;
XSb' < 3;
Xtb' + 2.19869 Sb' + -0.226304 SF2 + -0.226304 SF6 + -0.226304 SF7 + -0.226304 Ssub2' > 4.92275;
Xtb' + 0.942297 Sb' + -0.145481 SF2 + -0.145481 SF6 + -0.145481 SF7 + -0.145481 Ssub2' > 3.47534;
Xtb' + 0.523499 Sb' + -0.107764 SF2 + -0.107764 SF6 + -0.107764 SF7 + -0.107764 Ssub2' > 2.79988;
XTa' - ta' = 0;
XTF1 - tF1 - Ta' > 0;
XTF5 - tF5 - Ta' > 0;
XTsub2' - tsub2' - Ta' > 0;
XTsub3' - tsub3' - Ta' > 0;
XSa' > 1;
XSa' < 3;
Xta' + 1.97929 Sa' + -0.226304 SF1 + -0.226304 SF5 + -0.226304 Ssub2' + -0.226304 Ssub3' > 4.33767;
Xta' + 0.848267 Sa' + -0.145481 SF1 + -0.145481 SF5 + -0.145481 Ssub2' + -0.145481 Ssub3' > 3.09922;
Xta' + 0.471259 Sa' + -0.107764 SF1 + -0.107764 SF5 + -0.107764 Ssub2' + -0.107764 Ssub3' > 2.52127;
XTF7 - tF7 - Tsub4' > 0;
XSsub4' > 1;
XSsub4' < 3;
Xtsub4' + 0.811889 Ssub4' + -0.226304 SF7 > 2.58243;
Xtsub4' + 0.347952 Ssub4' + -0.145481 SF7 > 1.97085;
Xtsub4' + 0.193307 Ssub4' + -0.107764 SF7 > 1.68544;
XTsub4 - tsub4 = 0;
XTsub4' - tsub4' - Tsub4 > 0;
XSsub4 > 1;
XSsub4 < 3;
Xtsub4 + 0.811889 Ssub4 + -0.226304 Ssub4' > 2.95243;
Xtsub4 + 0.347952 Ssub4 + -0.145481 Ssub4' > 2.34085;
Xtsub4 + 0.193307 Ssub4 + -0.107764 Ssub4' > 2.05544;
XTF7 - tF7 - Tsub3' > 0;
XSsub3' > 1;
XSsub3' < 3;
Xtsub3' + 0.811888 Ssub3' + -0.226304 SF7 > 4.80243;
Xtsub3' + 0.347952 Ssub3' + -0.145481 SF7 > 4.19085;
Xtsub3' + 0.193307 Ssub3' + -0.107764 SF7 > 3.90544;
XTF3 - tF3 - Tsub2' > 0;
XSsub2' > 1;
XSsub2' < 3;
Xtsub2' + 0.811889 Ssub2' + -0.226304 SF3 > 3.32243;
Xtsub2' + 0.347952 Ssub2' + -0.145481 SF3 > 2.71085;
Xtsub2' + 0.193307 Ssub2' + -0.107764 SF3 > 2.42544;
XTF2 - tF2 - Tsub1' > 0;
XSsub1' > 1;
XSsub1' < 3;
Xtsub1' + 0.811889 Ssub1' + -0.226304 SF2 > 3.69243;
Xtsub1' + 0.347952 Ssub1' + -0.145481 SF2 > 3.08085;
Xtsub1' + 0.193307 Ssub1' + -0.107764 SF2 > 2.79544;
XTF1 - tF1 - Tint13' > 0;
XTF4 - tF4 - Tint13' > 0;
XTF5 - tF5 - Tint13' > 0;
XTF6 - tF6 - Tint13' > 0;
XSint13' > 1;
XSint13' < 3;
Xtint13' + 1.97929 Sint13' + -0.226304 SF1 + -0.226304 SF4 + -0.226304 SF5 + -0.226304 SF6 > 4.33767;
Xtint13' + 0.848267 Sint13' + -0.145481 SF1 + -0.145481 SF4 + -0.145481 SF5 + -0.145481 SF6 > 3.09922;
Xtint13' + 0.471259 Sint13' + -0.107764 SF1 + -0.107764 SF4 + -0.107764 SF5 + -0.107764 SF6 > 2.52127;
XTint13 - tint13 = 0;
XTF1 - tF1 - Tint13 > 0;
XTF5 - tF5 - Tint13 > 0;
XTint13' - tint13' - Tint13 > 0;
XTsub1' - tsub1' - Tint13 > 0;
XTsub2' - tsub2' - Tint13 > 0;
XTsub3' - tsub3' - Tint13 > 0;
XSint13 > 1;
XSint13 < 3;
Xtint13 + 3.19637 Sint13 + -0.226304 SF1 + -0.226304 SF5 + -0.226304 Sint13' + -0.226304 Ssub1' + -0.226304 Ssub2' + -0.226304 Ssub3' > 7.04799;
Xtint13 + 1.36987 Sint13 + -0.145481 SF1 + -0.145481 SF5 + -0.145481 Sint13' + -0.145481 Ssub1' + -0.145481 Ssub2' + -0.145481 Ssub3' > 4.97371;
Xtint13 + 0.761039 Sint13 + -0.107764 SF1 + -0.107764 SF5 + -0.107764 Sint13' + -0.107764 Ssub1' + -0.107764 Ssub2' + -0.107764 Ssub3' > 4.00571;
XT_max - TF7 > 0;
XSF7 > 1;
XSF7 < 3;
XtF7 + 0.727024 SF7 > 5.02873;
XtF7 + 0.311582 SF7 > 4.33633;
XtF7 + 0.173101 SF7 > 4.01321;
XT_max - TF6 > 0;
XSF6 > 1;
XSF6 < 3;
XtF6 + 0.727025 SF6 > 4.28873;
XtF6 + 0.311582 SF6 > 3.59633;
XtF6 + 0.173101 SF6 > 3.27321;
XT_max - TF5 > 0;
XSF5 > 1;
XSF5 < 3;
XtF5 + 0.727024 SF5 > 3.91873;
XtF5 + 0.311582 SF5 > 3.22633;
XtF5 + 0.173101 SF5 > 2.90321;
XT_max - TF4 > 0;
XSF4 > 1;
XSF4 < 3;
XtF4 + 0.727025 SF4 > 4.28873;
XtF4 + 0.311582 SF4 > 3.59633;
XtF4 + 0.173101 SF4 > 3.27321;
XT_max - TF3 > 0;
XSF3 > 1;
XSF3 < 3;
XtF3 + 0.727024 SF3 > 5.02873;
XtF3 + 0.311582 SF3 > 4.33633;
XtF3 + 0.173101 SF3 > 4.01321;
XT_max - TF2 > 0;
XSF2 > 1;
XSF2 < 3;
XtF2 + 0.727024 SF2 > 5.02873;
XtF2 + 0.311582 SF2 > 4.33633;
XtF2 + 0.173101 SF2 > 4.01321;
XT_max > TF1;
XSF1 > 1;
XSF1 < 3;
XtF1 + 0.727024 SF1 > 4.65873;
XtF1 + 0.311582 SF1 > 3.96633;
XtF1 + 0.173101 SF1 > 3.64321;
Xint Sd' Sc';
END_OF_lp_solve/ex4.lp
if test 4816 -ne `wc -c <lp_solve/ex4.lp`; then
echo shar: \"lp_solve/ex4.lp\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex4.out -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex4.out\"
else
echo shar: Extracting \"lp_solve/ex4.out\" \(1531 characters\)
sed "s/^X//" >lp_solve/ex4.out <<'END_OF_lp_solve/ex4.out'
XValue of objective function: -1779.5
XSsub4 1
XTsub4 2.3668
XSsub1' 1
XSsub2' 1
XTsub1' 5.8146
XSsub3' 3
XTsub2' 5.4286
XT_max 9.7303
XSsub4' 1
XTsub3' 6.2364
XTsub4' 4.8163
Xtsub4 2.3668
XSint13 3
XTint13 2.5876
Xtsub1' 3.227
Xtsub2' 2.7368
Xtsub3' 3.6488
Xtsub4' 2.4495
XSint13' 1.0266
XTint13' 5.7986
Xtint13 2.5876
Xtint13' 3.211
XSF1 1
XSF2 1.5309
XTF1 9.7303
XSF3 1
XTF2 9.7303
XSF4 1
XTF3 9.7303
XSF5 1
XTF4 9.3603
XSF6 1
XTF5 8.9903
XSF7 3
XTF6 9.3603
XTF7 9.7303
XSa' 1.6322
XSb' 1.8399
XTa' 2.5876
XSc' 1
XTb' 2.6917
XSd' 3
XTc' 3.2939
XTd' 2.1999
XtF1 3.9317
XtF2 3.9157
XtF3 4.3017
XtF4 3.5617
XtF5 3.1917
XtF6 3.5617
XtF7 3.4939
Xta' 2.5876
Xtb' 2.6917
Xtc' 3.2939
Xtd' 2.1999
END_OF_lp_solve/ex4.out
if test 1531 -ne `wc -c <lp_solve/ex4.out`; then
echo shar: \"lp_solve/ex4.out\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/ex5.out -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/ex5.out\"
else
echo shar: Extracting \"lp_solve/ex5.out\" \(3833 characters\)
sed "s/^X//" >lp_solve/ex5.out <<'END_OF_lp_solve/ex5.out'
Xprimal
XValue of objective function: 2.3314e+06
XCOL00001 0
XCOL00010 1365.6
XCOL00100 937.34
XCOL00002 158
XCOL00011 0
XCOL00101 0
XCOL00020 915.23
XCOL00110 800
XCOL00003 158
XCOL00012 0
XCOL00102 312.23
XCOL00021 0
XCOL00111 3544.2
XCOL00030 961.68
XCOL00120 550.89
XCOL00004 0
XCOL00013 1600
XCOL00103 312.23
XCOL00022 187.6
XCOL00112 0
XCOL00031 586.46
XCOL00121 0
XCOL00040 1164
XCOL00130 800
XCOL00005 158
XCOL00014 0
XCOL00104 0
XCOL00023 187.6
XCOL00113 0
XCOL00032 0
XCOL00122 355.5
XCOL00041 0
XCOL00131 4569.3
XCOL00050 835.19
XCOL00140 0
XCOL00006 158
XCOL00015 158
XCOL00105 312.23
XCOL00024 0
XCOL00033 848.11
XCOL00114 0
XCOL00123 355.5
XCOL00042 210.32
XCOL00132 0
XCOL00051 1133.8
XCOL00060 1200
XCOL00007 0
XCOL00016 158
XCOL00106 312.23
XCOL00025 187.6
XCOL00115 312.23
XCOL00034 0
XCOL00124 0
XCOL00043 210.32
XCOL00133 0
XCOL00052 0
XCOL00061 0
XCOL00070 893.97
XCOL00008 2504.4
XCOL00017 375.2
XCOL00107 3533.3
XCOL00026 187.6
XCOL00116 312.23
XCOL00035 187.6
XCOL00125 355.5
XCOL00044 0
XCOL00053 0
XCOL00134 355.5
XCOL00062 241.02
XCOL00071 1856.9
XCOL00080 1178.1
XCOL00009 1430
XCOL00018 14.7
XCOL00108 2566.7
XCOL00027 2210.9
XCOL00117 710.99
XCOL00036 187.6
XCOL00126 355.5
XCOL00045 210.32
XCOL00135 0
XCOL00054 0
XCOL00063 241.02
XCOL00072 0
XCOL00081 0
XCOL00090 800
XCOL00019 2400
XCOL00109 0
XCOL00028 2566.7
XCOL00118 171.66
XCOL00037 420.64
XCOL00127 3533.3
XCOL00046 210.32
XCOL00136 355.5
XCOL00055 210.32
XCOL00064 0
XCOL00073 0
XCOL00082 273.88
XCOL00091 2636.7
XCOL00029 312.67
XCOL00119 710.99
XCOL00038 0
XCOL00128 2566.7
XCOL00047 3176.6
XCOL00137 809.92
XCOL00056 210.32
XCOL00065 241.02
XCOL00074 0
XCOL00083 273.88
XCOL00092 0
XCOL00039 2400
XCOL00129 0
XCOL00048 2566.7
XCOL00138 0
XCOL00057 482.05
XCOL00066 241.02
XCOL00075 241.02
XCOL00084 0
XCOL00093 0
XCOL00049 321.57
XCOL00139 0
XCOL00058 112.85
XCOL00067 3439.4
XCOL00076 241.02
XCOL00085 273.88
XCOL00094 0
XCOL00059 2365.2
XCOL00068 2566.7
XCOL00077 547.75
XCOL00086 273.88
XCOL00095 273.88
XCOL00069 0
XCOL00078 206.56
XCOL00087 3533.3
XCOL00096 273.88
XCOL00079 1883.2
XCOL00088 2566.7
XCOL00097 624.45
XCOL00089 0
XCOL00098 236.08
XCOL00099 1335.4
END_OF_lp_solve/ex5.out
if test 3833 -ne `wc -c <lp_solve/ex5.out`; then
echo shar: \"lp_solve/ex5.out\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/globals.h -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/globals.h\"
else
echo shar: Extracting \"lp_solve/globals.h\" \(1284 characters\)
sed "s/^X//" >lp_solve/globals.h <<'END_OF_lp_solve/globals.h'
X/* function declarations */
X#include "proto.h"
X
X/* global variables */
Xextern int Rows, Columns, Nonnuls, Sum;
Xextern double Extrad;
Xextern double *Pcol; /* [Rows+1] */
Xextern nstring Probname;
Xextern int Totnum, Classnr, Linenr;
Xextern short Bounds, Ranges, Verbose, Debug, Show_results;
Xextern unsigned Cur_eta_size;
Xextern double *Eta_value;
Xextern int *Eta_rownr;
X
Xextern matrec *Mat;
Xextern double *Upbo, *Lowbo;
Xextern nstring *Names;
Xextern int *Cend;
Xextern double *Rh;
Xextern short *Relat;
X
Xextern short *Chsign;
Xextern int *Endetacol;
Xextern int *Rend, *Bas;
Xextern double *Rhs;
Xextern int *Colno;
Xextern short *Basis, *Lower;
X
Xextern double *Solution, *Best_solution, *Orig_rh, *Orig_upbo, *Orig_lowbo;
Xextern short *Must_be_int;
Xextern matrec *Orig_mat;
Xextern int Level;
X
Xextern intrec *First_int;
X
X /* external variables for yy_trans and the yacc parser */
Xextern int yylineno;
Xextern int yyleng;
Xextern int Lin_term_count;
Xextern int Sign;
Xextern char yytext[];
X
Xextern hashelem *Hash_tab[HASH_SIZE];
Xextern rside *First_rside;
Xextern short Ignore_decl;
X
Xextern tmp_store_struct tmp_store;
X
END_OF_lp_solve/globals.h
if test 1284 -ne `wc -c <lp_solve/globals.h`; then
echo shar: \"lp_solve/globals.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/lex.l -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/lex.l\"
else
echo shar: Extracting \"lp_solve/lex.l\" \(1477 characters\)
sed "s/^X//" >lp_solve/lex.l <<'END_OF_lp_solve/lex.l'
XWS [ \n\t]+
XLT [A-Za-z]
XKR [A-Za-z0-9_]
XDI [0-9]
XNM {DI}*\.?{DI}+([Ee][-+]?{DI}+)?
XVR {LT}{KR}*"'"?
XS_OP [-+ \t\n]+
XLOG [<>]?=?
X
X%start COMMENT
X
X%%
X<INITIAL>"/*" {
X BEGIN COMMENT; } /* begin skip comment */
X
X<COMMENT>"*/" {
X BEGIN INITIAL; } /* end skip comment */
X
X<COMMENT>. {
X }
X
X<COMMENT>\n {
X }
X
X<INITIAL>{WS} {
X }
X
X<INITIAL>"," {
X return(COMMA);
X }
X
X<INITIAL>{NM} {
X sscanf(yytext,"%lf",&f);
X return(CONS);
X } /* f contains the last float */
X
X<INITIAL>{S_OP} { Sign=0;
X for(x=0;x<yyleng;x++)
X if(yytext[x]=='-'||yytext[x]=='+')
X Sign=(Sign==(yytext[x]=='+'));
X return (SIGN);
X /* Sign is TRUE if the sign-string
X represents a '-'. Otherwise Sign
X is FALSE */
X }
X
X
X<INITIAL>{VR} {
X {strcpy(Last_var, yytext);}
X return(VAR);
X }
X
X<INITIAL>"*" {
X return(AR_M_OP); }
X
X<INITIAL>{LOG} {
X return(RE_OP); }
X
X<INITIAL>";" {
X return(END_C); }
X
X<INITIAL>. {
X fprintf(stderr,"LEX ERROR : %s lineno %d \n" ,yytext,yylineno); }
X
X%%
END_OF_lp_solve/lex.l
if test 1477 -ne `wc -c <lp_solve/lex.l`; then
echo shar: \"lp_solve/lex.l\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/lp.y -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/lp.y\"
else
echo shar: Extracting \"lp_solve/lp.y\" \(2744 characters\)
sed "s/^X//" >lp_solve/lp.y <<'END_OF_lp_solve/lp.y'
X/* ========================================================================= */
X/* NAME : lp.y */
X/* ========================================================================= */
X
X
X%token VAR CONS SIGN AR_M_OP RE_OP END_C COMMA
X
X
X%{
X#include "defines.h"
X#include "globals.h"
X
X/* globals */
Xchar Last_var[NAMELEN];
Xint Rows;
Xint Lin_term_count;
Xdouble f;
Xint x;
Xint Sign;
Xint isign; /* internal_sign variable to make sure nothing goes wrong */
X /* with lookahead */
Xint make_neg; /* is true after the relational operator is seen in order */
X /* to rember if lin_term stands before or after re_op */
X%}
X
X
X
X%start inputfile
X%%
X
Xinputfile :
X{
X init_read();
X isign = 0;
X make_neg = 0;
X}
X objective_function
X constraints
X int_declarations
X ;
X
Xconstraints : constraint
X | constraints
X constraint
X ;
X
Xconstraint : x_lineair_sum
X RE_OP
X{
X store_re_op();
X make_neg = 1;
X}
X x_lineair_sum
X END_C
X{
X if(Lin_term_count == 0)
X
X {
X fprintf(stderr, "WARNING line %d: constraint contains no variables\n",
X yylineno);
X null_tmp_store();
X }
X if(Lin_term_count > 1)
X Rows++;
X if(Lin_term_count == 1)
X store_bounds();
X Lin_term_count = 0;
X isign = 0 ; make_neg = 0;
X}
X ;
X
Xint_declarations: /* EMPTY */
X | real_int_decls
X ;
X
Xreal_int_decls : int_declaration
X | real_int_decls int_declaration
X ;
X
Xint_declaration : int_declarator vars END_C
X ;
X
Xint_declarator : VAR {/* check_decl(yytext);*/}/* check it here !! */
X ;
X
Xvars : VAR {add_int_var(yytext);}
X | vars VAR {add_int_var(yytext);}
X | vars COMMA VAR {add_int_var(yytext);}
X ;
X
Xx_lineair_sum : x_lineair_term
X | SIGN
X{
X isign = Sign;
X}
X x_lineair_term
X | x_lineair_sum
X SIGN
X{
X isign = Sign;
X}
X x_lineair_term
X ;
X
Xx_lineair_term : lineair_term
X | CONS
X{
X if (isign ^ (!make_neg))
X f = -f;
X rhs_store(f);
X isign = 0;
X}
X ;
X
Xlineair_sum : lineair_term
X | SIGN
X{
X isign = Sign;
X}
X lineair_term
X | lineair_sum
X SIGN
X{
X isign = Sign;
X}
X lineair_term
X ;
X
Xlineair_term : VAR
X{
X if (isign ^ make_neg)
X var_store(Last_var, Rows, (double)-1);
X else
X var_store(Last_var, Rows, (double)1);
X isign = 0;
X}
X | CONS
X VAR
X{
X if (isign ^ make_neg)
X f = -f;
X var_store(Last_var, Rows, f);
X isign = 0;
X}
X | CONS
X AR_M_OP
X VAR
X{
X if (isign ^ make_neg)
X f = -f;
X var_store(Last_var, Rows, f);
X isign = 0;
X}
X ;
X
Xobjective_function: lineair_sum
X END_C
X{
X Rows++;
X Lin_term_count = 0;
X isign = 0;
X make_neg = 0;
X}
X ;
X%%
X# include "lex.yy.c"
END_OF_lp_solve/lp.y
if test 2744 -ne `wc -c <lp_solve/lp.y`; then
echo shar: \"lp_solve/lp.y\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/lp_solve.1 -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/lp_solve.1\"
else
echo shar: Extracting \"lp_solve/lp_solve.1\" \(3747 characters\)
sed "s/^X//" >lp_solve/lp_solve.1 <<'END_OF_lp_solve/lp_solve.1'
X.TH LP_SOLVE 1ES
X.SH NAME
Xlp_solve - Solve (mixed integer) linear programming problem.
X.SH SYNOPSIS
Xlp_solve [option]* "<" <input-file>
X.SH OPTIONS
X.TP 1.2i
X-v
XVerbose mode
X.TP
X-h
XHelp mode, prints the usage
X.TP
X-d
XDebug mode, all intermediate results are printed, and the branch-and-bound
Xdecissions in case of (mixed) integer problems.
X.TP
X-b <bound>
XSpecify a lower limit for the value of the objective function
Xto the program. Only useful for (mixed) integer problems.
XIf close enough, may speed up the calculations.
X.TP
X-i
XPrint all intermediate valid solutions. Can give you useful
Xsolutions even if the total run time is too long.
XOnly useful for (mixed) integer problems.
X.SH DESCRIPTION
XThe linear programming problem can be formulated as: Solve A.x >= V1, with
XV2.x maximal. A is a matrix, x a vector of variables, V1 a vector called
Xthe right hand side, and V2 a vector specifying the objective function.
X.br
XAny of the variables may be specified integer.
X.br
XThis program solves problems of this kind. It is slightly more general
Xthan the above problem, in that every row of A (specifying one equation)
Xcan have its own (un)equality, <=, >= or =. Also there is a possibility to
Xspecify bounds and ranges for individual variables (which could also be done
Xin A of course). The result specifies values for all variables.
X.br
XUses a 'Simplex' algorithm and sparse matrix methods, for pure LP problems.
XIf one or more of the variables is declared integer, the Simplex algorithm is
Xiterated with a branch and bound algorithm, until the desired optimal
Xsolution is found.
X.SH "INTERRUPT"
XIn order to make it possible to get useful solutions for a mixed integer
Xproblem which takes too long to finish completely, the "interrupt" signal
X(kill -INT, ^C for many people) will not terminate the program, but print the
Xbest valid solution found sofar. If you see all zeros, it implies that no
Xvalid solution has been found yet. To really terminate the program, use a
Xdifferent signal, like KILL.
X.SH "INPUT SYNTAX"
XThe input syntax is a set of algebraic expressions and "int" declarations in
Xthe following order:
X.sp
X<objective function>
X.br
X<constraint>+
X.br
X<declaration>*
X.sp
Xwhere:
X.TP 0.2i
X-
X<objective function> is a linear combination of variables, ending with a semicolon.
X.TP
X-
X<constraint> is a linear combination of variables and constants,
Xfollowed by a relational operator, followed again by a linear combination of
Xvariables and constants, ending with a semicolon. The relational operator can
Xbe any of the following: "<" "<=" "=" ">" ">=".
X.TP
X-
X<declaration> is of the form: "int" <var>+ ";" Commas are allowed between
Xvariables.
X.sp
XSo, the simplest linear problem consists of an objective function and 1
Xconstraint.
X.SH EXAMPLE
XThe simple problem:
X.sp
Xx1 >= 1
X.br
Xx2 >= 1
X.br
Xminimise x1 + x2 (= maximise -(x1 + x2)), with x1 integer
X.sp
Xcan be written as follows:
X.sp
X-x1 + -x2;
X.br
Xx1 > 1;
X.br
Xx2 > 1;
X.br
Xint x1;
X.sp
XThe correct result for (x1, x2) is of course (1, 1).
X.SH BUGS
XDue to the implementation, bounds (constraints on just one variable), do not enter into the A-matrix. Therefore, extremely simple problems with only bounds sometimes cannot be solved, because they define the empty problem. Real-life examples probably never have this property.
X.SH SEE ALSO
XThe implementation of the simplex kernel was mainly based on:
X.br
XW. Orchard-Hays: "Advanced Linear Programming Computing Techniques", McGrawhill
X1968
X.SH CONTRIBUTED BY
XM.R.C.M. Berkelaar
X.br
XEindhoven University of Technology
X.br
XDesign Automation Section
X.br
XP.O. Box 513
X.br
XNL-5600 MB Eindhoven, The Netherlands
X.br
Xphone ...-31-40-473345
X.br
XE-mail: michel@es.ele.tue.nl
X.SH STATUS
XUse at own risk. Bug reports are welcome, as well as succes stories.
END_OF_lp_solve/lp_solve.1
if test 3747 -ne `wc -c <lp_solve/lp_solve.1`; then
echo shar: \"lp_solve/lp_solve.1\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/lp_solve.man -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/lp_solve.man\"
else
echo shar: Extracting \"lp_solve/lp_solve.man\" \(4622 characters\)
sed "s/^X//" >lp_solve/lp_solve.man <<'END_OF_lp_solve/lp_solve.man'
X
X
X
XLP_SOLVE(1ES) UNIX Programmer's Manual LP_SOLVE(1ES)
X
X
X
XNAME
X lp_solve - Solve (mixed integer) linear programming prob-
X lem.
X
XSYNOPSIS
X lp_solve [option]* "<" <input-file>
X
XOPTIONS
X -v Verbose mode
X
X -h Help mode, prints the usage
X
X -d Debug mode, all intermediate results are
X printed, and the branch-and-bound decissions in
X case of (mixed) integer problems.
X
X -b <bound> Specify a lower limit for the value of the
X objective function to the program. Only useful
X for (mixed) integer problems. If close enough,
X may speed up the calculations.
X
X -i Print all intermediate valid solutions. Can give
X you useful solutions even if the total run time
X is too long. Only useful for (mixed) integer
X problems.
X
XDESCRIPTION
X The linear programming problem can be formulated as: Solve
X A.x >= V1, with V2.x maximal. A is a matrix, x a vector of
X variables, V1 a vector called the right hand side, and V2 a
X vector specifying the objective function.
X Any of the variables may be specified integer.
X This program solves problems of this kind. It is slightly
X more general than the above problem, in that every row of A
X (specifying one equation) can have its own (un)equality, <=,
X >= or =. Also there is a possibility to specify bounds and
X ranges for individual variables (which could also be done in
X A of course). The result specifies values for all variables.
X Uses a 'Simplex' algorithm and sparse matrix methods, for
X pure LP problems. If one or more of the variables is
X declared integer, the Simplex algorithm is iterated with a
X branch and bound algorithm, until the desired optimal solu-
X tion is found.
X
XINTERRUPT
X In order to make it possible to get useful solutions for a
X mixed integer problem which takes too long to finish com-
X pletely, the "interrupt" signal (kill -INT, ^C for many peo-
X ple) will not terminate the program, but print the best
X valid solution found sofar. If you see all zeros, it implies
X that no valid solution has been found yet. To really ter-
X minate the program, use a different signal, like KILL.
X
X
X
XPrinted 6/17/92 1
X
X
X
X
X
X
XLP_SOLVE(1ES) UNIX Programmer's Manual LP_SOLVE(1ES)
X
X
X
XINPUT SYNTAX
X The input syntax is a set of algebraic expressions and "int"
X declarations in the following order:
X
X <objective function>
X <constraint>+
X <declaration>*
X
X where:
X
X - <objective function> is a linear combination of variables,
X ending with a semicolon.
X
X - <constraint> is a linear combination of variables and con-
X stants, followed by a relational operator, followed again
X by a linear combination of variables and constants, ending
X with a semicolon. The relational operator can be any of
X the following: "<" "<=" "=" ">" ">=".
X
X - <declaration> is of the form: "int" <var>+ ";" Commas are
X allowed between variables.
X
X So, the simplest linear problem consists of an objective
X function and 1 constraint.
X
XEXAMPLE
X The simple problem:
X
X x1 >= 1
X x2 >= 1
X minimise x1 + x2 (= maximise -(x1 + x2)), with x1 integer
X
X can be written as follows:
X
X -x1 + -x2;
X x1 > 1;
X x2 > 1;
X int x1;
X
X The correct result for (x1, x2) is of course (1, 1).
X
XBUGS
X Due to the implementation, bounds (constraints on just one
X variable), do not enter into the A-matrix. Therefore,
X extremely simple problems with only bounds sometimes cannot
X be solved, because they define the empty problem. Real-life
X examples probably never have this property.
X
XSEE ALSO
X The implementation of the simplex kernel was mainly based
X on:
X W. Orchard-Hays: "Advanced Linear Programming Computing
X
X
X
XPrinted 6/17/92 2
X
X
X
X
X
X
XLP_SOLVE(1ES) UNIX Programmer's Manual LP_SOLVE(1ES)
X
X
X
X Techniques", McGrawhill 1968
X
XCONTRIBUTED BY
X M.R.C.M. Berkelaar
X Eindhoven University of Technology
X Design Automation Section
X P.O. Box 513
X NL-5600 MB Eindhoven, The Netherlands
X phone ...-31-40-473345
X E-mail: michel@es.ele.tue.nl
X
XSTATUS
X Use at own risk. Bug reports are welcome, as well as succes
X stories.
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
XPrinted 6/17/92 3
X
X
X
END_OF_lp_solve/lp_solve.man
if test 4622 -ne `wc -c <lp_solve/lp_solve.man`; then
echo shar: \"lp_solve/lp_solve.man\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/main.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/main.c\"
else
echo shar: Extracting \"lp_solve/main.c\" \(4961 characters\)
sed "s/^X//" >lp_solve/main.c <<'END_OF_lp_solve/main.c'
X#include <signal.h>
X#include "defines.h"
X#include "globals.h"
X#include "patchlevel.h"
X
X/* declare all global variables here */
Xint Rows, Columns, Nonnuls, Sum;
Xdouble Extrad;
Xdouble *Pcol;
Xnstring Probname;
Xint Totnum, Classnr, Linenr;
Xshort Bounds, Ranges, Verbose, Debug, Show_results;
Xunsigned Cur_eta_size;
Xdouble *Eta_value;
Xint *Eta_rownr;
X
X/* Variables which contain the original problem statement */
Xmatrec *Mat; /* initial problem matrix */
Xdouble *Upbo, *Lowbo; /* bounds on variables */
Xnstring *Names; /* contains the names of rows and columns */
Xint *Cend; /* Column start indexes in Mat */
Xdouble *Rh; /* Right hand side of original problem */
Xshort *Relat; /* Relational operators of original problem */
X
Xtmp_store_struct tmp_store;
Xrside *First_rside;
Xhashelem *Hash_tab[HASH_SIZE];
X
X/* Variables which are used during solving */
Xshort *Chsign; /* tells which row was multiplied by -1 before solving */
Xint *Endetacol; /* Column start indexes in Eta */
Xint *Rend, *Bas; /* ?? */
Xdouble *Rhs; /* right hand side of Eta ?? */
Xint *Colno; /* ?? */
Xshort *Basis, *Lower; /* ?? */
X
X/* New variables for mixed integer solving */
Xdouble *Solution, *Best_solution; /* to store solutions */
Xshort *Must_be_int; /* indicates whether variable should be int */
Xmatrec *Orig_mat; /* To store original version of Mat */
Xdouble *Orig_upbo; /* To store original version of Upbo */
Xdouble *Orig_lowbo; /* To store original version of Lowbo */
Xdouble *Orig_rh; /* To store original version of Rh */
Xint Level; /* the recursion level of solve */
Xintrec *First_int;
Xshort Ignore_decl;
X
Xshort is_int(double value)
X{
X double tmp;
X
X tmp = value - floor(value);
X if(tmp < EPSILON)
X return(1);
X if((tmp > 0.5) && ((1.0 - tmp) < EPSILON))
X return(1);
X return(0);
X}
X
Xvoid allocate_globals(void)
X{
X Sum = Rows + Columns;
X Cur_eta_size = ETA_START_SIZE;
X
X CALLOC(Eta_value, Cur_eta_size, double);
X CALLOC(Eta_rownr, Cur_eta_size, int);
X CALLOC(Pcol, Rows + 2, double);
X CALLOC(Cend, Columns + 2, int); /* column boundaries in Mat */
X CALLOC(Endetacol, Sum + 2, int);
X CALLOC(Rend, Rows + 2, int);
X CALLOC(Bas, Rows + 2, int);
X CALLOC(Lowbo, Sum + 2, double);
X CALLOC(Orig_lowbo, Sum + 2, double);
X CALLOC(Upbo, Sum + 2, double);
X CALLOC(Orig_upbo, Sum + 2, double);
X CALLOC(Names, Sum + 2, nstring);
X CALLOC(Rh, Rows + 2, double); /* rhs for Mat */
X CALLOC(Orig_rh, Rows + 2, double); /* rhs for Mat */
X CALLOC(Rhs, Rows + 2, double);
X CALLOC(Colno, Nonnuls + 2, int);
X CALLOC(Mat, Nonnuls + 1, matrec); /* (initial) problem matrix */
X CALLOC(Orig_mat, Nonnuls + 1, matrec); /* (initial) problem matrix */
X CALLOC(Relat, Rows + 2, short);
X CALLOC(Basis, Sum + 2, short);
X CALLOC(Lower, Sum + 2, short);
X CALLOC(Chsign, Rows + 2, short);
X
X CALLOC(Solution, Sum + 1, double);
X CALLOC(Best_solution, Sum + 1, double);
X CALLOC(Must_be_int, Columns + 1, short);
X} /* allocate_globals */
X
X
Xvoid signal_handler(int sig)
X{
X fprintf(stderr, "Caught signal %d, will print intermediate result\n", sig);
X print_solution(stderr, Best_solution);
X}
X
X
Xint main (int argc, char *argv[])
X{
X int i, failure;
X double obj_bound = -INFINITE;
X
X for(i = 1; i < argc; i++)
X {
X if(strcmp(argv[i], "-v") == 0)
X Verbose = TRUE;
X else if(strcmp(argv[i], "-d") == 0)
X Debug = TRUE;
X else if(strcmp(argv[i], "-i") == 0)
X Show_results = TRUE;
X else if(strcmp(argv[i], "-b") == 0)
X obj_bound = atof(argv[++i]);
X else if(strcmp(argv[i], "-h") == 0)
X {
X printf("Usage of %s version %s:\n", argv[0], PATCHLEVEL);
X printf("%s [-v] [-d] [-h] [-b <bound>] [-i] \"<\" <input_file>\n",
X argv[0]);
X printf("-h:\t\tprints this message\n");
X printf("-v:\t\tverbose mode, gives flow through the program\n");
X printf("-d:\t\tdebug mode, all intermediate results are printed,\n\t\tand the branch-and-bound decisions\n");
X printf("-b <bound>:\tspecify a lower limit for the value of the objective function\n\t\tto the program. If close enough, may speed up the calculations.\n");
X printf("-i:\t\tprint all intermediate valid solutions. Can give you useful\n\t\tsolutions even if the total run time is too long\n");
X exit(0);
X }
X else
X fprintf(stderr, "Unrecognized command line option %s, ignored\n",
X argv[i]);
X }
X /* construct basic problem */
X yyparse();
X Rows--; /* @!? MB */
X allocate_globals();
X readinput(Cend, Orig_rh, Relat, Orig_lowbo, Orig_upbo, Orig_mat, Names);
X
X
X /* from now on, catch interrupt signal to print best solution sofar */
X signal(SIGINT, signal_handler);
X
X /* solve it */
X Best_solution[0] = obj_bound; /* lower bound of objective function */
X failure = solve(Orig_upbo, Orig_lowbo);
X
X /* print result */
X if(!failure)
X print_solution(stdout, Best_solution);
X else
X fprintf(stderr, "No solution.\n");
X
X return (0);
X} /* main */
END_OF_lp_solve/main.c
if test 4961 -ne `wc -c <lp_solve/main.c`; then
echo shar: \"lp_solve/main.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/patchlevel.h -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/patchlevel.h\"
else
echo shar: Extracting \"lp_solve/patchlevel.h\" \(25 characters\)
sed "s/^X//" >lp_solve/patchlevel.h <<'END_OF_lp_solve/patchlevel.h'
X#define PATCHLEVEL "1.0"
END_OF_lp_solve/patchlevel.h
if test 25 -ne `wc -c <lp_solve/patchlevel.h`; then
echo shar: \"lp_solve/patchlevel.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/proto.h -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/proto.h\"
else
echo shar: Extracting \"lp_solve/proto.h\" \(2241 characters\)
sed "s/^X//" >lp_solve/proto.h <<'END_OF_lp_solve/proto.h'
X#ifdef __STDC__
X# define P(s) s
X#else
X# define P(s) ()
X#endif
X
X
X/* dual.c */
Xvoid rowdual P((int *rownr ));
Xshort coldual P((int *numeta , int *rownr , int *colnr , short *minit , double *prow , double *drow ));
X
X/* lp.c */
Xint yyparse P((void ));
X
X/* read.c */
Xvoid yyerror P((char *string ));
Xvoid check_decl P((char *str ));
Xvoid add_int_var P((char *name ));
Xvoid init_read P((void ));
Xint hashvalue P((nstring string ));
Xhashelem *gethash P((nstring variable ));
Xcolumn *getrow P((column *p , int row ));
Xbound *create_bound_rec P((void ));
Xvoid null_tmp_store P((void ));
Xvoid store P((nstring variable , int row , double value ));
Xvoid store_re_op P((void ));
Xvoid rhs_store P((double value ));
Xvoid var_store P((char *var , int row , double value ));
Xint store_bounds P((void ));
Xvoid resize_eta P((void ));
Xvoid readinput P((int *cend , double *rh , short *relat , double *lowbo , double *upbo , matrec *mat , nstring *names ));
X
X/* tran.c */
Xvoid ftran P((int start , int end , double *pcol ));
Xvoid btran P((int numc , double *row ));
X
X/* main.c */
Xshort is_int P((double value ));
Xvoid allocate_globals P((void ));
Xvoid signal_handler P((int sig ));
X
X/* solve.c */
Xvoid condensecol P((int rownr , int numc , double *pcol ));
Xvoid addetacol P((int *numc ));
Xvoid presolve P((void ));
Xvoid setpivcol P((short *lower , int varin , int numeta , double *pcol ));
Xshort colprim P((int *colnr , int *numeta , short *minit , double *drow ));
Xvoid minoriteration P((int colnr , int rownr , int *numeta ));
Xvoid rhsmincol P((double *theta , int rownr , int varin , int numeta ));
Xvoid invert P((int n , int *numeta , int *numinv ));
Xshort rowprim P((int *rownr , double *theta , double *pcol ));
Xvoid iteration P((int *numc , int *rownr , int *varin , double *theta , double *up , short *minit , short *low , short *primair , short *smotes , int *iter , int *numinv ));
Xint solvelp P((void ));
Xvoid construct_solution P((double *sol ));
Xint solve P((double *upbo , double *lowbo ));
X
X/* write.c */
Xvoid print_solution P((FILE *stream , double *sol ));
Xvoid print_indent P((void ));
Xvoid debug_print_solution P((double *sol ));
Xvoid debug_print_bounds P((double *upbo , double *lowbo ));
Xvoid debug_print P((char *format , ...));
X
X#undef P
END_OF_lp_solve/proto.h
if test 2241 -ne `wc -c <lp_solve/proto.h`; then
echo shar: \"lp_solve/proto.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/tran.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/tran.c\"
else
echo shar: Extracting \"lp_solve/tran.c\" \(1231 characters\)
sed "s/^X//" >lp_solve/tran.c <<'END_OF_lp_solve/tran.c'
X#include "defines.h"
X#include "globals.h"
X
X#ifdef alliant
X#pragma global safe (Eta_rownr, Eta_value)
X#pragma global assoc
X#endif
X
Xvoid ftran(int start,
X int end,
X double *pcol)
X{
X int i, j;
X int k, r;
X double theta;
X
X#ifdef alliant
X#pragma safe (pcol, Endetacol)
X#pragma routine permutation (Eta_rownr)
X#endif
X
X if (Verbose)
X printf("ftran\n");
X for (i = start; i <= end; i++)
X {
X k = Endetacol[i] - 1;
X r = Eta_rownr[k];
X theta = pcol[r];
X if (theta != 0)
X for (j = Endetacol[i - 1]; j < k; j++)
X pcol[Eta_rownr[j]] += theta * Eta_value[j]; /* cpu expensive line */
X pcol[r] *= Eta_value[k];
X }
X
X#ifdef alliant
X#pragma loop novector
X#endif
X
X for (i = 0; i <= Rows; i++)
X if (abs(pcol[i]) < EPSEL)
X pcol[i] = 0;
X} /* ftran */
X
Xvoid btran(int numc,
X double *row)
X{
X int i, j, k;
X double f;
X
X#ifdef alliant
X#pragma safe (row, Endetacol)
X#endif
X
X if (Verbose)
X printf("btran\n");
X for (i = numc; i >= 1; i--)
X {
X f = 0;
X k = Endetacol[i];
X for (j = Endetacol[i - 1]; j < k; j++)
X f += row[Eta_rownr[j]] * Eta_value[j];
X if (abs(f) < EPSEL)
X row[Eta_rownr[k - 1]] = 0;
X else
X row[Eta_rownr[k - 1]] = f;
X }
X} /* btran */
END_OF_lp_solve/tran.c
if test 1231 -ne `wc -c <lp_solve/tran.c`; then
echo shar: \"lp_solve/tran.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lp_solve/write.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lp_solve/write.c\"
else
echo shar: Extracting \"lp_solve/write.c\" \(1465 characters\)
sed "s/^X//" >lp_solve/write.c <<'END_OF_lp_solve/write.c'
X#include "defines.h"
X#include "globals.h"
X#include <stdarg.h>
X
X/* this is the ansi version ... */
X
Xvoid print_solution(FILE *stream, double *sol)
X{
X int i;
X
X if(Verbose)
X for (i = 0; i <= Sum; i++)
X fprintf(stream, "%-10s%16.5g\n", Names[i], sol[i]);
X else
X {
X fprintf(stream, "Value of objective function: %16.5g\n", sol[0]);
X for (i = Rows + 1; i <= Sum; i++)
X fprintf(stream, "%-10s%16.5g\n", Names[i], sol[i]);
X }
X} /* print_solution */
X
X
Xvoid print_indent(void)
X{
X int i;
X
X fprintf(stderr, "%2d", Level);
X for(i = Level; i > 0; i--)
X fprintf(stderr, "--");
X fprintf(stderr, "> ");
X} /* print_indent */
X
X
Xvoid debug_print_solution(double *sol)
X{
X int i;
X
X if(Debug)
X for (i = 0; i <= Sum; i++)
X {
X print_indent();
X fprintf(stderr, "%-10s%16.5g\n", Names[i], sol[i]);
X }
X} /* debug_print_solution */
X
X
Xvoid debug_print_bounds(double *upbo, double *lowbo)
X{
X int i;
X
X if(Debug)
X for(i = Rows + 1; i <= Sum; i++)
X {
X if(lowbo[i] != 0)
X {
X print_indent();
X fprintf(stderr, "%s > %10.3g\n", Names[i], lowbo[i]);
X }
X if(upbo[i] != INFINITE)
X {
X print_indent();
X fprintf(stderr, "%s < %10.3g\n", Names[i], upbo[i]);
X }
X }
X} /* debug_print_bounds */
X
X
Xvoid debug_print(char *format, ...)
X{
X va_list ap;
X
X if(Debug)
X {
X va_start(ap, format);
X print_indent();
X vfprintf(stderr, format, ap);
X fputc('\n', stderr);
X va_end(ap);
X }
X} /* debug_print */
X
END_OF_lp_solve/write.c
if test 1465 -ne `wc -c <lp_solve/write.c`; then
echo shar: \"lp_solve/write.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of archive 1 \(of 2\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked both archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0
exit 0 # Just in case...
--
Andrew Patrick acting as Comp.Sources.Reviewed Moderator
Department of Communications, Ottawa, CANADA
csr@calvin.dgbt.doc.CA
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads