Date: 4 May 1995 12:17:49 GMT
From: Philippe Refalo
Subject: Adding / Removing constraints in REVISED SIMPLEX ??
What are the most efficient (or the most used) methods for
adding or removing a constraint in a linear program
solved with the revised Simplex method ?
More precisely, how can we efficiently enlarge or reduce the inverse of a basis or a basis 'LU-factorised ' ?
This problem is encoutered in Constraint Logic Programming over linear constraints where constraints are added and removed one by one, or in ILP solvers when adding a x=0 or a x=1 constraint during the enumeration phase.
Thank you for pointing any reference or trick.
Philippe Refalo, LIM - Laboratoire d'Informatique de Marseille, URA CNRS 1787, F-13288 MARSEILLE, Cedex 09 - FRANCE, refalo@lim.univ-mrs.fr, (33) 91.26.93.58
Date: 4 May 1995 17:23:30 GMT
From: el@fusl.ac.be (Etienne Loute)
Subject: Adding / Removing constraints in REVISED SIMPLEX ??
Modern invert routines are pretty fast. Unless you have to add or
delete a row very frequently, i.e. every few simplex iterations,
you'd better reinvert ! The alternative would be to update your current
basis inverse representation to take into account the row change.
In the case of an LU inverse (explicit or product form), there exist
algorithms for doing this in a number of operation o(m**2) in the
dense case, (m is the number of rows).
Note that if you delete a row, it means that the basic variable affected to this row becomes non basic at a level which is not necessarily one of its bounds (or possibly not the right bound). You will have to perform a special iteration to see at which bound you will drive it (or exchange it with another basic variable).
If you add a row, you may have to perform a short phase-one procedure to find a basic variable to affect to this row, in such a way that you have a basic feasible solution.
Frequent row addition or deletion may require you to adopt data structures departing from the traditional column-wise packing scheme, e.g. non-zero coefficients of the same column stored in contiguous elements of a one dimensional array with rows indices in a parallel array, completed with an array of pointers toward each column. You can adopt a doubly linked list for the non-zero coefficients. However repacking may be more efficient if you use fast sort routines.
I would definitely not treat x=0 or x=1 as adding a general constraint but rather as fixing the value of the variable !
Etienne Loute, FUSL, Brussels, CORE and QANT/UCL, Louvain-la-Neuve, Belgium, el@fusl.ac.be, eloute@core.ucl.ac.be
Date: 3 May 1995 19:13:18 GMT
From: ijchang@flagstaff.Princeton.EDU (Isaac J. Chang)
Subject: Megiddo's Algorithm for LP
I was curious as to whether anyone out there has, or knows of actual
implementations of Megiddo's linear time algorithm for linear programming
in either R^2 or R^3. The algorithm is described in SIAM Journal on Computing
Nov 83, v12, number 4.
I'm especially interested to seeing how the geometric figures and primitives are represented.
Date: Wed, 17 May 1995 14:28:37 GMT
From: nf141@fim.uni-erlangen.de (Wolfgang Paulus)
Subject: searching for LP case studies
I am looking for some prepared case studies of managed LP-applications
from industry, agricultural, services, which can be used in the extended
solver-module of MS-excel.
Especially I am searching for applications based on blending-, cutting stock-, transportation-, assignment-, multiperiod planning-problems and models of stochastic LP, goal programming.
The case studies should provide students of Business Administration with a selection of management problems solved with models of LP. For educational reasons it is necessary that the case studies are not too "theoretical" and can be represented on a PC.
It would be grateful, if you can mail me a case study or even guide me to some papers, books, etc.
I am looking forward to any comment. E-mail:nf141@fim.uni-erlangen.de
Thanks, Wolfgang Paulus
I need to solve linear programming problems with the following characteristics:
I presume that the solutions to these problems will always be integers, however, that isn't important to me.
Any help in locating fast solvers for this class of problem will be very much appreciated. Thanks in advance for your time and trouble.
Jeff Barnett
Date: Thu, 8 Jun 1995 09:58:23 -0400
From: Michael Trick <mt1w+@andrew.cmu.edu>
Subject: Want specialized LP method.
Looks like the LP from a Critical Path Network. If all the C(i,j) in the
C(i,j) <= x[i]-x[j]
are nonnegative (as seems from part 4), then simply starting from 1 and setting each variable in turn to be the smallest value possible will get the smallest x[i] for all i, relative to whatever value for x[1] that is chosen. Therefore, it will minimize x[n]-x[1]. This will, of course, take a fraction of a second for the problem sizes given.
Mike Trick
Date: 8 Jun 1995 21:35:36 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: Want specialized LP method.
Mike: I agree that it looks like a CPM kind of network, and I'm with you
as far as initializing the x's as small as possible. The trick is to make
x[1] as large as possible without further increasing x[n] - which amounts
to an incremental approach, updating "critical" paths until either a
variable hits its upper bound or node n is added to the critical path. I
communicated this in more detail by e-mail to the poster. This kind of
approach strikes me as more efficient than general simplex stuff.
Paul
SCI.OP-RESEARCH Digest Mon, 26 June, Volume 2: Issue26
Date: Thu, 22 Jun 1995 09:57:11 +0100 (BST)
From: hunter@scs.leeds.ac.uk (H T Albright)
Subject: Efficient Critical Point Generation
Does anyone know of any code that will generate the set of efficient critical
points for a multiple objective linear programming problem?
Thanks for your help,
Hunter Albright
------------------------------
Date: 23 Jun 1995 19:29:21 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: Efficient Critical Point Generation
I don't know of any code specifically designed to find *all* the corner
points of the efficient frontier of a MOLP (I assume that's what you mean
by "critical"). The problem is equivalent to finding all the extreme
points of a polyhedron, although in essence you are only interested in a
subset of (very roughly) half of them.
I quote below from a post to sci.math.symbolic some time back, regarding a program you might find useful. (I have no experience with it myself.) Conversion of your MOLP to a convex polyhedron specified algebraically is easy (at least conceptually easy).
>From: fukuda@dma.epfl.ch
>Newsgroups: comp.theory,sci.math.symbolic
>Subject: convex hull, vertex enumeration program available
>Date: 16 Feb 1994 17:34:35 GMT
>Organization: Ecole Polytechnique Federale de Lausanne
>---------------------------
>cdd version c0.51 available
>---------------------------
>This is to inform that a C-implementation of the double description
>method for enumerating all vertices and extremal rays of a general
>convex polyhedron P={x: b - A x >= b} is available via anonymous
>ftp from
>
> ftp.epfl.ch (128.178.139.3)
> directory: incoming/dma
> file: cdd-051.tar.Z
>
>Note that this program is made specially for solving degenerate
>problems. If your input is nondegenerate, there are other faster
>programs - I suppose.
>--------------
> Komei Fukuda
> Departement de Mathematiques
> Ecole Polytechnique Federale de Lausanne
> CH-1015 Lausanne
> Switzerland fax +41-21-693 42 50 tel +41-21-693 42 44
> email : fukuda@dma.epfl.ch or fukuda@gssm.otsuka.tsukuba.ac.jp
I've omitted extensive parts of the post for brevity. You might want to
contact the author directly.
Paul
------------------------------
Date: 23 Jun 1995 19:34:14 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: Efficient Critical Point Generation
In article <1995Jun22.085711.17072@leeds.ac.uk>,
hunter@scs.leeds.ac.uk (H T Albright) wrote:
->Does anyone know of any code that will generate the set of efficient
critical
->points for a multiple objective linear programming problem?
->
->Thanks for your help,
->
->Hunter Albright
Oops, spoke too soon in my previous post. I just noticed the following information (in John Gregory's LP FAQ):
>ADBASE is a package that computes all efficient (i.e., >nondominated) extreme points of a multiple objective linear >program. It is available without charge for research and instructional >purposes. If someone has a genuine need for such a code, they should >send a request to: Ralph E. Steuer, Faculty of Management Science, >Brooks Hall, University of Georgia, Athens, GA 30602-6255.
A couple of my colleagues used ADBASE several years ago (I think) with good results. I thought ADBASE only found some efficient points, but according to this, it finds all of them.
Paul
------------------------------
Date: Wed, 21 Jun 1995 18:45:25 +0100 (BST)
From: hunter@scs.leeds.ac.uk (H T Albright)
Subject: MOLP Data
I am looking for some Multi-Objective Linear Programming data sets to run some
tests on. Does anyone know where I might be able to find some?
Thanks for your help,
Hunter Albright
------------------------------ ------------------------------
Date: Thu, 22 Jun 1995 22:31:55 GMT
From: lct6v@kelvin.seas.Virginia.EDU (Luong Canh Tran)
Subject: what are the largest LP's solved?
Dear OR colleagues,
I am a research student that is working on a sub-problem that
can be formulated as a linear program with the following
summary characterisics:
N+1 + n*n + N*(N-1)/2 continuous variables
1+ n*(1+N) + 3*(N*N-1)/2 constraints.
I have concern that this problem might not be computationally
feasible since I am dealing with LP the sizes of
n = 5000 to 25000
N= 300 to 500.
My first question to all is: (1) what are the largest sized
LP9s that have been solved?
Secondly, since part of the constraint set is the assignment
problem constraints: (2) what are the largest assignment solved?
Any help or references to either question will be greatly
appreciated.
--
Luong Tran
Department of Systems Engineering
University of Virginia
Phone: (804)982-2075, email: lct6v@virginia.edu
------------------------------
Date: 23 Jun 1995 18:22:34 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: what are the largest LP's solved?
I read something years ago about a team at Stanford U., headed by George
Dantzig, solving a macroeconomic model with something like 2 million
columns (not sure about rows, half a million sounds about right).
Technology has moved ahead since then, so I would not take that as an upper
bound on solvable problem size. Then again, I'm guessing that Dantzig had
sole use of (or large blocks of time on) a pretty darn big computer to do
that (federal grant $ was involved, of course), and I did not hear what the
turnaround time on runs was.
What was the Military Airlift Command (I forget the new designation) reputedly also had a pretty large LP model for scheduling flights. There was a write-up in OR/MS Today sometime after Desert Shield, but I don't recall seeing the size.
Your model, I trust, will be sparse (or else forget it). The large number of columns might be handled by some combination of column generation, off-line storage and (considerable) patience. I'm not sure about the number of rows, though.
Paul
------------------------------
Date: 26 Jun 1995 09:13:52 +1000
From: amal@kurango.cit.gu.edu.au (Amal De Silva)
Subject: what are the largest LP's solved?
Have you considered parallel programming. For my Ph.D thesis
I have been doing work on parallel interior point algorithms for
block structured LPs. I have implemented a interior point algorithm
to solve bi-angular LPs (Constraint matrix has diagonal blocks with
linking columns and linking rows). It can be used for block
angular LPs (only linking rows) or dual block angular LPs
(only linking columns). This algorithm exploits the block structure
for parallelisation. Most very large sparse LPs have some sort of
a block structure. The fact that you have n*n term in the number
of variables makes me suspect this problem has a block structure as
well. You can have n blocks each with n columns. This approach
is differant from decomposition as only the linear
algebra (Cholesky factorisation) parallelised. The basic
interior point algorithm is used.
If anybody is interested let me know. I have written two research
reports and I can email it over if interested.
regards
Amal de Silva
amal@cit.gu.edu.au
Ph.D student,
School of Computing and Information Technology,
Griffith University,
Nathan, QLD 4111.
AUSTRALIA
------------------------------
------------------------------
Date: (null)
H. Wolkowicz asked what happens in an interior point method
for LP if the Newton equations are singular or near singular.
It turns out that, even though the coefficient matrix is
nearly singular, a theoretically accurate solution can
still be computed. This follows from the existence of
bound due to Stewart and Todd independently, although
A. Forsgren has recently traced the bound back to Dikin.
The bound applies to linear systems of the form
The bound implicit in the Stewart-Todd theorem is not necessarily attained
by Cholesky factorization or other similar algorithms, and so
Cholesky and other algorithms should be considered unstable for this
problem.
An algorithm for solving the Newton system that actually
achieves the Stewart-Todd stability bound was proposed in my paper
"Stable Numerical Algorithms for Equilibrium Systems", SIMAX, 15:1108,
1994. Patty Hough and I have a simpler algorithm which is described in a
preprint
available on line (see my home page at Cornell,
Wolkowicz's original question was motivated by SDP rather than LP.
It's not known (at least, it's not known to me) how much of this
work extends from LP to SDP.
SCI.OP-REASEARCH, Mon, 3 Jul, 95 Volume 2: Issue 27
Date: Mon, 26 Jun 1995 14:37:27 GMT
lct6v@kelvin.seas.Virginia.EDU (Luong Canh Tran) wrote:
In terms of variables, the largest one that I know of is one I was involved in.
It is derived from crew scheduling, 837 rows, 12.75 million variables, and we
used a technique we call "sifting" to solve it on a Cray. This technique is a
form of column generation that keeps the problem size small. The reference is:
@article{int:Bixby1,
Bixby has actually solved this problem directly via the dual simplex method on
a
SGI Power Challenge with gobs of memory.
At CPLEX, I've seen problems with over 100,000 constraints and 1,000,000
variables from real customers, which we solve on machines that have sufficient
memory. Extra variables don't seem to be the problem, but extra constraints
make the problem harder for both the simplex methods and CPLEX's barrier
method.
In terms of constraints, both CPLEX and OB1 have solved large-scale fleet
assignment problems, one of which had 270,796 rows, and 303,986 columns.
The problem mentioned above would seem to have over 12 million constraints, and
I don't think there is a hope of solving that directly. Given that the author
asked:
> Secondly, since part of the constraint set is the assignment
I would venture to say there is an appropriate column generation/decomposition
technique for the large problem that takes advantage of the embedded assignment
problem, which will do far better than any direct method.
-Irv Lustig
PS The above in no way represents an advertisement for CPLEX Optimization, Inc.
or its products.
------------------------------
Date: 30 Jun 1995 00:35:27 GMT
Barr, R. and J.S. Turner, 1981. Microdata File Merging through Large-
Scale Network Technology, Mathematical Programming Study 15, 1-22.
------------------------------
Date: 18 Jul 1995 19:45:00 GMT
Date: 31 Jul 1995 18:54:37 GMT
My question: has there been any work regarding the possibility of
using an APPROXIMATE polytope to attack a combinatorial optimization problem? For example, if I omit some constraints, can I still solve the problem exactly most of the time? Or if I use wrong constraints, can I round the LP solution to get an exact or approximate solution to the optimization problem?
Thanks.
Date: 2 Aug 95 10:03:06
Yes, there has been quite a bit of work done on this. The angle I am
most familiar with is using polynomial-time solvable linear programs
to find approximate solutions to integer programs that model NP-hard
optimization problems. The usual tack is to formulate a "relaxation"
of the problem under consideration; that is, a linear program such
that all integer solutions are feasible for the linear program and
have the same value as they do in the integer program. The easiest
way to do this is usually to drop the integrality conditions on the
variables. Then the trick becomes finding a good integer solution
given the optimal solution to the linear program. Sometimes one can
simply round the variables to the nearest integer. In some cases
treating the value of a fractional variable as a probability and
setting the variable randomly gives very good results. Sometimes
other techniques are needed. Other recent work has looked at using
polynomial-time solvable convex programs to find good solutions to
integer programs.
I can provide references to those who are interested.
David Williamson
dpw@watson.ibm.com
Date: 31 Jul 1995 17:16:15 -0500
Also, x1 appears in the first three constraints, that is, truck 1 is made up of loads 1, 2, and 3. xi is a binary decision, whether to run that truck or not.
The questions I have regarding this formulation for a problem with
approximately 60,000 - 100,000 variables are:
Thanks in advance for any suggestions and/or pointers to references.
I think a good MIP solver (I'm biased towards CPLEX :-> ) should be able to handle such a problem. The key is to identify the constraints as SOS type 1 constraints. This will make the branch and bound solver more efficient.
**other questions deleted**
Irv Lustig
Date: 7 Aug 1995 13:45:04 -0400
This is a well-known problem called a "Binary Packing problem." In
terms of solving it, there are good heuristics as well as IP
solutions. Of course, the best might be to use a primal heuristic to
get a good feasible solution, and use this incumbent solution to
reduce the size of the branch and bound tree.
Good references include the book Integer Programming by G. Nemhauser and L. Wolsey, and a recent paper in Annals of Operations Research (v.57) by D. Wedelin.
Gregory Glockner
Date: 7 Aug 1995 10:59:48 +0100
Hello
This is a follow-up to a news post that has already expired on my
machine. It asked whether Mastermind can be solved using linear
programming (I think).
Well, I just wanted to say that there is quite an elegant solution in
constraint logic programming. Mastermind is one of quite a few puzzles and games discussed in Van Hentenryck's book [1]; he has a program which is a total of 48 lines long, in CHIP (a Prolog-like language with constraints). He then has a few modifications for speed, which involve changing 20 lines.
Basically his book is an attempt to incorporate OR techniques (and CSP
techniques) into a high-level declarative language. So the basic
algorithms may be nothing special to readers of this newsgroup, but the ease of programming, of maintenance, and of presentation, may be worth a look.
Date: 29 Aug 1995 11:53:41 -0400
Bob Silverman
Date: 29 Aug 1995 17:53:02 GMT
A tough problem. Any ideas, anyone?
John Chandler
Date: 29 Aug 1995 14:06:10 -0400
Bob Silverman
Date: 30 Aug 1995 01:24:17 GMT
John Birge, U. Michigan
Date: 30 Aug 1995 10:06:35 -0700
See e.g. Alistair Sinclair's book "Algorithms for random generation and
counting: A Markov chain approach", Birkhauser, 1993.
--
David Eppstein, UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Date: 31 Aug 1995 01:06:01 GMT
Erik Rolland
Date: 31 Aug 1995 01:05:47 GMT
Erik Rolland
Date: 31 Aug 1995 09:40:48 GMT
There's a survey of the area by Ravi Kannan in the Proceedings of the
35th Annual IEEE Foundations of Computer Science, pp. 656--671 (1994) (which I am skimming madly as I write this). If you don't have access to these proceedings, you might try asking Professor Kannan for a copy directly; I believe he is in the CMU Computer Science department.
David Williamson
Date: Mon, 18 Sep 1995 21:08:01 UNDEFINED
The problem I'm posting arises in the context of planning under uncertainty. Here is a step by step explanation (at least an attempt).
Step 1: Given a state of the world x(i), determine a decision d which
minimizes a cost function C(d,x(i)) subject to miscellaneous constraints.
This is supposed to be a LP and so, easy to solve.
Step 2: If each state occurs with probability p(i), it is sensible to look
for d which minimizes the cost expectation i.e. sum over i of p(i) *
C(d,x(i)). When the p(i)'s are given, the problem is still linear.
Step 3: Now suppose the p(i)'s are unknown but an order exists between them: state 1 is more probable than state 2, state 2 is more probable than state 3, and so on. The literature identifies the following criterion: min over d of max over p(i) of p(i) * C(d,x(i)) subject to the previous constraints and some conditions on the probabilities e.g. p(1) >= p(2); p(2) >= p(3); ... The problem is no longer linear. I'm wondering whether it is possible to solve this problem, by decomposition, through a sequence of LP s. Could anyone explain me how and/or point me out some references ?
Step 4: At step 2, the problem is to minimize an expectation i.e. a mean. How can I find the decision d which minimizes the median ? The search for the median is itself a LP problem:minimize sum over i of p(i) * ( deltap(d,x(i)) + deltan(d,x(i)) ) with the previous constraints andC(d,x(i)) = median(d) + deltap(d,x(i)) - deltan(d,x(i))So there are two embedded LP problems: (a) min over d of median(d) and (b) the search for the median. Any idea to tackle the problem ?
Thanks in advance for your help.
Alain.
Date: 21 Sep 1995 03:58:05 GMT
I have developed a management model for joint use of surface and ground water resources under deterministic framework. The model is linear programming model and has 115 constraints (including objective function) and 309 variables. Formulation of the model looks like a goal programming. I have tried to solve this model on UNIX-based system using XMP. When I run this program it found initial feasible solution, however, it could not improve it and abondened the problem with a message of too many rejected pivots.
Does anyone out there know that what could it be reason and how I can improve the solution further? Any help is greatly appreciated.
Sincerely,
HAKAN
Date: Thu, 21 Sep 1995 10:40:49 +0100
I think the rejected pivots message is produced by the invert routine
(an LU factorization routine from the Harwell Library ?).
While it does not compete with industrial codes such as CPLEX, OSL,
XA, XPRESS, to quote a few, XMP is decent from a numerical point of
view. The size of your problem is small and you should not run into
numerical trouble, unless it is badly scaled.
XMP doesn't have automatic scaling. You have to do it by yourself :
i.e. apply scaling factors to columns and rows so as to limit the dispersion of non zero values in the constraint matrix around
one (in absolute value).
Etienne Loute
Date: 25 Sep 95 09:31:39 CDT
.333333 x + 0.666666 y = 1
could easily give rise to near-singular basis matrices, when the
obvious intent of the equation
x + 2y = 3
is not at all challenging numerically. I don't know if XMP might
give the "rejected pivots" message because of this, but it would
seem to be worth checking.
John W. Gregory
Date: 12 Oct 1995 01:41:04 GMT
where cx is the objective function. However, now we're sort of back where we started since b is not known, so I'm asking myslef whether this is really an LP problem. I don't really care about the value of b, but rather if there exists a vector b that satisfies Bb >= 0. I'd appreciate any suggestions.
PS. I don't really know anything about solving LP problems, and I might be way off track here. Maybe I'm missing something obvious... DS.
Date: 16 Oct 1995 16:27:39 GMT
Hi Peter,
Peter Lindstrom
You can just solve the problem
min 0
All standard LP solvers do a 2-phase method which will stop and
tell you if your problem is not feasible.
Geometrically, you are asking for a vector b that makes lass than
a 90 degree and with the rows of B, so maybe you don't even need
to do LP at all if you know something about B.
Saying as though we're at the same school, let me know if you need
any further help and we can get together.
Regards,
Date: 17 Oct 95 02:36:19 GMT
Matthew Saltzman
Date: Tue, 17 Oct 1995 11:13:15 -0600
Although I'm not a student reader I'll answer this. On correspondence with Peter it seems he wants Bx > 0 (he is trying to find a hyperplane that strictly separates some points).
The solution is based on the theorem of alternatives. This says that
either System (I) has a solution, or system (II) has a solution but not both.
System (I) is:
Bx > 0
System (II) is:
yB = 0
One can prove this by using duality.
So to determine if the system Bx>0 is feasible we simply do a phase I of the simplex method on the problem
Max 0.y
S. Raghavan
Date: 19 Oct 95 23:57:52 GMT
The alternative theorem analysis might be a little deep for students
in a basic course, but the problem I posed is a nice little textbook
problem, I think.
Matthew Saltzman
Date: Thu, 16 Nov 1995 18:16:48
I'm a research scientist in Norway working on a LP model which purpose is to optimize productmix in the fish processing industry. I have limited experience with LP-programming and have met challenges that I've not been able to solve myself yet.
I'll try to explain the problem through a brief summary:
The model is a one day production planning modell for a fish proceccing plant featuring four different departments. In dep. A, the cutting senter, the fish is cut, before it continues to senter B where it's filleted. Then there are two departments in paralell, C and D, which produces two different products from the same raw material and could be driven simoultaneously. These departments in parallell causes some trouble because it includes a certain time aspect.
The object function is to maximize the marginal profit contribution, and there are several constraints. Constraints interesting in this context are those connected to production capacity, which are buildt up like this:
capacity needed to produce one unit of each product in department A*quantity of each product =< available capacity in department A.
Equal constraints are made for departments B, C and D. The problem is caused by the paralelity in C and D because we don't say antything about when capacity is available in the departments.
The output of the model are the quantities of each product that is most
profitable to produce, however the model sometimes presents results not possible to produce during a day.
This example illustrates the problem:
If we produce one fish specie through A,B and C from 08.00 to
12.00, the modell will find there are 8 hours available (if we have an 8 hour day) in department D for the rest of the production that day. That's obviously not true cause we're at 12 o'clock, and four of the eigth ours that the modell think is available is between 08.00 and 12.00 and therefore not available even if they're not "used".
The last line shows the problem. Virtually there are 8 hours available in this department for producing product **, but as the first operation in that production batch is not started before 12.00, it's not possible to use capacity before 12.00.
Does anybody have any ideas of how it's possible to take care of this problem, or do anybody have any references to articles on similar problems?
I would be extremely grateful for any suggestions!
Boerge Soleng
Date: 19 Nov 1995 05:24:15 GMT
borges@fiskforsk.norut.no (Boerge Soleng) wrote:...
>Hello!
This is not a trivial problem. If you finish this you will know more
about the factory then the management.
I have written a very similar program for a large fish canning factory.
You need to think of the program as an inventory model. That is how you can control the time function.
Use max/min numbers on the inventory variables to control how much is butchered at any one time and how much offset time you need to get the fish to the next stage of processing, i.e.cooking or cooling time.
I cannot share my program with you as it is very special for the business I am in but I can offer you ideas to help you.
My data is set up in Lotus worksheets using dynamic lookup tables that will generate the different processing times depending on the fish size and will control the min/max levels for each hour.
I use XA solver by Sunset Software; the program is an mixed integer (MIP) program with several thousand constraints and variables. It has the capacity for 10 different fish sizes (adjustable) and our factory works 24 hrs a day.
It works quite well, running on a 486 in a couple of minutes. We run it
every day to get the schedule for the next day.
A good example of prod scheduling is in the textbook by
Hiller and Lieberman; Intro to Op Research, 4th ed, pg 255 - 258
A paper I found very useful;
"The application of a product mix linear programming model in corporate policy making" by Jack Byrd, Jr and Ted Moore, in Management Sci, Vol 24, # 13, 1978.
Best Regards
Date: 18 Nov 1995 23:37:53 GMT
Implementing the DW decomposition algorithm for LP from a modular MPS system is a reasonable project. Efficiency will depend
on the level at which the MPS system is used. Just calling
the primal revised simplex routine or the routines whose assembling makes the steps of the the primal revised simplex will not bring the same degree of efficiency. The following references report on these aspects for an implentation based on the MPSX/370, the 10 years ago IBM LP workhorse for mainframes. MPSX/370 had a revised simplex callable library from PL/I. In spite of the high degree of modularity of the library (you could rebuild your own variant of revised simplex from building bloks) we brought a few minor changes to the original sources, such as a variant of the classical FORMC routine which sets up the initial row vector for the simplex multipliers BTRAN operation. This changes allows for an implicit handling of the composite objective row of the subproblems. BTW this changes turns out very useful in goal programming. We also implented an automatic intermediate proposal generation on the fly which required carrying
the coupling part of the columns as data in non binding rows.
An efficient modern revised simplex implementation will not allow you to do that.
The DW algorithm is conceptually simple.
Implementing it in a textbook fashion by using the standard
services of an MPS system may be disapointing. For example
in the last cycles you may spend very few simplex iterations in
the subproblem, revising the data to accomodate the change in the
objective row may be time consuming compared to an implicit
scheme. Reconstruction of the final solution is a problem that
calls for an appropriate solution. Last but not the least, choosing
an appropriate way to specyfy the block structure in the data
(block angular for one level DW, or other for multilevel DW)
is important.
Our implentation was relying extensively on the filed form
of the problem (the so called PROBFILE) penalized by a
non standard form for floating point data : the last
two bytes of the IBM 8 bytes for floating double were
overwritten by the two bytes of the row index of the coefficient.
This one and an half precision was not a good thing for the proposal
data in the master problem.
In a reengineered code I would definitely save all the computational data structures, in fact the whole current problem context, in memory, when switching from master or subproblem to another subproblem. Clearly a code whose computational data structures are pointerized offers an advantage.
J. K. Ho, E. Loute, 'An advanced implementation of the Dantzig Wolfe
decomposition algorithm for linear programming', Mathematical Programming, t. 20, 1981, p. 303-326.
J. K. Ho, E. Loute, 'Computational experience with advanced
implementation of decomposition algorithms for linear programming', Mathematical Programming, vol 27, 1983, pp. 283-290.
Olivier Janssens, E. Loute, 'Solving Arborescent Linear Programs
with Nested Decomposition' pp 285-314 in ``Contribution
to Operations Research and Economics'', The 20th anniversary of CORE, B. Cornet et H. Tulkens eds., MIT Press, 1989.
There have been implementations of DW based on more modern MPS syste and at least one (the IBM OSL package) has it as an option. I am aware of a CPLEX implenetation by a team headed by JP Vial at Geneva university. There exist a fortran code named DECOMP, documented in a book by J. Ho and alii (Springer Verlag). It implements one level DW for block angular
structures.
I have used DECOMP for years for experimental and teaching purposes and maintain it on Mac platform. It uses a neat MPS based format with one major drawback, it does not allow the bound and range sections.
I have a set of block angular test problems from small to medium size (up to a few thousand rows for the whole problem with ten blocks and a few hundred coupling rows). I can make them available.
One should not hastily draw conclusions from experimenting. For
example applying the one level DW on a block angular LP where
the coupling rows gather all intertemporal constraints from a
time phased LP can be disapointing, whereas nested DW can perform well.
Date: 13 Dec 1995 11:13:57 GMT
A FINITE PIVOT RULE (like Bland's) will take me to the optimum basic
solution from wherever I am on an UNIQUE PATH of pivot steps. The
collection of ALL such paths forms a tree (in the non-degenerate case)
rooted in the optimum basic solution. In order to implement an
enumeration algorithm for listing ALL basic solutions I try to REVERSE
(cf. Avis, Fukuda) a finite pivot rule going from the optimum solution
"node" backwards to all the others.
This is the setting...
My question is: How can I estimate the "breadth" of this enumeration
tree (for a given pivot rule, say Bland's or lexicographic rule). Does
there exist an upper bound (polynomial???). (I think there is none...)
Any pointers are most warmly appreciated!
I wonder if someone can help me with this problem, i am having some troubles to solve it :
Here it goes :
A market studies company wants to do a study, by probing in 7 places of a district. This 7 places must be probed by order, in 7 days of the same week, i. e., in Monday ( of the chosen week) we must probe the 1st place, in tuesday the second place and so on.This way wich place will be probe only and only one day.
The number of inquirers for probing a place in one day, depends of the same and the foward board gives us the values needed
To wich inquirer ( of the 3 existents ) that is used in this probing,
the company will pay 30 u.m. The inquirers contracted cost to the company 40 u.m eac one.
All the expenses of any inquirer during ther activity must be payied by the company.This way one activity day of an inquirer cost the company 10 u.m.Besides one inquirer after probing one place can probe another one day after or can rest one day and probe another only 2 days after.
Wich of this choises have a certain cost ( transport & staying). The
next matrix shows the cost to the company for inquirer after he probe a place i and will probe a place j ( j=i or j=j+1).
Any help with this problem will be apreciated
Date: Tue, 23 Jan 96 21:02:28 PDT
In our company's steering quality committee we have decided to look for a linear program system in order to reduce our annual off spec products.
We are a petrochemical plant which manufactures plastic material especially Polypropylene as a raw material for the plastic industry.
Our annual capacity is over 150,000 ton in this plant alone and we produce propylene by ourselves for self consumption.
Our company is highly computerised (TDC3000 in the plant, PI, windows NT & AS400 computers which can "talk" with each other in real time) WE want to use linear programming in order to plan the production in the PP plant with respect to our constraints which are for example low products stock policy, sales changing demands, raw material and additives stock & availability, product's saling prices, as much as possible transitions among products manufecturing etc.
Does anyone know or familiar with that kind of program which is ACTUALLY working in that kind of industry?
Any kind of information regarding WORKING software on either AS400 or Windows NT will be gratefully appreciated. Pls send any info available ASAP
To contact me please sent e-mail or fax to 972-4-8221928
Thank you and best regards
A. Nattiv
Date: 24 Jan 1996 11:26:07 -0500
Their product, Exsys Professional, an expert system shell, interfaces
directly with PI, LINDO (a linear programming package) and SQL databases.
Not to mention custom screens and hypertext capability. I am developing systems for airline use.
Point of contact: Michael Eskew, Sales Manager 505-256-8356. He can
provide you with names of customers who use the system and have interfaced with PI for plant automation.
Lloyd Prince
Date: 12 Feb 1996 10:27:09 GMT
I would like to optimize my code, especially by reinverting periodically the basis.
Can someone address me to a good book with a detailed explanation about refactorization or directly explain it to me?
Thanx & Bye
PS: I'd prefere a direct explation, because our local library have a very
few books.
Date: Thu, 15 Feb 1996 15:23:25 -0500
lp_solve, this is a C implementation of a Revised Simplex Method (with
source code) ftp://ftp.es.ele.tue.nl/pub/lp_solve
I used an old book called:
Advanced linear-programming computing techniques,
by W. Orchard-Hays, McGraw-Hill, 1968
There should be some newer books with this information, if you
find one, please let me know.
Date: 14 Feb 96 11:18:00 CST
Thanks.
Steve Bush
Date: 15 Feb 1996 12:08:36 +0100
Marco
Date: Fri, 01 Mar 1996 01:38:38 GMT
Antonio Iglesias
Date: 01 Mar 1996 19:34:29 GMT
Reference: pp. 237f in K. G. Murty's book _Linerar_Programming_
New York: Wiley and Sons, 1983
ISBN 0-471-09725-X
Date: 4 Mar 1996 07:54:49 GMT
If one or more of the artificial variables remain at nonzero level at the
end of phase 1, the problem is infeasible. The constraint to which the
artificial variable at nonzero level is related is violated. However,
you cannot say that this is 'the' constraint that is responsible for
infeasibility. However, it is safe to say that it is one of several
mutually exclusive constraints that render the problem infeasible.
Greetings
There is now quite a literature on the analysis of infeasible linear
programs. One major approach that I have been involved with is the
identification of an Irreducible Infeasible Subset (IIS) of
constraints. An IIS is a set of constraints which is infeasible, but
which becomes feasible if any one or more constraints from the set is
removed. Finding an IIS among the many constraints defining an LP
helps the analyst to zero in on the cause of the infeasibility.
Following is a list of some of my papers on the topic -- see also work
by Harvey Greenberg, Jennifer Ryan, Mark Parker, Mehrdad Tamiz and
others on this topic. There are also a few words on this topic in
John Gregory's LP FAQ.
A list of my publications on infeasibility analysis:
J.W. Chinneck (1996), "Computer Codes for the Analysis of Infeasible
Linear Programs", Journal of the Operational Research Society, vol.
47, pp. 61-72.
J.W. Chinneck (1996), "Feasibility and Viability", chapter to
appear in the forthcoming book "Recent Advances in Sensitivity
Analysis and Parametric Programming", T. Gal and H.J. Greenberg
(eds.), Kluwer.
J.W. Chinneck (1995), "An Effective Polynomial-Time Heuristic
for the Minimum-Cardinality IIS Set-Covering Problem", Annals of
Mathematics and Artificial Intelligence, to appear.
J.W. Chinneck (1995), "Analyzing Infeasible Nonlinear Programs",
Computational Optimization and Applications, vol. 4, pp. 167-179.
J.W. Chinneck and M.A. Saunders (1995), "MINOS(IIS) Version 4.2:
Analyzing Infeasibilities in Linear Programs", technical note in
the European Journal of Operational Research, vol. 81, pp. 217-218.
J.W. Chinneck (1995), "Localizing and Diagnosing Infeasibilities in
Networks", ORSA Journal on Computing, to appear.
J.W. Chinneck (1994), "MINOS(IIS): Infeasibility Analysis Using
MINOS", Computers and Operations Research, vol. 21, no. 1, pp. 1-9.
J.W. Chinneck and Wojtek Michalowski (1994), "MOLP Formulation
Assistance Using LP Infeasibility Analysis", Proceedings of
MOPGP'94, Portsmouth England, to appear.
J.W. Chinneck (1993), "Finding the Most Useful Subset of Constraints
for Analysis in an Infeasible Linear Program", Systems and Computer
Engineering Technical Report SCE-93-07.
J.W. Chinneck and E.W. Dravnieks (1991), "Locating Minimal Infeasible
Constraint Sets in Linear Programs", ORSA Journal on Computing, vol.
3, no. 2, pp. 157-168.
I have also established a set of infeasible LP test problems on
the netlib in the lp/infeas directory.
The following article/its references may contain useful infomation:
"Computer Codes for the Analysis of Infeasible Linear Programs",
J. W. Chinneck, Journal of the Operational Research Society
(1996) 47, 61-72.
Dicky Yan.
Date: 8 Mar 1996 09:54:28 -0500
I have a problem which, I know, it can be solved, but I just cannot
make the model.....can u make LP-model from this?
It's Cutting the tube... and the goal is to minimize waste tubing.
You have unlimited number of 6290 mm long tubes. The tube diametes are 8 mm and 16 mm.
You have to cut following lengths and quantities form both diameters.
Working cycle
First you make a trim cut of 60 mm. Then comes cutting process until
the end of each 6290 mm long tube (i.e. as far as u can make cuttings from each 6290 mm long rawtubing - the remaining piece is so called rest piece).
The above mentioned 2 different cutting lengths behaves differently:
Cut A. This cutting method can be used until the length of rawmaterial is
minimum 357 mm + the length being cut with that method. (For ex. cut length 200 mm, method A can make cuttings until the rawmaterial is 557 mm long).
The minimum cutting length for this method is 3*tube diameter (for ex 16 mm
diam it is 3*16mm=48 mm). With this cutting method you can start cutting
>from the beginning of 6290 mm long tube.
Cut B. This cutting method is possible until the remaining rawmaterial is
min. 60 mm long. The minimum cut length is 150 mm. With this method it is not
possible to start cutting from the beginning of the tube. This means, you
have to use first Cut method a until the rawmaterial is 3000 mm long. After
that you can use this method.
Now. The 6290 mm tube can be cut with both of these methods by using any of
above mentioned combinations. Say. 6 pcs with method A and 5 pcs with method
B. and so on...The point is to find optimum combination of cut-lengths for
minimizing the waste. (Waste = trim cut 60 mm + rest pieces)
Can this problem be solved with LP-model and simplex algorithm?
Date: 10 Mar 1996 05:25:47 -0500
Milt Gutterman in Skokie, IL
Date: Sun, 10 Mar 1996 13:33:53 GMT
Henry
Date: Tue, 12 Mar 1996 13:35:14 +0100
I'm currently working on a research project involving Realtime
modelchecking.
As Sub-Problem I encountered the following constraint problem.
I have a vector of non-negative, real-valued variables X
(X^T=(x1,x2,x3,x4.....,xn)), a vector of integer constants C
(C^T=(c1,c2,c3,c4.........,cm)) and an integer matrix A=
This matrix is sparsely filled (at most 5 non-zero entries per row),
but there is no definite structure and it can become moderately large
(hoe groot?).
I am now looking for a package that can efficiently
Preferably written in C, source code included.
Does any one know of such packages?
Replies preferably by e-mail
Thanx in advance,
Bart Knaack
L.S.,
I am looking for some references to material on the practical
use of stochastic LP. I have seen some books on the subject, but
we would like get some information, including the small details that
make it work, from someone who has implemented stochastic LP in
(larger) applications.
Thanks,
Date: Tue, 12 Mar 1996 11:08:50 +0100
I am studiing interior-point-methods for LP. (for example: Todd, Liao) and would like to know a nice idea for finding an
INTERIOR - Starting - Point
for a given Standar form problem min cTx s.t. Ax=b
because I want to test different programs with NETLIB-Testset -- examples.
Thanks Armin
Date: Tue, 19 Mar 1996 12:00:29 GMT
Solve the LP.
Identify the range of right hand sides that maintain feasibility, say from bcurr_i-bred_i to bcurr_i+binc_i for each basic variable.
Now suggest that bcurr_ is changed (wlog increase), from bcurr_i to bnew_i and that two or more changes are made. Then the 100pc rule says that the current basis remains feasible and optimal so long as:
sigma_i ((bnew_i-bcurr_i)/binc_i) <= 1
which can be shown to be true by considering the convex space defined by the rhs feasibility conditions. But it would be nice to have a formal treatment.
Any help gratefully received
Try the book "Applied Mathematica Programming" by
Bradley/Hax/Magnanti
Date: Tue, 02 Apr 1996 19:35:18 -0800
Does anyone know the answer to the following question:
suppose you have the system of linear constraints Ax=b
and that you define other variables, z, with another linear system:
Tx=z;
is it possible and how, to define a new system, say, Dz=c, defining the
same region to which the z belong (by means of Ax=b and Tx=z)?
In other words, which is the form of D and c?
Thank you
Marco
Date: 3 Apr 1996 13:03:47 GMT
This problem is a variable elimination problem,
i.e. you want to eliminate x variables from the system {Ax=b, Tx=z}.
The well-known Fourier agorithm can perform such an elimination
It is exponential in the worst case and and, unfortunately, in
practice too, and there is no a priori structure for the resulting
system.
Philippe
I assume you really want "=", not ">=" ?
write it as a composed system
clearly you need an equivalence reduction. Since, without restriction,
A has full row rank, this means dim(x)>=dim(b), if b is "general".
let s=dim(b), d=dim(z),n=dim(x). If d<=min(n,s) and T has full row rank, apply a regular transform Q on T* (transpose) such that the last n-s rows become zero and apply the same transform to A*. If the first s rows of the transformed matrix A1 say, are a regular s*s matrix then (and only then) you are done by eliminating the corresponding s variables y_1,..,y_s, y=Q^(*-1)x from the system A1y=b , since T1y=T(Q*)y does not depend on y_{s+1},..,y_n. for fourier elimination, which philippe mentioned, see stoer&witzgall, convexity and optimization in finite dimensions I, springer, 1970.
hope it helps
peter
Date: Mon, 08 Apr 1996 21:20:13 +0000
Thank you.
PS: Please also answer by mail.
--
Louis Bronne
Date: 8 Apr 96 20:58:04 GMT
The ellipsoid algorithm due to Khachian (from about 1980) is described nicely in Chvatal's _Linear Programming_ (Freeman, 1983). Some interesting combinatorial applications are covered in
The algorithm due to Karmarkar from the mid-80s is described readably in an article by John Hooker in:
Matthew Saltzman
Date: 9 Apr 1996 16:47:28 GMT
The book also lists a mess of papers that cover these topics. For ellipsoid methods, Sofer and Nash list:
Bland, Goldfarb and Todd. "The Ellipsoid Method: a survey" Operation Research 40 (1981)
Schrader. "The ellipsoid method and its implications." OR Spektrum 5 (1983).
Schrader. "Ellipsoid Methods in Modern Applied MAthematics-Optimization and Operations Research", B. Korte (editor), North-Holand, Amsterdam (1982).
Gacs and Lovasz. "Khachiyan's Algorithm for linear programming" Mathematical Programming Study 14. (1981).
Hope this helps.
--
Mike hennebry@plains.NoDak.edu
Date: 11 Apr 1996 14:18:21 -0400
A. Nemirovsky and D. Yudin, "Problem Complexity and Method Efficiency in Optimization," J. Wiley, 1983.
It is also described in less detail in my own book, "Nonlinear
optimization: Complexity Issues," Oxford Univ. Press, 1991.
In the N-Y book, the method is called the "modified method of centers
of gravity" (MMCG) rather than the ellipsoid method. The algorithm is
an iterative method that returns a solution to a convex optimization
problem with accuracy epsilon, where epsilon is specified by the user.
I would not label Khachiyan's application of the ellipsoid algorithm to linear programming a "straightforward specialization". Khachiyan's
version of the ellipsoid algorithm is polynomial time for LP in the
usual Turing machine sense of polynomial time. This requires some
fairly subtle techniques to obtain an exact optimum LP solution in
polynomial time (because, as I mentioned above, the Yudin-Nemirovsky ellipsoid method returns only approximations).
-- Steve Vavasis
Date: 11 Apr 96 18:12:56 GMT
You're probably thinking of N. Z. Shor, who has several papers on
convex programming. Khachian's paper also builds on work by Levin,
and by Judin and Nemirovskii. All of the references appear in
Chvatal.
--
Matthew Saltzman
Date: Thu, 11 Apr 96 15:52:10 PDT
Judin & Nemirovskii
also upon earlier work by Shor, Agmon, Motzkin and Schoenberg.
Date: 12 Apr 1996 11:35:53 -0500
given a floating point number N with L bits, and a positive integer D,
find integers p and q such that |N-p/q| < 2^-D and 0< q<=D ?
My recollection is that today this can be done in linear time.
What about then?
Mike hennebry@plains.NoDak.edu
Date: 18 Apr 1996 08:39:49 GMT
Two good references in this field are:
Papadimitriou, Steiglitz
"Combinatorial Optimization"
Prentice Hall, 1982
and
A. Schrijver
"Theory of Linear and Integer Programming"
which explain the Karmarkar- and Ellipsoid-method and give
references.
Date: 24 May 1996 13:13:13 GMT
Any help would be greatly appreciated.
Many Thanks
Date: Fri, 31 May 1996 11:50:29 +0100
My appologies (sincere) if I am posting to the wrong group...If so can you redirect me?
The problem:
When determining the winner of a competition like the Mathematical Contest in Modeling, there are generally a large number of papers to judge.
Let's say there are P=100 papers. A group of J judges is collected to
accomplish the judging. Funding for the contest constrains both the number of judges that can be obtained and the amount of time that they can judge. For example, if P=100, then J=8 is typical.
Ideally each judge would read each paper and rank-order them, but there are too many papers for this. Instead, there will be a number of screening rounds in which each judge will read some number of papers and give them scores. Then some selection scheme is used to reduce the number of papers under consideration: If the papers are rank-ordered, then the bottom 30%
that each judge rank-orders could be rejected. Alternatively, if the judges do not rank order the papers, but instead give them numerical scores (say, from 1 to 100), then all papers falling below some cut-off level could be rejected.
The new pool of papers is then passed back to the judges, and the process is repeated. A concern is that the total number of papers each judge reads must be substantially less than P. The process is stopped when there are only W papers left. These are the winners. Typically for P=100, W=3.
Task is to determine a selection scheme, using a combination of
rank-ordering, numerical scoring, and other methods, by which the final W papers will include only papers from among the "best" 2W papers. (By ""best," we assume that there is an absolute rank-ordering to which all judges would agree.) For example, the top 3 papers found by your method will consist entirely of papers from among the "best" six papers. Among all such methods, the one that requires each judge to read the least number of papers is desired.
Note the possibility of systematic bias in a numerical scoring scheme. For example, for a specific collection of papers, one judge could average 70 points, while another could average 80 points. How would you scale your scheme to accomodate for changes in the contest parameters (P,J, and W)?
Thank you :)
David Rogers
Date: 16 Jun 1996 21:14:42 GMT
Regards Ross Withers
Date: 18 Jun 1996 07:55:45 GMT
modern lp-codes typically use some decomposition of the basis matrix rather than inverting it. A first basic introduction may be found in fletchers "practical optimization", who describes several possible such decompositions. using a qr-decomposition would reduce the rounding errros even more, but since this one has much more fill in, it is not employed in standard lp-solvers. Anyway you must imagine that lp-solvers will work reasonably on a restricted class of not too illconditioned cases, since the algorithm heavily relies on >0 <0-decisions which are unsafe under roundoff. An old trick is to set any number occuring in such decisions which is below machine_eps*condition(basis) to zero, but this clearly is a heuristic which may or may not work. conditon estimators for lr-decompositions are well known, e.g. LAPACK has implemented some.
hope this helps
peter
Date: 20 Jun 1996 00:27:32 GMT
Date: Thu, 20 Jun 1996 12:43:38 GMT
John J. Forrest and Donald Goldfarb, Steepest-edge simplex algorithms for linear programming, Mathematical Programming 57 (1992), pp. 341-374.
That paper has references to the original steepest-edge paper by
Goldfarb and Reid, and the original Devex paper by Harris.
Date: 2 Jul 1996 22:35:59 -0400
I am an engineer investigating water collection in the third
world. Specifically, the queues at water collection points are
my interest (for now). There is sufficient reason to believe
that the arrivals are not Poisson, but dependent in many
instances. After collecting data from queues in Honduras, I
have begun to further explore the mathematical models available.
Although lost in much of the math, it is clear that the Poisson
assumption is critical to most of the models. I would greatly
appreciate the ear (screen) of someone more familiar with
queueing and the math behind it, in hopes that they can
illuminate me to the essentials, or the sources where I may
drink deeply.
Thanks, Bill Randall
Date: 2 Jul 1996 19:06:34 GMT
I checked the FAQ and could find nothing on this topic. My question is whether I can claim that an algorithm can be solved in polynomial time if it is in the form of a linear program. From what I understand the Simplex algorithm is not polynomial time. I heard that there is an algorithm (Ellipsoid?) which can solve all LP's in polynomial time.
If there is no simgal polynomial time algorithm, are there characteristics of LP's which can guarantee polynomial time? I know, for example, that network flow problems can be solved in polynomial time and if a problem can be placed into that form then it can be solved. (my problem cannot).
My problem I have has the following form:
Any help would be appreciated. If there is one algorithm which can solve any LP in polynomial time a reference would be greatly appreciated.
Thanks in advance,
Doug
Date: 2 Jul 1996 21:43:55 -0400
Hope I didn't offend anybody...
Jonathan Eckstein
Date: 5 Jul 96 20:45:06 GMT
There is an additional point to watch for: You must be sure that
the LP is of polynomial size. For example, if you write an NP-hard
problem as an LP, you will find some instances generate LPs
exponentially larger than the original problem description.
David
Date: 7 Jul 1996 23:52:17 GMT
It is even worse than this. It seems to be impossible to write any NP-hard problem as an LP for all sizes of problem, even if you use an exponential number of constraints. The difficulty is that you
do not know all the constraints. For each larger problem size, new
classes of constraints appear. Not only the number of constraints grows exponentially, but the number of classes of constraints grows with problem size. There seems to be no reasonable way to predict the form of the new classes of constraints without a brute-force analysis of the problem polyutope. (This is all predicated on the number of variables of the LP growing only polynomially with problem size.)
A counterexample to my statement above would prove NP==co-NP because it would lead to a polynomial-length optimality proof for your problem.
Date: Thu, 18 Jul 1996 01:45:19 +0000
Date: Thu, 18 Jul 1996 15:24:08 +0100
_Quant. Analysis for Business Decisions_ by Bierman et al. (also Irwin) has a pretty good set of end-of-chapter exercises.
Paul
Date: Fri, 19 Jul 1996 14:59:50 +0200
you are interested in LP problems?
What do you think of the following:
formulate an lp for one period
Therefore either the cheap credit or the expensive one has to be taken.
One possibility seems to be to take only the depreciation in the
objective function, and to note down the price of the investment in the
liquidity constraint.
This technique involves full interest costs for the investment rather
than
half the interest costs (like we normally do as a rough estimate).
The investments will therefore be too low.
What can be done?
Ludger
The simple answer is:'throw away your accounting textbooks'. They lead you into all sorts of nonsense when they start allocating costs in all directions, usually on the basis of the half-baked theories of the current guru. If you are optimising, then only treat _real_ flows of money.
Date: Mon, 22 Jul 1996 14:12:21 GMT
ftp://orion.uwaterloo.ca/pub/henry/teaching/readme.html
The files are also available by anonymous ftp.
I am also looking for new problems AND new projects for the OR course.
Please tell me if there is a site for them and/or if you can email them to me.
Date: 12 Aug 1996 18:05:27 GMT
and need to generate random solutions with all x_i >= 0. I am
currently using a singular value decomposition of A to get a solution but don't know how to properly include the non-negativity
constraint. I believe this is called the feasible set in linear
programming. How do I select random points in the feasible set? Any help or pointers to software that solves this problem would be much appreciated!
Please email any suggestions since this is problem a very simple
question for readers of this group.
Thanks in advance,
F = { x \in \Re^n | Ax = b, x >= 0 }
may be unbounded, and you do not specify a probability distribution (if F was bounded, I might assume you intended a uniform distribution).
In general, I guess you need to specify some density d on random
vectors x \in Re^n. Then I guess you want to generate the points with the distribution d conditioned on x \in F.
I am not sure the solution to this problem is either easy or well
known. Perhaps somebody else will address the solution...
Assistant Professor Jonathan Eckstein
Date: 13 Aug 1996 21:23:06 GMT
Since you didn't specify a distribution for the generated points, I assume you either want them generated uniformly over the polyhedron P = {x : Ax = b, x >= 0} or else you don't care about the distribution.
I'll also take the liberty of assuming the polyhedron is actually a
polytope (i.e., bounded), although some of the methods below would work ok without boundedness, albeit at the loss of uniformity. Last, I'll assume you're interested in sampling the interior of P; the methods below have probability zero of hitting the boundary.
Method 1: This method is mathematically tractable only for problems of
small dimension, but it has the two redeeming features of (a) giving
samples guaranteed to be uniformly distributed and (b) letting me cite an old paper of mine :-) ["Generating Random Points in a Polytope",_Communications in Statistics - Simulation_ 13, 3, 375-396, 1984]. Start by enumerating all the corner points of P. You can do this, among other ways, by trying all possible decompositions of the A matrix into a nonsingular basic submatrix B and whatever is left (N), then solving for
x_B = Binv*b - Binv*N*x_N (where x = (x_B, x_N) is the corresponding decomposition of x and Binv is the inverse of B), setting x_N = 0 for each such decomposition and discarding any where x_B fails to be nonnegative. This gets old geometrically with the number of columns of A. If you live through it, you will also implicitly have a list of edges of P, since they connect pairs of corner points whose corresponding basic submatrices differ
in exactly one column. The procedure in my paper then builds a list of all faces of progressively higher dimensions, computes their barycenters (that part at least is a trivial calculation), and partitions up P into a bunch of simplices with corners at either an original vertex of P or one of the facial barycenters. That's a ton of up-front computing, after which you can generate points pretty quickly by randomly choosing a simplex (with probability in proportion to its volume) and randomly waiting its vertices.
Method 2: Find an initial point x in P, say by selecting a basis submatrix B such that x_N = 0 makes x_B >= 0. (One way to do this is to maximize or minimize the constant zero function subject to Ax = b, x >= 0, which is, per your opening comment, a linear program.) Now randomly generate a direction d in the null space of A and find max {s >= 0 : A(x + s*d) = b, x + s*d >= 0}. Note that s is a scalar here. If s = 0 (meaning the line segment from x in direction d immediately departs P), discard d and try again. Otherwise, generate a scalar t uniformly distributed over the open
interval (0, s), make your next sample point x + t*d, and iterate. This is know as "random walk sampling." Per another one of my papers ("Short-run Characteristics of Samples Drawn by Random Walks", _Communications in Statistics - Simulation_ 14, 2, 473-490, 1985) (wow, two cites in one post!), this produces samples which are uniformly distributed in the long-run (i.e., large samples are uniform) but which may not be uniform in the short run (if P has a funky shape). Of course, if you don't care about uniformity, that's not a problem. You won't sample the boundary with with
this approach, even if you use the closed interval [0, s] when choosing t (since 0 and s will have probability 0 of being used).
Method 2a: Getting a suitable direction d in method 2 might be a pain in the butt. I'd strongly consider finding a basic/nonbasic partition, solving for x_B = Binv*b - Binv*N*x_N, eliminating x_B from the problem and replacing the equation constraints with the inequalities Binv*N*x_N <= Binv*b. The reduced dimension region P' defined by these inequalities and x_N >= 0 has an interior. Find a starting point x' in the interior of P'. (One way is to solve successive linear programs, maximizing each of the components of x_N subject to the aforementioned constraints, then average the solutions.) It's possible that P' has no interior (i.e., P' is of less than full dimension), but I wouldn't worry about it. If it happens, it can be dealt with. Now do random walk sampling, secure in the knowledge that
you'll always be within the interior of P', so *every* direction d is
feasible.
Method 3: Use acceptance-rejection sampling. Get some initial
basic/nonbasic decomposition and stick to it. Successively maximize each nonbasic variable subject to the constraints and use the results to generate a hyperrectangle containing all feasible choices for x_N. Randomly sample that hyperrectangle (uniformly) to get x_N, calculate the corresponding x_B, and accept x iff x_B >= 0. This is arguably the simplest to program. Method 1 is more efficient if the sample size is big enough, since the rejections in method 3 will *eventually* pay for the front-loaded overhead of method 1. Method 2a should be more efficient than method 3, though. I'm not sure about method 2 vs. method 3, since 2 also includes the possibility of rejections. Method 3 is guaranteed to
produce a uniform sample.
Thanks for the opportunity to plug my wares :-). Sadly, I had to go back and pull the papers out of a file, since I'd forgotten the content of the first one.
Paul
Date: Tue, 13 Aug 1996 13:42:18 -0400
Since the question is very natural, I am sure people have thought of it before. In reality, the problem I am looking at is a generalization of LP, but once I have an answer to this question, hopefully
I can generalize it.
Any help would be greatly appreciated.,p>
Thanks a lot
Gabor Pataki
Date: 16 Aug 1996 23:30:02 GMT
Paul
Date: Wed, 21 Aug 1996 18:08:05 GMT
RGV
how OR education reflect the current state of OR art, and how much it is atribute to most spectacular achievements - sort of a self-monument.
For example, many OR classes require manual manipulation with simplex tables, and computing those pivot rows, etc. I am yet to see similar attention to scheduling, gradient
methods or global optimization.
Of course, every science defines certain basics that are the core of all future development - but eventually most of those "basics" get discarded in favor of new emerging challenges. And it seems to me thatmanual pivoting is less intersting in our days than problems that correspond to modern computing challenges.
p.s. this is nothing personal towards pivoting or Prof. Dantzig, of course - just an example of a more general issue
Anyone have experience to use numerical receipt to solve LP problem. Right now I got a C file ie simplx.c, simp1.c, simp2.c and simp2.c. However, I don't know how to make an input.To simplify my problem. I make an example as follow.
Date: Thu, 22 Aug 1996 07:29:23 -0700
there are many elementary implementations of LP solvers available somewhere. If you want one which is using Simplex comes with a nice demo, accepts different formats (the lp-format is just about exactly as you give your example) then consider lp_solve.
If you ever have to solve larger problems, then you may want to look at one of the interior point codes. These codes are listed on and linked to at
http://plato.la.asu.edu/guide.html
This is not a website trying to list everything available, it merely lists exemplary, proven, and recommended codes; typically one or a few per type of problem.
Date: 27 Aug 1996 22:44:56 GMT
I'm not sure if it's a "self-monument" or inertia. There is a strong
temptation to teach a subject the way one learned it, and textbooks
reinforce this by sticking to tried and true formulas.
That notwithstanding, there is a point to pivoting - you
understand the algorithm a bit better, and appreciate the subtleties of
rounding error and numerical precision a bit more, after rolling in the mud
with a problem or two. I don't pivot in my MBA classes - in fact, I don't
teach the algorithm. Those students need to formulate problems and
interpret solutions. In my OR class, though, we crunch problems by hand to
learn the algorithm. Computer-assisted computation is always waiting in
the next life.
Paul
Date: Fri, 13 Sep 1996 08:40:37 +0100
In terms of accuracy, speed, memory intensity, etc.
Thanks in advance, Anwar
Date: 19 Sep 1996 02:28:16 GMT
Thanks in advance
Date: 19 Sep 1996 15:49:50 GMT
Thank you very much.
Date: 16 Sep 1996 19:35:11 GMT
I am working on a project which requires testing of "linear inequation
set"(forgive my limited terminology) containment. I am seeking help
from any Linear Programming Guru in the net....
The problem is as follows. A LIS (shorthand for linear inequation set)
is a set of linear (in)equations combined by "AND", "OR", "NOT"
operators.
((x+y>=0) AND (y=z)) OR (y<3)
The solution can be either in the Integer domain or the Real (but
dense totally ordered) domain.
(Note: there is no "NOT", since "NOT" can always be pushed into the
">", "=", or "<" operators, right?)
Thanks in advance.
Ben
You are going to face two immediate difficulties using mathematical
programming. The first is that strong inequalities are out; you'll need to
work exclusively with weak inequalities. One possible approach is to
"weaken" strong inequalities and then penalize their satisfaction as
equalities in the objective function. The second difficulty is that
whereas the AND operator is easy (listing a bunch of constraints in a MP
model enforces their conjunction), OR (disjunction) is a problem. You
handle disjunction by adding 0-1 variables to indicate which terms among a
disjunction are being satisfied, and wind up with an integer program (which
is part of the NP-completeness issue Mike Hennebry raises in his response).
I can show you sample MP formulations for your examples below, if that will
help. Everything will be in the real domain unless noted otherwise.
To handle the disjunction, I'll introduce a 0-1 variable a, which will be 0
if we enforce y < z and 1 if we enforce the alternative. (Note that,
regardless of the value of a, it might in general be possible for both
terms of the disjunction to be true.) To the model is now:
What's left is to deal with the strict inequalities. Introduce a
nonnegative real variable b and change the first and third inequalities to:
y + b <= 0
y + b <= z + Ma.
Now solve the problem
Date: 17 Sep 1996 10:46:36 -0500
Date: Mon, 16 Sep 1996 13:10:41 -0500
x1/(x1 + x2) >= 3/4.
If x1 and x2 are >= 0 it reduces to:
x1 - 3*x2 >= 0
which works fine.
My situation is that x1 and x2 should be modeled as unconstrained, which
means that the constraint above does not work correctly if one or more
of the variables is negative.
As a workaround in the meantime I've written a NLP constraint:
abs(x1) - 3*abs(x2) >= 0
which works the way I want, but I'd rather not have it be a NLP.
Does anyone know how I might write a linear (or 0-1) constraint(s) that
does the same thing as the NLP constraint above.
Thanks.
Date: Mon, 23 Sep 1996 15:09:33 +0100
James Tebboth
Date: Thu, 26 Sep 1996 22:43:38 +0200
Given is a (pretty large) set of n objects. Of those objects some can
carry information and others can only represent references to objects.
Objects can also be clustered together.
Now I want to map this set of objects to a set of organized graphical
primitives, taking into consideration that the display should be
'well-organized'. This would e.g. include not having objects intersect
each other, assigning coordinates so that references would intersect
each other as little as possible.
Attempt/guess at a strategy for a solution:
The first idea that came to mind was to solve this with linear/quadratic
programming.
But intuitively I get the feeling that it would be overkill to use such
a general method, I need to solve this problem a dozen times per sec or
so. Even though I'm currently only working with sets consisting of 10 <=
n <= 100 objects or so, there will be a *lot* of constraints - for all
the possible distances between all the objects in the set (n^2) - which
will have to be satisfied.
There are also several, <= n, distances to be minimized simultaenously.
Question:
Could anybody tell me if this is possible at all? It seems to me that this problem must have been investigated before - does anybody know?
Thankful for any help
Regards
/johan
Date: 26 Sep 1996 23:07:12 -0400
I can also make available some C++ code and documentation illustrating how these ideas apply to managing a layout of nested rectangular regions which can change dynamically. This is the type of algorithm one might want in window management where refreshing a changed window can be expensive. You want only those windows (portions of windows) that are affected by the change to be updated.
Your problem partially fits into this scheme in that the rectangles might be the bounding boxes for your objects. Although my code is for 2D layout, it should be easy enough to extend it to 3D.
Dave Eberly
Date: Thu, 26 Sep 1996 14:36:22 GMT
Please e-mail. I will post a summary if replies warrant.
Thanks in advance.
Robin Becker
Date: 23 Sep 1996 10:36:54 -0500
Mike hennebry@plains.NoDak.edu
Date: 9 Oct 1996 12:13:20 GMT
J E Beasley
Published by Oxford University Press 1996 (ISBN 0 19 853856 1)
Linear and integer programming are mathematical techniques that
are concerned with optimization, that is with finding the best
possible answer to a problem. They are often associated with the
wider field of operations research. They have been studied and
researched since the late 1940s and elements of them are now taught
in undergraduate and graduate programmes in mathematics/operations
research worldwide.
In recent years, after the advent of interior point methods, there
has been an explosion of research into linear programming, as
well as further steady advances in integer programming. This research
has been reported, as one would expect, piece by piece in the
research literature, i.e. at conferences and in journals. The
reason for assembling this book was to bring together in a single
text an accessible exposition of these advances.
With contributions from acknowledged experts in their field
this book deals with:
For more details, including a full list of contents, see
http://mscmga.ms.ic.ac.uk/jeb/book/book.html
Date: 3 Oct 1996 19:08:43 GMT
If anyone knows of an actual method for generating hard SAT problems that they
could let me have a copy of/give me details about I'd be most grateful
Cheers
Andrew
Date: Tue, 15 Oct 1996 15:01:33 +0200
We use a crude mps format parser written in C to read the mps
file and store the constraint matrix data in a doubly linked list.
We generate text commands for autocad to display the nonzero
location with a cross sign. By putting the non zeroes at
appropriate multiples of graphic units, we can infer from
the nonzero sign coordinates the serial number of the row and
columnn. This was satisfactory for our purposes, although not as
functional as oslgui for example. What we like is the possibility
of expansion. For example we are programming the commands to
display the nonzero structure of the matrix times its transpose...
Etienne Loute
Date: Tue, 15 Oct 1996 15:01:33 +0200
We use a crude mps format parser written in C to read the mps
file and store the constraint matrix data in a doubly linked list.
We generate text commands for autocad to display the nonzero
location with a cross sign. By putting the non zeroes at
appropriate multiples of graphic units, we can infer from
the nonzero sign coordinates the serial number of the row and
columnn. This was satisfactory for our purposes, although not as
functional as oslgui for example. What we like is the possibility
of expansion. For example we are programming the commands to
display the nonzero structure of the matrix times its transpose...
Etienne Loute
Date: Wed, 30 Oct 1996 17:09:55 +0100
I would like to test some interior point methods (Todd, Liao) with porblems of
the Netlib-Testset.
Always is for this class of algorithms given a primal Problem (P) in standard form,
and any interior point x_0-- so this is my little problem.
Everything I know is finding a point with primal-dual-IP-methods OR Using a big-M method, wich is called to be not good enough for solving sparse-matrix-problems.
I really would be happy for some helpful comments!
Thanks ARMIN SAAGE
Date: Mon, 04 Nov 1996 10:28:56 -0500
Date: 7 Nov 1996 15:53:50 GMT
Morton O'Kelly
okelly+@osu.edu
Date: Thu, 7 Nov 1996 15:02:25 -0500
Turkay M. and Grossmann I.E., "Disjunctive Programming Techniques for
the Optimization of Process Systems with Discontinuous Investment
Costs-Multiple Size Regions", Industrial & Engineering Chemistry
Research, vol:35, no:8, pp2611-2623 (1996).
The paper describes conventional techniques such as direct approach (use
od if then statements), smooth approximation, big-M formulation with
binary variables (which corresponds to what you're looking for) and
discusses two new techniques based on disjunctive programming. The
approaches are valid both for linear and nonlinear piece wise cost
functions.
Metin Turkay
Date: 7 Nov 1996 21:32:00 GMT
Assuming that your model is otherwise a linear program, if your piecewise
linear function represents a diseconomy of scale, you still have an LP; if
it represents an economy of scale, you get an IP.
Suppose the argument of your function is x and the breakpoints occur at a0
< a1 < ... < an. For starters, you need to introduce divisible variables
x1, ..., xn such that
x = x_1 + ... + x_n
What comes next depends on the "cost" function f(x).
Treat x_j as the amount of the j-th interval used, constrain it 0 <= x_j <=
a_j - a_j-1, and you're set. If f(x) appears in the objective function,
the solution will automatically fill in from the left (exhaust interval j
before using interval j+1). If f(x) does not appear as part of the
objective function, you might wind up with the right value for x but
inefficient choices for the x_j, in which case you can correct the x_j's
manually.
Let f(x) = b_j + m_j*x for a_j-1 <= x <= a_j. (I'm being intentionally
sloppy about whether the domain intervals are closed on the left or on the
right.) Introduce 0-1 variables y_1, ..., y_n, constrained such that
y_1 + ... + y_n = 1,
and constrain the x_j's so that a_j-1 * y_j <= x_j <= a_j * y_j.
The cost of x is sum {j=1 ... n} (b_j*y_j + m_j*x_j).
This is potentially inaccurate if f is discontinuous AND it takes the
higher of the two possible values at some jump points AND the optimal
solution you get picks a value of x exactly equal to such a jump point. In
that case, my suggestion is to fudge x by a tiny amount.
There are other ways to formulate these, but as far as I know you need the
equivalent of a binary variable for each domain interval (except Case I),
so I suspect this approach is about as efficient as it gets. The
constraint on the sum of the binary variables is a Type 1 SOS constraint,
which some solvers can exploit. Williams poses a construction with the y's
replaced by divisible variables that satisfy a Type 2 SOS constraint, but
my impression is that this just moves the binary variables from an explicit
position in the model to an implicit position in the solution process.
-- Paul
Date: 8 Nov 1996 20:35:39 GMT
Hope this helps.
Frida.
Date: Thu, 07 Nov 1996 22:17:23 +1000
Hi all,
I have one problem which looks very nice but I am not sure if it
has nice solution.
Let a = [1 p q r s]', //where ' means transpose
b = [1 u v w z]'
and A = a*a';
Is there anu "shortcut" to solve the system
A*x = b;
i.e is it possible to solve it with less operations than using
Gauss' (or some even more effective) procedure.
Date: Tue, 12 Nov 1996 10:49:08 +0000
James Tebboth
Date: Wed, 13 Nov 1996 09:56:46 +0000
Bob Daniel
To identify the model in cases where the function has one input and
one output you can use "broken stick" or "segmented" regression. What
Ken Cogger (School of Business, U. Kansas) and I have been doing is to
use an adaptive procedure to identify the model. It is then possible
to test to see if the complexity of that model is justified or if a
simpler model will do. What happens then is that you represent the
max of two (continuous, piecewise linear) functions y1 and y2 as y1 +
(y2-y1)*z where z is 1 or 0 depending on whether y2 > y1 or not. Both
y1 and the (y2-y1)*z are *continuous*. This is much better than using
z's to indicate where a given piece is active in a piecewise linear
function because then you don't necessarily have continuity.
Finally, for testing, you can test whether b is 0 in
f= y2 + b * (y2 - y1)* z.
We have a paper in preparation, so if you email me I can give you the
ftp coordinates of the draft, or maybe the final version if it is ready.
Date: Tue, 12 Nov 1996 15:38:51 +0200
Unless u=p, v=q, w=r and z=s, in which case it has infinitely many
solutions, your system has no solution.
Note that your A matrix is a rank one matrix (external product
of a by itself).
Solving Ax=b means trying to express b in the column space of A.
This column space amounts to the vectors colinear to your a vector.
If your b vector is not colinear to a, your system has no solution.
Since you normalize a and b by imposing a 1 as first component,
it means b identical to a. Solutions are then for example [1 0 0 0 0],
[0 1/p 0 0 0], [0 0 1/q 0 0] ....
Many thank and in hope, Greg Holba
Date: 16 Dec 1996 08:38:21 GMT
G'day:
Those of you looking for exciting LP codes for teaching the simplex method
may wish to have a look at the very light WWW document I have just put
http://www.maths.mu.oz.au/~moshe/lp/
And while you are over there have a look at the exciting interactive DP
codes located at
http://www.maths.mu.oz.au/~moshe/dp/DPstudio.html
Have fun! (You'll need Netscape 3)
Moshe Sniedovich
Crawl back to front page.
From: (null)
From: vavasis@parc.xerox.com (Stephen Vavasis)
Newsgroups: sci.op-research
Subject: Re: backtracking in interior-point alg.
Date: 21 Jun 1995 17:58:45 GMT
Organization: Xerox PARC
Lines: 31
Distribution: world
Message-ID: <3s9mkl$d35@news.parc.xerox.com>
References: <3rgjdj$b67@net.auckland.ac.nz>
Keywords: interior-point, primal-dual, semidef. progr
A*D*A'*x = A*D*b
where A is a rectangular matrix, A' is its transpose, and D
is a diagonal positive definite but ill-conditioned matrix, b
is given, and x is unknown.
http://www.cs.cornell.edu/Info/People/vavasis/vavasis.html).
-- Steve Vavasis
From: Irv Lustig
Subject: what are the largest LP's solved?
To: lct6v@kelvin.seas.Virginia.EDU
>Dear OR colleagues,
>
>I am a research student that is working on a sub-problem that
>can be formulated as a linear program with the following
>summary characterisics:
>
>N+1 + n*n + N*(N-1)/2 continuous variables
>1+ n*(1+N) + 3*(N*N-1)/2 constraints.
>
>I have concern that this problem might not be computationally
>feasible since I am dealing with LP the sizes of
>
>n = 5000 to 25000
>N= 300 to 500.
>
>My first question to all is: (1) what are the largest sized
>LP9s that have been solved?
>
**Stuff deleted**
author = "R. E. Bixby and J. W. Gregory and I. J. Lustig and R. E. Marsten
and D. F. Shanno",
title = "Very large--scale linear programming~: {A} case study in
combining interior point and simplex methods",
journal = "Operations Research",
volume = "40",
year = "1992",
pages = "885--897"
}
Having a good presolve routine helps enormously. I don't think I've seen a
problem that we've solved with a direct method that has more than 300,000
constraints, but I could be mistaken, and I'm not privy to all of the problems
that are routinely solved by CPLEX on a daily basis.
> problem constraints: (2) what are the largest assignment solved?
Director of Numerical Optimization
CPLEX Optimization, Inc. http://www.cplex.com/
irv@dizzy.cplex.com
From: barr@seas.smu.edu (Richard S. Barr)
Subject: what are the largest LP's solved?
If the entire problem is a network, you can solve quite large models.
One of the largest on-going applications for LPs is at the U.S. Treasury
Department, of all places. It is a descendant of a system that I
originally wrote in the 1970s where transportation problems with 10s of
thousands of constraints and 20+ million variables were solved on a Univac 1108
(with a whopping 128K words of RAM). These types of problems are routinely
solved
today (more quickly of course) with an up-to-date primal-simplex network solver.
For details, see:
From: Zhi-Long Chen
Subject: Large Scale Sparse LP
I am using CPLEX callable functions to solve an LP problem with
564 rows and 20437 columns (each column contains 3 nonzeros).
If I use the function "optimize()", the result is "Segmentation
Fault (core dumped)". While, if I use the barrier method "baropt()",
it gets an optimal solution after about 28 CPU seconds.
I wonder if this size is too big for the Simplex method function
"optimize()". Also, what leads to the segmentation fault (inside
the function "optimize()")?
Another puzzling thing is that when I use "baropt()" to solve
an LP with the similar structure to the above one but with
about 40k columns, it does solve the LP, but the status value
inside the "solution()" is 42. There are totally 41 possible
status values (1, 2, ..., 41) described in the CPLEX manual,
then what does 42 refer to?
Any help will be greatly appreciated.
Zhi-Long Chen
Department of Civil Engineering & Operattions Research
Princeton University
Princeton, NJ 08544, USA
------------------------------
Date: Wed, 19 Jul 1995 13:07:19 GMT
From: Irv Lustig
Subject: Large Scale Sparse LP
To: zhichen@phoenix.princeton.edu
Zhi-Long Chen
>I am using CPLEX callable functions to solve an LP problem with
>564 rows and 20437 columns (each column contains 3 nonzeros).
>If I use the function "optimize()", the result is "Segmentation
>Fault (core dumped)". While, if I use the barrier method "baropt()",
>it gets an optimal solution after about 28 CPU seconds.
>
You might be clobbering memory, and the error is getting caught
during your call to optimize() but not baropt(). You should use
the checkprob() facility to check your arguments to loadprob().
You should also use a memory debugger, like Purify or Insight,
or the public domain malloclib to determine where you might be clobbering
memory.
>I wonder if this size is too big for the Simplex method function
>"optimize()". Also, what leads to the segmentation fault (inside
>the function "optimize()")?
>
No, the simplex method within CPLEX has handled problems with over 100,000
constraints and millions of variables. It's not a problem with
optimize(). The segmentation fault is most likely due to you clobbering
memory somewhere.
>Another puzzling thing is that when I use "baropt()" to solve
>an LP with the similar structure to the above one but with
>about 40k columns, it does solve the LP, but the status value
>inside the "solution()" is 42. There are totally 41 possible
>status values (1, 2, ..., 41) described in the CPLEX manual,
>then what does 42 refer to?
>
That was a new status added after the manual was printed. It means that
the barrier method got into numerical difficulties (possibly due to
high rank deficiency in your constraint matrix), but returned the
best solution found anyway. If you are getting this return code, it's
worth it to submit the problem to me and I'll take a look at it.
To do this, place a call to mpswrite() just before your baropt()
call, and contact me directly for directions on how to submit your MPS
file. You might also try using the interactive optimizer to read
in the MPS file to see what happens. That might reveal your memory
clobbering bug.
-Irv Lustig irv@dizzy.cplex.com
Director of Numerical Optimization
CPLEX Optimization, Inc. http://www.cplex.com/
------------------------------
From: naylor@mti.sgi.com (William Clark Naylor)
Subject: [Q]: approximate linear programming polytopes
When solving combinatorial optimization problems using linear programming, it is customary to use a constraint set which exactly bounds the polytope for the optimization problem.
From: dpw@watson.ibm.com
Subject: [Q]: approximate linear programming polytopes
In article <3vj8td$37d@chronicle.mti.sgi.com> naylor@mti.sgi.com (William Clark
Naylor) writes: .......
From: bpatnaik@MCS.COM (Biswajit Patnaik)
Subject: How can this special case of LP be exploited?
I have a problem where I am trying to maximize the utilization of trucks.
The LP formulation looks something like this:
Date: Mon, 7 Aug 1995 13:26:00 GMT
From: Irv Lustig <irv@dizzy.cplex.com>
Subject: How can this special case of LP be exploited?
To: bpatnaik@MCS.COM,irv
bpatnaik@MCS.COM (Biswajit Patnaik) wrote: ......
From: gt1086c@prism.gatech.edu (Gregory Glockner)
Subject: How can this special case of LP be exploited?
bpatnaik@MCS.COM (Biswajit Patnaik) writes: ....
From: jampel@cs.city.ac.uk (Michael Jampel)
Subject: Mastermind as a linear program
From: bobs@mathworks.com (Bob Silverman)
Subject: Random Points in Feasible Space
Does anyone know of an effective algorithm which will find uniformly
distributed random points in the feasible space of an LP? You
may assume that there are upper bound constraints on all variables
so that the feasible space is not unbounded. Also, the number of
variables is very small, i.e. less than 15.
One could find the minimal convex hull, then generate random points
by rejection, but the success rate would depend on the volume of the
feasible space relative to the volume of the hypercube given by the
upper/lower bounds on each variable.
I don't know how practical this approach would be.
The MathWorks Inc.
24 Prime Park Way
Natick, MA
From: jpc@a.cs.okstate.edu (John Chandler)
Subject: Random Points in Feasible Space
In article <41veu1$d8o@charm.magnus.acs.ohio-state.edu>,
Duane F Marble <dmarble@magnus.acs.ohio-state.edu> wrote:
jpc@a.cs.okstate.edu
From: bobs@mathworks.com (Bob Silverman)
Subject: Random Points in Feasible Space
In article <41vk5u$1kpj@bubba.ucc.okstate.edu>,
John Chandler <jpc@a.cs.okstate.edu> wrote:
The MathWorks Inc.
24 Prime Park Way
Natick, MA
From: jrbirge@engin.umich.edu (John R Birge)
Subject: Random Points in Feasible Space
I think Lovasz showed that this is an NP-complete problem even if you try to obtain some form of $\epsilon$ approximation. (For example, if you can enclose the LP region in a hypercube then the expected volume of the LP feasible region becomes small exponentially fast in the dimension $n$.) There are some results from Frieze, Kannan and others (including Lovasz) that give rapid mixing results that approximately obtain a uniform distribution with
some $\alpha$ confidence level. So, you can obtain it with some probability but not exactly.
From: eppstein@wormwood.ics.uci.edu (David Eppstein)
Subject: Random Points in Feasible Space
If you are willing to take a distribution arbitrarily close to but not
exactly uniform, and modulo some boundary and discretization effects,
this is possible even when the dimension is unbounded. The technique is (very roughly) to take a random walk inside the polytope (by generating steps and testing to make sure each one stays inside) for long enough that you don't know where you are any more... The number of steps you need can be shown to be a (moderate exponent) polynomial in the dimension (and in the accuracy with which you wish to approximate uniformity).
From: Erik Rolland <erik@ucrac1.ucr.edu>
Subject: Random Points in Feasible Space
If you are able to distribute the points to the extent that they
accurately map the boundary of the "efficient frontier", then whatever
approach you have found should enable us to solve problems (to
optimality) which we currently do not know how to deal with (such as
non-linear, non-convex problems). Thus, the chance of finding a
polynomial algorithm for your "point distribution" is very small (unless P=NP)!!!
From: Erik Rolland <erik@ucrac1.ucr.edu>
Subject: Random Points in Feasible Space
If you are able to distribute the points to the extent that they
accurately map the boundary of the "efficient frontier", then whatever
approach you have found should enable us to solve problems (to
optimality) which we currently do not know how to deal with (such as
non-linear, non-convex problems). Thus, the chance of finding a
polynomial algorithm for your "point distribution" is very small (unless P=NP)!!!
From: dpw@watson.ibm.com
Subject: Random Points in Feasible Space
There has been some amount of work done on this problem and related ones in theoretical computer science. I am unfortunately not very familiar with the details, but it works for certain well defined
convex bodies, and the basic idea is to take a random walk inside
the body for a certain number of steps. The walk is defined either
by discretizing the space (i.e. introducing lattice points) or by
starting at the current point, choosing a point uniformly within a ball
of a certain radius, moving to the point if it is inside the body,
otherwise staying at the current point. The papers in this area
show that these walks converge to an almost uniform distribution on
the interior of the body if the walk is sufficiently long (in this case,
a polynomial number of steps, poly in the number of dimensions) and
if the body obeys certain properties.
From: alain.michiels@electrabel.be (Alain Michiels)
Subject: Embedded LP's
Hi,
alain.michiels@electrabel.be
From: ez062245@dale.ucdavis.edu (Hakan Basagaoglu)
Subject: rejected pivots
Hi out there,
From: loute@core.ucl.ac.be (Etienne Loute)
Subject: rejected pivots
In article <43qnsd$30g@mark.ucdavis.edu>
ez062245@dale.ucdavis.edu (Hakan Basagaoglu) wrote ....
CORE&QANT/UCL & ESPO/FUSL
eloute@core.ucl.ac.be
el@fusl.ac.be
From: jwg@ceres.cray.com (John Gregory)
Subject: rejected pivots
Another cause, I think, could be scaling of a different kind.
Models containing inaccurate data, for instance,
Applications Div Cray Research, Inc.
Eagan, MN 55121
612-683-3673
612-683-3099 (fax)
jwg@cray.com or ashbury@skypoint.com
Thought for today:
I used to get high on life but lately I've built up a resistance.
From: Peter Lindstrom <lindstro@cc.gatech.edu>
Subject: LP Problem?
Is Bb >= 0, where B is a known matrix, b is an unknown vector, and Bb is yet another vector, easiest solved as an LP feasability problem (is it even an LP feasability problem?), or is there a quicker way of solving this? I've attempted to write this in standard LP form:
From: "J.T. Linderoth" <jeff@akula.isye.gatech.edu>
Subject: LP Problem?
st Bb >=0
b FREE
-Jeff
From: mjs@hubcap.clemson.edu (M. J. Saltzman)
Subject: LP Problem?
"J.T. Linderoth"
Clemson University Math Sciences
mjs@clemson.edu
From: raghava@advtech.uswest.com (S. Raghavan)
Subject: LP Problem?
In article <mjs.813897379@hubcap>, mjs@hubcap.clemson.edu (M. J. Saltzman) wrote: ...
y >= 0 and y ne 0
s.t. yB = 0
sum_i y_i = 1
y >= 0
If this problem is feasible the system Bx > 0 has no feasible solution,
and if this problem is infeasible the system Bx > 0 has a feasible
solution.
U S WEST Advanced Technologies
4001 Discovery Drive, Suite 280
Boulder, CO 80303
phone: 1-303-541-7101
fax: 1-303-541-6003
From: mjs@hubcap.clemson.edu (M. J. Saltzman)
Subject: LP Problem?
raghava@advtech.uswest.com (S. Raghavan) writes:
Clemson University Math Sciences
mjs@clemson.edu
From: borges@fiskforsk.norut.no (Boerge Soleng)
Subject: Lp model for optimal productmix - can anyone help?
Hello!
Research Scientist
Norwegian Institute of fisheries and aquaculture
Boerge Soleng, borges@fiskforsk.norut.no
From: John De Beer & Mona Baumgartel <johnmona@cts.com>
Subject: Lp model for optimal productmix - can anyone help?
To: borges@fiskforsk.norut.no
John De Beer
(johnmona@cts.com) OR (73554.165@compuserve.com)
From: harmeier@davinci (Paul Harmeier)
Subject: Norwegian Fish Processing Plant
I believe the best approach to this problem would be the mode approach as shown below:
From: eloute@core.ucl.ac.be (Etienne Loute)
Subject: Any good D/W implementation out there?
In article <frangio-2211952156160001@frangioni.di.unipi.it>,
frangio@di.unipi.it (Antonio Frangioni) wrote: ...
From: marco@moc.math.nat.tu-bs.de (Marco Luebbecke)
Subject: Q: Simplex Enumeration Tree
Dear OR-Community,
Marco Luebbecke
Department of Mathematical Optimization
Technical University of Braunschweig, Germany
Pockelsstrasse 14
D-38106 Braunschweig
Germany
Email: on.mluebbecke@zib-berlin.de
http://moa.math.nat.tu-bs.de/~marco
Newsgroups: sci.op-research
Subject: Help with linear programing
Date: Mon, 25 Dec 1995 08:50:05 +0100
Organization: Faculdade de Ciencias da Universidade de Lisboa
Lines: 61
Message-ID:
Thanks in Advance
From: tqsan@netvision.net.il
Subject: Linear Program. in the petroche. Industry.
Dear Group's Member
Qaulity Assurance Manager
CQE
From: lprince@aol.com (Lprince)
Subject: Linear Program. in the petroche. Industry.
I can recommend a company called Exsys Systems Software out of
Albuquerque, NM USA.
CC&L Research Associates
Jacsonville, FL USA
From: abaldoni@csr.unibo.it (Alessandro Baldoni mat.1010)
Subject: Q: Revised Simplex & Reinversion
I am a student in Computer Science and I'm trying to implement the
Revised Simplex Method in FORTRAN with sparse matrices.
Sorry for my bad english.
From: jeroen Jurgen Dirks <jeroend@tor.numetrix.com>
Subject: Q: Revised Simplex & Reinversion
To: abaldoni@csr.unibo.it
Alessandro Baldoni mat.1010 wrote:
From: jshaw7@ibm.net
Subject: Simplex Method (where did the name come from)
In <1996Feb14.111801.114013@kuhub.cc.ukans.edu>, "Stephen F. Bush"
From: "Stephen F. Bush" <sbush@tisl.ukans.edu>
Subject: Simplex Method (where did the name come from)
I am curious about what the name "simplex" refers to in the
Simplex Method. Is it refering to the geometric simplex shape,
or is there another meaning for the name ?
From: marco@moc.math.nat.tu-bs.de
Subject: Simplex Method (where did the name come from)
G.B. Danzig's "Linear Programming" contains a chapter about "The Simplex interpretation of the Simplex Method" (hope that was the title...)
Department of Mathematical Optimization
Technical University of Braunschweig
Pockelsstrasse 14
D-38106 Braunschweig
Germany
Email: on.mluebbecke@zib-berlin.de
WWW: http://moa.math.nat.tu-bs.de/~marco
From: open58@redestb.es (OPEN58)
Subject: How figure out conflicting constraints in unfeasible Linear Program
When I get that a Linear Programming problem is unfeasible, how can I tell which constraints are preventing it from getting a feasible
solution?
From: rmg@vnet.ibm.com (Richard M. Gabrielson)
Subject: How figure out conflicting constraints in unfeasible Linear Program
The short answer is that the constraints preventing feasibility are
the ones which correspond to nonzero values in the dual solution of
the Phase 1 problem.
From: mhanke@isis.wu-wien.ac.at (Michael Hanke)
Subject: How figure out conflicting constraints in unfeasible Linear Program
In article <4h4kin$p9j@minerva.ibernet.es>, open58@redestb.es (OPEN58) says:
Michael
From: chinneck@halley.sce.carleton.ca (John Chinneck)
Subject: How figure out conflicting constraints in unfeasible Linear Program
open58@redestb.es (OPEN58) writes ...:
From: rmg@vnet.ibm.com (Richard M. Gabrielson)
Subject: How figure out conflicting constraints in unfeasible Linear Program
In a private note Harvey Greenberg writes:
From: yan-dicky@cs.yale.edu (Dicky Yan)
Subject: How figure out conflicting constraints in unfeasible Linear Program
In article <4h4kin$p9j@minerva.ibernet.es> open58@redestb.es (OPEN58) writes: ...
From: metalman@alpha.c2.org
Subject: Minimizin waste tube. Can you make a LP-model?
Dear reader,
From: mgutterman@aol.com (MGutterman)
Subject: Minimizin waste tube. Can you make a LP-model?
Probably requires integer programming.
From: hwolkowi@orion.math.uwaterloo.ca (Henry Wolkowicz)
Subject: Minimizin waste tube. Can you make a LP-model?
For the following problem, you may want to look up the 'stock cutting'
problem, see e.g. the book on linear programming by V. Chvatal. Another
related problem is the airline crew scheduling problem. However, Chvatal
describes the 'column generation' approach for this LP. The columns are
generated using a knapsack problem model.
From: Bart Knaack <bknaack@win.tue.nl>
Subject: constraint solving Question
Hello all,
Ph.D-student Computer science
EUT (Eindhoven University of Technology)
Date: Tue, 12 Mar 1996 15:07:29 -0500
From: "Jeroen J. Dirks" <jeroend@tor.numetrix.com>
Subject: Have you ever used stochastic LP?
From: Armin Saage <asaage@wmpi00.math.uni-wuppertal.de>
Subject: Looking for an ineterior-starting/point
Hi,
From: D.K.Smith@exeter.ac.uk
Subject: The hundred percent rule
Please can anyone point me in the direction of a reference (book or paper) to what I have seen called "the hundred percent rule" in linear programming. In case you know it as something else, the essence is as follows:
David Smith
From: Henry Wolkowicz <hwolkowi>
Subject: The hundred percent rule
To: D.K.Smith@exeter.ac.uk
From: Marco Zaffalon <zaffalon@vmimat.mat.unimi.it>
Subject: Ax=b, Tx=z ==> ?
From: Philippe Refalo <phil>
Subject: Ax=b, Tx=z ==> ?
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: Ax=b, Tx=z ==> ?
From: Louis Bronne <bronne@montefiore.ulg.ac.be>
Subject: Linear programming polynomial algorithm
Can anybody tell me where to find information (articles, book, ...)
about the polynomial algorithm to linear programming discovered
in the late 70s ?
E-mail: bronne@montefiore.ulg.ac.be
URL: http://www.montefiore.ulg.ac.be/cgi-bin-ulg/bronne
From: mjs@hubcap.clemson.edu (M. J. Saltzman)
Subject: Linear programming polynomial algorithm
Louis Bronne
Clemson University Math Sciences
mjs@clemson.edu
From: Mark <mark@uta.geo.orst.edu>
Subject: Linear programming polynomial algorithm
To: bronne@montefiore.ulg.ac.be
That other guy that answered had a lot of good references. The text book "Linear and Nonlinear Programming" by Sofer and Nash has a good discussion of Khachiyan's 1979 ellipsoid method and a few different interior point algorithms which are polynomial (and better).
From: hennebry@plains.nodak.edu (Michael J. Hennebry)
Subject: Linear programming polynomial algorithm
Ivanova recommends not getting in front of Delenn.
From: vavasis@cs.cornell.edu (Stephen Vavasis)
Subject: Linear programming polynomial algorithm
The ellipsoid algorithm for convex programming is generally credited
to Yudin and Nemirovsky [1976], although some of the ideas appeared in Shor [1970]. You can read about the method in the book
From: mjs@hubcap.clemson.edu (M. J. Saltzman)
Subject: Linear programming polynomial algorithm
hennebry@plains.nodak.edu (Michael J. Hennebry) writes ...:
Clemson University Math Sciences
mjs@clemson.edu
From: rdsilverman@qed.com
Subject: Linear programming polynomial algorithm
From: hennebry@plains.nodak.edu (Michael J. Hennebry)
Subject: Linear programming polynomial algorithm
Ivanova recommends not getting in front of Delenn.
From: Dino Ahr <Dino.Ahr@gmd.de>
Subject: Linear programming polynomial algorithm
To: bronne@montefiore.ulg.ac.be
Hi,
From: bandrew@inyanga.cs.wits.ac.za (Brynn Andrew)
Subject: Convex Hull Question
Does anyone know of any way to compute the convex hull of a four
dimensional iris data set, using the simplex method alone? I have thought of using varients, but do not know how to convert the set of points into a simplex tableau.
Brynn
From: "David C. Rogers" <webmaster@enchantedmtn.com>
Subject: LP or PERT/CPM problem
I am an MBA student in an accelerated Mgt Science course. Having covered only basic LP (simplex method) and queing theory I have been presented with the following bonus question. Since tutors are very scarce in summer, and my business clients disagree or don't know how to proceed on this one, I greatly appreciate any insights, etc.
Olean, NY
From: hrnz@chch.planet.org.nz (Harness Racing NZ)
Subject: computational rounding problems
I'm an OR/computer science student and have written a computational engine for the simplex method but despite putting an inversion algorithm in I'm still getting rounds problems - can anyone point me in the right direction ie advise on techiques or a text that will help in sorting out these compuational rounding type problems errors.
e-mail: ross@hrnz.co.nz
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: computational rounding problems
In article <4q1tg2$gj9@sirius.plain.co.nz>, hrnz@chch.planet.org.nz (Harness Racing NZ) writes: ...
From: logic101@step.polymtl.ca (Mostafa Modirrousta)
Subject: Simplex Pricing Methods
As indicated in CPLEX Manual (ver. 3.0), several options are available for pricing, e.g. DEVEX, Steepest-edge. I`m looking for thorough and comprehensible references on any of these methods.
Any pointer is welcome.
From: Irv Lustig <irv@dizzy.cplex.com>
Subject: Simplex Pricing Methods
To: Mostafa Modirrousta <logic101@step.polymtl.ca>
The definitive paper on steepest edge methods is
From: wrandall@freenet.vcu.edu
Subject: Non-Poisson Queueing Problem
To Op.Researchers:
From: doug@parallel.ee.binghamton.edu (Doug Summerville)
Subject: Polynomial Time Algorithm for LP
Hi All,
From: jeckstei@rutcor.rutgers.edu (Jonathan Eckstein)
Subject: Polynomial Time Algorithm for LP
There are many polynomial time algorithms for general LP. Ellipsoid was the first, but it has been joined by a variety of
barrier-function-based methods, starting with Karmarkar's. Some of these barrier methods are very good in practice, although the worst case complexity bounds tend to be very loose and not reflective of real performance.
From: mitchell@cs.toronto.edu (David G. Mitchell)
Subject: Polynomial Time Algorithm for LP
As has already been mentioned, LPs can be solved in polynomial time.
From: naylor@synopsys.com (William Naylor)
Subject: LP formulation of NP-hard problems
In article .... David G. Mitchell ...wrote:
From: Roland Maerivoet <roland.maerivoet@innet.be>
Subject: Looking for LP-problems
As a teacher of OR at college-level I am looking for
more LP problems to be solved by my students; my 'reservoir'
is running low...
So if anyone could send me refences of boofs with lots of LP
problems (or send me the problems themselves) I would be
very thankful.
From: Bob Daniel <rcd@dash.co.uk>
Subject: Looking for LP-problems
H.P. Williams, Model Building in Mathematical Programming 3rd edition revised. Wiley is a good source (with answers too!).
From: rubin@msu.edu (Paul A. Rubin)
Subject: Looking for LP-problems
I liked the problems in _Principles of O. R. for Management_ by Budnick et al. (Irwin), but I think it's out of print.
From: Ludger Hinners-Tobraegel <lhinner@gwdg.de>
Subject: Looking for LP-problems
To: roland.maerivoet@innet.be
Hello Roland,
introduce one (or two) investment(s)
introduce two (or three) interest rates with an upper limit for the
cheaper credit
introduce one (or two) products which can only be produced if the
investment was also undertaken.
introduce a liquidity constraint as follows:
From: Bob Daniel <rcd@dash.co.uk>
Subject: Looking for LP-problems
In article .... Ludger Hinners-Tobraegel writes ....
From: hwolkowi@orion.math.uwaterloo.ca (Henry Wolkowicz)
Subject: Looking for LP-problems
I have assignments and solutions for a course on linear programming and also a course on Operations Research - modelling.
You can access them with URL:
thanks
From: wgm@pojoaque.santafe.edu (Bill Macready)
Subject: feasible set help
I have a problem I need to solve and I believe it is related to linear
programming. I have a set of m linear equations in n unknowns with m<
Bill
From: jeckstei@rutcor.rutgers.edu (Jonathan Eckstein)
Subject: feasible set help
The problem is ill posed. The set
From: rubin@msu.edu (Paul A. Rubin)
Subject: feasible set help
I'm both posting and e-mailing this response since I'm not persuaded the problem would be uninteresting to other readers of sci.op-research.
From: Gabor Pataki <gp1h+@andrew.cmu.edu>
Subject: Question on LP
I have a fairly simple question.
Suppose I have an LP in standard form
From: rubin@msu.edu (Paul A. Rubin)
Subject: Question on LP
I'm not sure, but I don't think so, for the following reason: if you can bound cx-cx^*, you can immediately recognize when the problem is unbounded, and I've never heard of a procedure for spotting unboundedness faster than "pivot until you hit an unbounded edge."
From: Gaius CO CHAN <
gchan@tiny.me.su.oz.au>
Subject: LP Optimization
Currently, I've a problem to find a solution of LP which is to minimise an objective function with some constraints. My problem is that I don't know how to start to program the problem. Anyone can give me some help in term of any good book(for LP programming) and any Libraries (in C++). Thanks!
From: RVICKSON@MANSCI.uwaterloo.ca (Ray Vickson)
Subject: LP Optimization
You should NOT try to write your own LP code, because the ones available already have been written with many subtleties taken care of (roundoff effects, matrix factorizations, etc.). They are often based on 20 or 30 years experience by teams of many people. You can get copies of such popular packages as LINDO for the price of a textbook, as many of these come with a student version of LINDO taped to the back cover. Also, there are FREE codes available on the net, but I don't remember where at the moment.
From: Theo Scott <rkwtgs@pukrs8.puk.ac.za>
Subject: LP Optimization
Ray Vickson wrote:
From: ashbury@skypoint.com (John W Gregory)
Subject: LP Optimization
In article <321D93B3.41C6@pukrs8.puk.ac.za>,
Theo Scott <rkwtgs@pukrs8.puk.ac.za> wrote:
From: simon1@bu.edu (Simcha Streltsov)
Subject: OR education was Re: LP Optimization
John W Gregory (ashbury@skypoint.com) wrote:
From: Gaius CO CHAN <gchan@tiny.me.su.oz.au>
Subject: Using Numerical Recipt to solve LP
Hi,
From: Hans D Mittelmann <mittelmann@math.la.asu.edu>
Subject: Using Numerical Recipt to solve LP
Hi,
From: rubin@msu.edu (Paul A. Rubin)
Subject: OR education was Re: LP Optimization
In article ...
simon1@bu.edu (Simcha Streltsov) wrote:
From: Mohammed Anwar Sayid <sayid@signal.dra.hmg.gb>
Subject: Linear Programming
Does anyone know of the comparitive benefits and/or pitfalls of performing linear programming using
EMail : sayid@signal.dra.hmg.gb
From: hrnz@chch.planet.org.nz (Harness Racing NZ)
Subject: degenerate dual
can anyone help with an algorithm to step past a degenerate (cycling)
dual when using the Primal-dual simplex method.
Ross Withers
From: tomlin@almaden.ibm.com (John Tomlin)
Subject: degenerate dual
If this is just a one-off difficulty throw in tiny random perturbations
and it should be OK. If you have a long-term interest in this, then read:
G.W. Graves "A complete constructive algorithm for the general mixed LP
problem", Naval Research Logistics Quarterly 12, pp 1-34 (1965).
That gives a nested method to deal with both dual and primal degeneracy.
From: Ricardo Esparta <ricardo@isr.uni-stuttgart.de>
Subject: Finding the set of basic variables
Could anyone point me literature references related to the choice of
the basic/nonbasic (solution/decision; project; design or whatever
they are called :-) variables?
From: tchang@teleport.com (Tipin Ben Chang)
Subject: Linear Equation Set Implications problem.....
Hi
From: rubin@msu.edu (Paul A. Rubin)
Subject: Linear Equation Set Implications problem.
.
Yes and no. Yes, you are correct that "NOT( expression1 REL expression2 )"
can be converted to "expression1 REL' expression2" where REL' is the
complementary relation to REL (for instance, REL is >= and REL' is <). The
catch is that strict inequalities are anathema to mathematical programming,
so if you are intending to use mathematical programming to solve your
problems, this may not work.
From: hennebry@plains.nodak.edu (Michael J. Hennebry)
Subject: Linear Equation Set Implications problem.....
Satisfiability can readily be converted to LIS Containment and is the first
problem proven to be NP-complete.
From: "Harry W. Conway" <ConwayH@kochind.com>
Subject: Proportionality constraints on unconstrained variables
I have a constraint that I want to include in an LP of the form:
From: James Tebboth <jrt@dash.co.uk>
Subject: Finding the set of basic variables
If you want to know about choosing the variable to enter the basis, try
Paula Harris, 1973 for details of Devex Pricing, an alternative to the
standard 'Dantzig' criterion. Forrest and Goldfarb followed this up in
1992.
Dash Associates, Blisworth House, Blisworth, Northants NN7 3BX, UK
Phone: +44 1604 858993 Fax: +44 1604 858147
Email: jrt@dash.co.uk Web: http://www.dash.co.uk/
XPRESS-MP : Software for Modelling and Optimisation
From: Johan Gunnarsson <johan_g@algonet.se>
Subject: Is this a linear programming problem?
Problem:
From: eberly@cs.unc.edu (David Eberly)
Subject: Is this a linear programming problem?
I had posted a reference to a good article on incremental constraint solving to handle exactly this type of problem, but was accused of posting obscure information. If you want the reference, let me know and I'll send it by email. The essential ideas are to (1) obtain a solution to your constraints (possibly using linear or quadratic programming) for the initial layout, then (2) resolve only those constraints that are affected by dynamic changes. The system has what are called "keep" constraints--if the current constraints lead to an underconstrained system, then enough of the variables keep their current values so that the system is properly constrained. In the overconstrained case, the system does not change (and possibly reports this state to whoever is monitoring the system). It is also possible to assign weights to the constraints, indicating how important it is to satisfy a constraint.
sasdhe@unx.sas.com
From: Chip Klostermeyer <wfk@cs.wvu.edu>
Subject: LP question
Any references to solving LP problems or (approximating) LP or IP problems over a finite field (GF(2) in particular) would be appreciated.
From: Robin Becker <robin@jessikat.demon.co.uk>
Subject: Proportionality constraints on unconstrained variables
From: hennebry@plains.nodak.edu (Michael J. Hennebry)
Subject: Proportionality constraints on unconstrained variables
"Nihilism states that? I thought it was Ivanova." -- Julian P. Graham
From: jeb1@ic.ac.uk (Dr J.E. Beasley)
Subject: Advances in linear and integer programming
Advances in linear and integer programming
Whilst some may read this book whole it is likely that the majority
of readers will be most interested in particular chapters. For
this reason each chapter has been written so that it can be read
and studied separately.
From: A.C.Robinson@lboro.ac.uk (AC Robinson)
Subject: Hard SAT problems for LP methods
Hi,
From: el@fusl.ac.be (Etienne Loute)
Subject: Graphical View of MPS file
I am continuing a subject put by Simon Papps on this newsgroup,
last september. I would like to report an unexpected use of
a well established program in the CAD-CAM field for the purpose
of visualizing the zero/nonzero structure of an LP constraint
matrix read from an mps file. Our experiment could be useful
to others.
Fac of Econ, Pol&Soc sciences, Fac. Univ. Saint-Louis Brussels
CORE & QANT/IAG Univ. Cath. de Louvain. loute@core.ucl.ac.be
From: el@fusl.ac.be (Etienne Loute)
Subject: Graphical View of MPS file
I am continuing a subject put by Simon Papps on this newsgroup,
last september. I would like to report an unexpected use of
a well established program in the CAD-CAM field for the purpose
of visualizing the zero/nonzero structure of an LP constraint
matrix read from an mps file. Our experiment could be useful
to others.
Fac of Econ, Pol&Soc sciences, Fac. Univ. Saint-Louis Brussels
CORE & QANT/IAG Univ. Cath. de Louvain. loute@core.ucl.ac.be
From: Armin Saage <asaage@wmpi06.math.uni-wuppertal.de>
Subject: find interior point , primal, without using duality
Hi, I am looking for a good method for finding an interior point.
From: Irv Lustig <irv@dizzy.cplex.com>
Subject: find interior point , primal, without using duality
In some article that got lost by my news server,
From: mokelly@magnus.acs.ohio-state.edu (Morton E O'Kelly)
Subject: Piecewise Linear Cost Function
I am trying to recall a method for employing a piece
wise linear "cost" function in a facility location problem. The
trick was to use integer variables to signal which piece
of the cost function is operative. Any pointers or
references to papers that use this device would be greatly
appreciated.
From: Metin Turkay <mt2q+@andrew.cmu.edu>
Subject: Piecewise Linear Cost Function
You can find a review of modeling and solution techniques for mathemical
programming problems with piece wise linear/nonlinear cost functions in,
From: rubin@msu.edu (Paul A. Rubin)
Subject: Piecewise Linear Cost Function
You might want to look at H. P. Williams, _Model Building in Mathematical
Programming_ (I think it's up to its third edition), John Wiley & Sons.
Look in the index under "economies of scale," as the stuff is scattered
around in the book.
From: fsaad@ttiadmin.tamu.edu (Frida Saad)
Subject: Piecewise Linear Cost Function
I found the discussion on piecewise linear objective functions
in "OSL - Optimization with IBM OSL" by Ming S. Hung et al
(ISBN 0-89426-244-0) to be very useful and very easy to understand.
You don't need to have OSL to implement the method.
From: Miroslav Trajkovic <miroslav@ee.usyd.edu.au>
Subject: Solving symmetric linear system
From: James Tebboth <james@dash.co.uk>
Subject: Piecewise Linear Cost Function
Morton E O'Kelly <mokelly@magnus.acs.ohio-state.edu> writes
From: Bob Daniel <rcd@dash.co.uk>
Subject: Piecewise Linear Cost Function
Special Ordered Sets are better in practice on problems like this, in my
experience. One possible nasty bit (numerically) is if you can't get a
good upper bound on the 'x' variable i.e. you could buy huge amounts of
stuff. If it would be helpful I could provide an example.
From: arms@cs.ualberta.ca (Bill Armstrong)
Subject: Piecewise Linear Cost Function
Using integer variables that way is one way to do things, but then you
have the problem of assuring continuity. So another way is to use
linear functions combined by max and min operations. The first step
is to identify a model of the cost function, then the next step is to
test to see if the model explains the data better than a simpler or
even linear model.
From: el@fusl.ac.be (Etienne Loute)
Subject: Solving symmetric linear system
From: Greg Holba <"100661,342"@compuserve.com>
Subject: Technology & Learning/Experience Curves
This weekend I am writing a dissertation on the influence of technology
on the learning curve/experience curve in a manufacturing context. Can
anyone provide me with information or references with respect to this.
From: moshe@mundoe.maths.mu.OZ.AU (Moshe Sniedovich)
Subject: LP codes on the WWW for teaching the simplex method!