-
Notifications
You must be signed in to change notification settings - Fork 1
/
README
113 lines (86 loc) · 3.79 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
TTVPlex - A revised simplex implementation
==========================================
TTVPlex stands vor TavTraVuoSimplex and is an implementation of the revised
simplex algorithm which was programmed as an exercise during the university
course "Linear and Integer Programming (ADM II), WS 2010/11" at TU Berlin.
For more information about the course visit:
http://www.math.tu-berlin.de/coga/teaching/wt10/adm2/
Authors
-------
* Christoph Tavan
* Tuan Tran
* Quyen Vuong
The code is (c) 2011 by the authors and distributed under the MIT license.
Download
--------
The TTVPlex project is hosted on github:
https://github.com/ctavan/ttvplex
You can download the source as a tarball there or clone the the git repository:
git clone git://github.com/ctavan/ttvplex.git
Installation
------------
Requirements:
* TTVPLex requires a recent version of the GNU C++ compiler g++ to be
installed on the system.
* TTVPlex makes use of The GNU Multiple Precision Arithmetic Library (GMP).
GMP needs either to be installed on the system or be compiled locally.
Mac OS X:
1. It is easiest to use Macports (http://www.macports.org/) to install GMP:
sudo port install gmp
2. Create a symbolic link to the correct Makefile:
ln -s Makefile.macosx Makefile
3. Compile:
make
Debian/Ubuntu:
1. You can install GMP through apt-get. If you do so, use the makefile
`Makefile.macosx` and adjust the `GMP_INC` and `GMP_LIB` paths
accordingly.
If you don't have super-user privileges, follow these steps:
2. Create a symbolic link to the correct Makefile:
ln -s Makefile.debian Makefile
3. Compile:
make
Documentation
-------------
You can generate a doxygen documentation of the code by issuing the command:
make doxy
The documentation is then located in the `docs`-folder.
Usage
-----
You can get a list of all available commandline-options by issuing:
./ttvplex -h
Assuming you want to solve the LP-file located at `examples/example3.lp`, use:
./ttvplex -powx -v 1 -i examples/example3.lp
You can increase the verbosity of the output:
./ttvplex -powx -v 2 -i examples/example3.lp
Some Notes
----------
* Currently for each row in the coefficient-matrix an artificial variable
is created for phase 1 of the simplex algorithm. The number of variables
could greatly be reduced, if artificial variables would only be introduced
for constraints other than <= (where a slack variable can play the role
of the artificial variable).
* We implemented Blands anti-cycling rule since it is easy to implement.
Implementing the lexicographic anti-cycling rule might be more efficient.
* There might be problems, if the upper bound of a variable is negative...
Then one should substitute y = -x.
* There also seem to be some problems if an LP contains unbounded variables.
Licence
-------
The MIT License
Copyright (c) 2011 Christoph Tavan
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.