Date: Sun, 27 Dec 1998 12:03:31 -0000
From: "Neil Freebairn" <neil.freebairn@lineone.net>
Subject: Want to Benchmark a simple iterative LP algorithm

Date: Wed, 16 Dec 1998 23:24:31 +0800
From: Ronald Hui <ronhui@hkpc.org>
Subject: Linear inequality and linear programming
To: cchui6@ie.cuhk.edu.hk

Hi,

If I have a linear inequality system for a set of variables xi, how can I find one solution that can satisfy the linear inequality constraint?

I think linear programming is a possible method. But is there any faster and easier method?

If you know the answer,please email to me since I seldome check the newsgroup.

my email is: cchui6@ie.cuhk.edu.hk
Thank you very much.

Ronald

Date: 16 Dec 1998 20:09:03 +0100
From: Dima Pasechnik <dima@duti515a.twi.tudelft.nl>
Subject: Linear inequality and linear programming
In general, nothing faster is known.

Dmitrii

Date: Thu, 17 Dec 1998 00:39:05 +0700
From: "Arthur L. Rubin" <216-5888@mcimail.com>
Subject: Linear inequality and linear programming
I think the ellipsoid method has been shown to be faster than the simplex method is guaranteed to be, but, in practice, the simplex method is actually the fastest method. (These are both linear programming methods, but I assume Mr. Hui was using "linear programming" to denote the simplex method.)

Arthur L. Rubin 216-5888@mcimail.com

Date: 17 Dec 1998 08:31:20 -0500
From: hrubin@b.stat.purdue.edu (Herman Rubin)
Subject: Linear inequality and linear programming
The speed of the ellipsoid method is not known practically; the bounds depend essentially on the size of the numbers as integers. While it may be polynomial time in the sum of the absolute values of the coefficients, this does not make the bound good.

However, the Karmarkar algorithm is generally faster for large problems. Its speed comes from going into the solution set, and not along edges.

Date: Wed, 16 Dec 1998 06:56:52 GMT
From: "Jaime Rodriguez" <jarodrig@coeds.eng.miami.edu>
Subject: A LP Problem
You cannot graph four dimensions on oridnary cartesian planes... what you need to do is substitute two of the variables for the other two and graph it as a 2-d problem..

For example, solve for c and D in terms of A and B, and substitute this into the constraints... This way you can use the graphical method...

Date: Wed, 16 Dec 1998 16:46:52 -0600
From: Jay Rudin <jrudin@nortelnetworks.com>
Subject: A LP Problem
Unfortunately, A and B are not uniquely determined by C and D in the feasible set, so this method won't work. I'm going to assume that the homework assignment has already been turned in, and supply the answer.

Look at the problem again. Any increase in A or B will reduce the objective function and make every constraint tighter. There is no reason to ever let A or B into the basis. To put it another way, any feasible solution (a, b, c, d) can be replaced with the superior feasible solution (0, 0, c, d). That reduces it to the 2-dimensional problem in C and D.

Jay Rudin

Date: Thu, 17 Dec 1998 06:58:54 -0600
From: Jeff Linderoth <linderot@mcs.anl.gov>
Subject: A LP Problem
Hello,

Likely, the professor wanted the students to solve the dual problem. 2 constraints => 2 dual variables, so a graphical method is appropriate.

Cheers,

-Jeff

Date: Mon, 07 Dec 1998 14:05:00 -0600
From: Jay Rudin <jrudin@nortelnetworks.com>
Subject: A LP Problem
Since this is a school problem, I'll give you a hint, but I won't solve it. You can't easily graph 4 dimensions. To solve it graphically you must find some mathematically valid way to reduce it to two variables. Good luck!

Jay Rudin

Date: Mon, 30 Nov 1998 20:29:31 +0100
From: "alex de schrijver" <ota018181@online.be>
Subject: linear programming diet-problem?
Hello,

We are a group of students who have a mathematic task to do. Our assignment is to find a diet-problem with 5 or more variables and 9 or more constraints.

Could someone help us with a good site or a solution.

thanks

Date: Mon, 30 Nov 1998 18:11:29 -0500
From: "Suleyman Karabuk" <suk6@lehigh.edu>
Subject: linear programming diet-problem?
Any elementary Operations Research textbook will do.

Suleyman Karabuk.
Manufacturing Logistics Institute
Lehigh University

Date: Tue, 01 Dec 1998 11:00:02 -0600
From: Jeff Linderoth <linderot@mcs.anl.gov>
Subject: linear programming diet-problem?
Hello Alex,

I suggest you check out the diet problem on the NEOS Guide. http://www-c.mcs.anl.gov/home/otc/Guide/CaseStudies/diet/

Hope this helps.

Cheers,

-Jeff

Date: Tue, 8 Dec 1998 00:30:56 +0800
From: "Chris Lee" <chris@linkpower.com.hk>
Subject: A LP Problem
Hi all,

My lecture gave us a LP problem and he require us to solve the problem by graphical method as below :

MAX -2A - B + C + 4D

Subject To

A + 2B + C + 3D < 30

-2A - B + 3C -2.5D > 20

If I can use LP software like LINDO or Excel solver, this question would become very easy. Can anyone give me some hints or solution for solving above problem by graphical method. Thanks.

Best Regard

Chris Lee

Remark : If possible, please answer me by E-mail. Thanks a lot !

Date: Thu, 26 Nov 1998 10:25:37 +0100
From: Balmes Cyril <cyril@via.ecp.fr>
Subject: Large scale problem
Does anyone have large scale linear problem ? I just want to test 2 soft I have made and I have no example of problem and solution.

Thank,

Date: 26 Nov 1998 10:57:41 GMT
From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Large scale problem
netlib has a library of linear programming problems (lp). for this and other collections and also benchmarks see http://plato.la.asu.edu/guide.html

hope this helps

peter

Date: Sat, 28 Nov 1998 06:45:24 -0700
From: "Hans D. Mittelmann" <mittelmann@asu.edu>
Subject: Large scale problem
, Hi,

are you talking about a large scale LP? You may start then at http://plato.la.asu.edu/guide.html#test

any thoughts? PLEASE responde via email

thanks,

Gary

TIA

Date: 14 Sep 1998 18:01:55 GMT
From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Linear Programming

RHS, etc.
RHS = right hand side,. the "c" in the example above

hope this helps
peter

Date: Fri, 11 Sep 1998 15:30:53 +0200
From: "Carlo Casaleggio" <carloc@mweb.co.za>
Subject: Linear Programming
Hallo

My name is carlo Casaleggio and I live in South Africa. I would appreciate it if anybody could help me with the following:

There seem to be a lot of information regarding LP on the net, but I cannot find any site which could explain to me how I can interpret the computer printouts of a LP problem. Can somebody please give me some information on how to interpret the computer printout? What does slack/surplus mean, what is the dual value, RHS, etc.

Thanks

Date: Sat, 12 Sep 1998 10:47:52 -0700
From: "Brien Alkire" <brien@alkires.com>
Subject: Linear Programming
You need to look at any standard text book on linear programming. There are so many it doesn't make much sense to recommend one. For what it's worth, I like "Intro to Linear Optimization" by Bertsimas and Tsitsiklis published by Athena Scientific, 1997.

Here's a rough synopsis:

Suppose you want to

minimize c'x
subject to Ax<=b

Here the variable is x. Typically c and x are n-vectors, A is an mxn matrix and b is an m vector. I don't think there's anything wrong with a scalar interpretation, too. If there is no x satisfying Ax<=b then we say that the problem is infeasible and therefore the optimal solution is +infinity. If the problem is unbounded the we say the optimal solution is -infinity.

Notice that the "constraints" are of an inequality type, Ax <= b. To understand slack/surplus, notice that

Ax<=b

is equivalent to requiring that

Ax + s = b, s>=0 where s in an m-vector and s>=0 means componentwise non-negativity

The variable s is the slack/surplus.

Notice our problem is a minimization problem involving the known parameters c, A and b. Duality theory says that there's a maximization problem corresponding to our problem that also involves the same parameters c, A and b. To find the dual, consider the lagrangian function:

L(x,z) = c'x + z'(Ax-b) = -b'z + x'(A'z + c) where z >= 0. Note that z is an m-vector, z>=0 means that it's positive component-wise.

If we minimize with respect to x:

inf L(x,z) = inf -b'z + x'(A'z + c) = -b'z if A'z + c = 0 and z >=0, otherwise -infinity

Our dual problem is then a maximization problem in z:

max -b'z
subject to: A'z = -c, z>=0

Many LP codes solve both problems at the same time, they're called primal-dual algorithms. We call the first problem the "primal" and the second problem the "dual". Why is this interesting?

First note that if the dual is not feasible then we say that the optimum is -infinity. If the problem is unbounded then we say that the optimum is +infinity (opposite of what we said about the minimization problem).

There's an important property that unless both the primal and the dual are infeasible, they have the same optimum value. Say that z and x are dual and primal feasible points respectively. Then

-b'z <= c'x (weak duality theorem)

So if you use a primal-dual algorithm to solve the primal, dual feasible points provide a lower bound to the optimal solution! That's useful for a lot of reasons, such as knowing when to terminate the algorithm.

Say that z* and x* are optimal dual and primal values respectively, even if unbounded. Then,

-b'z* = c'x* (strong duality)

So strong duality always holds unless both are infeasible. There are a lot of interesting correlations between the primal and the dual. One is complementary slackness:

z*'(b-Ax*) = 0

Suppose that you are really only interested in x*. The dual solution z* provides a "certificate of optimality" that guarantees x* is optimal. Another important result is Farkas lemma which says that EXACTLY ONE of the following alternatives must be true:

1. There exists some x such that Ax <= b
2. There exists some z>=0 such that A'z = 0 and b'z < 0

If we can find a z that satisfies 2 then we have a "proof" that the primal is infeasible (there are no x such that Ax <= b ).

Anyway, I hope this interests you enough to take a look at text book or two.

Brien Alkire

Date: Mon, 14 Sep 1998 12:55:17 +0100
From: Seyed Afshin Mansouri <S.A.Mansouri@lboro.ac.uk>
Subject: Linear Programming
I recomment to reffer to a text book on OR. As a good referrence, you can use the book of Whinston (1994). It contains all the definitions you are looking for, as well as directions for using computer packages.

Afshin

Date: Mon, 31 Aug 1998 21:55:29 -0700
From: "Brien Alkire" <brien@alkires.com>
Subject: LP without a clear optimization criterion
In my previous reply, I made a typo. It should be G = [ A -1 ] not G = [ A1 ].

Someone else mentioned using some "nice" criteria for an objective. A common "nice" criteria for some appliations is to minimize your favorite norm, e.g., the Eucliean norm. Then the problem in inequality form is:

Of course, the usefulness of this formulation is problem dependent. But it is a nice general form that has wide applicability. Unlike the other formulation I suggested there's no reason to believe that the solution will be interior.

Brien Alkire

Date: Sun, 30 Aug 1998 20:25:53 -0700
From: "Brien Alkire" <brien@alkires.com>
Subject: LP without a clear optimization criterion
You are trying to solve an LP feasibility problem. It is not at all unusual to use a standard LP package to solve a feasibility problem. Standard LP packages usually solve problems in either inequality form or standard form (which are duals of eachother):

Good luck,

Brien Alkire

Date: 31 Aug 1998 23:45:46 GMT
From: "H. Philip Walton" <hpwalton@worldnet.att.net>
Subject: LP without a clear optimization criterion
Several folks have suggested using zero as the cost for each variable. I disagree. You may not want to use all zeros. You may run into a degeneracy problem if you do. Depending on the lots of things, it may or may not matter.

My best suggestion is to find a different criteria that is a "nice-to-have", quantify it, and use it as the criteria. If you don't have that handy, I suggest a "random perturbation" of near-zero values.

My $0.02, hope it helps and doesn't hinder!

Philip Walton

>xmp> H. Philip Walton - Operations Research Analyst Of course this is my opinion, I pay the ISP :-) http://home.att.net/~hpwalton - be sure and sign the guestbook Date: 1 Sep 1998 09:57:47 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: LP without a clear optimization criterion

Brien Alkire

Date: Thu, 27 Aug 1998 23:29:25 -0700
From: Bernice Barnett <jbb@mediaone.net>
Subject: LP without a clear optimization criterion
Hello all. I am working on a problem and need some help. I've looked at the LP FAQ and found no help. Perhaps a pointer to the literature would be sufficient.

My problem is one of planning communications and I look at it as satisfaction, not an optimization problem. By that I mean that I am looking for any solution that does not violate a given constraint set; At the moment I do not have a reliable reason for preferences among the non violators. All of the constrains are LINEAR.

I am looking for ways to find points that satisfy the given constraints. I suppose that I could use an LP solver and create an artificial constraint but that seems craven. I assume that the standard LP solvers find a corner of the constraining hyper-cube then climb the edges, via magic incantations, to find an optima. If so, I only need the part that finds a legitimate corner.

I don't know how that is done and I don't know whether the optimality criterion is just used to define the meaning of "up" or whether it is used in some other way to define the hyper-cube. I would also be interested to know if there is some way to find a vector from a corner that points "inward". I.e, if the cube has reasonable-dimensional volume, is there a way to find a path from a corner to the inside? The reason I ask, is while I don't have an optimization criterion in hand, I do know that interior solutions are usually more stable/reliable/etc, that extremal ones.

Any comments, ideas, pointers, and/or hair-brain schemes would be most appreciated.

-- Jeff Barnett

Date: Fri, 28 Aug 1998 11:27:19 +0200
From: KolbjÀrn Christoffersen
<kolbjorn.christoffersen@itf.nlh.no>
Subject: LP without a clear optimization criterion
As I understand you, you could use ANY linear combination of the processes as the objective function, for instance all Cj=1 or only C1=1 and the other set to zero.

If you maximize this objective function, you will get a feasible solution (if one exists). If you minimize it, you will maybe get another one (at the other "side" of the feasible area?).

You could optimize with different objective functions. The mean of all this solutions will be inside the convex feasible area and will maybe be the solution you are searching.

Best regards

KolbjÀrn Christoffersen
Agricultural University of Norway

Date: 28 Aug 1998 13:51:57 +0200
From: Dima Pasechnik <dima@duti515a.twi.tudelft.nl>
Subject: LP without a clear optimization criterion
Fine, you can take any linear objective then, say, maximize x_1 subject to your set of constrains on x_1,...,x_n. First thing an LP solver does is to find a feasible point, anyway, and then it starts moving to an optimum.

The You should be careful while talking about "inside". Namely, one can talk about the interior of your polytope P defined by the constraints. (I presume you mean "polytope" while saying "cube"). The interior I of P is the subset of P such that all the constraints are satisfied as strict inequalities (in particular, there are no equality constraints). It is however possible for the problem so be feasible (i.e. all the constraints can be satisfied) while I be empty.

Most powerful modern algorithms to solve LP work by considering points in I. They're called "interior point methods". You can have a look at http://plato.la.asu.edu/guide.html

for a guide to optimization software. Dmitrii.
http://ssor.twi.tudelft.nl/~dima

Date: 28 Aug 1998 09:07:18 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: LP without a clear optimization criterion
Tell a simplex solver to just do phase one. If you have to give it a cost vector, give it all zeros.

You can formulate and solve goal programming models in ordinary LP, using ordinary LP solution codes. I think there are also some specialized GP codes available that may be a bit more efficient.

Date: Tue, 19 May 1998 16:58:07 -0400
From: "John F. Chionglo" <john_chionglo@dofasco.ca>
Subject: Question about dual prices
Hi.

Suppose we have an LP and it has the unique optimal solution, x*. Is it possible to have more than one set of dual prices? - john

John F. Chionglo                    Dofasco Inc.
B.A.Sc., P.Eng.                     Box 2460, Hamilton, ON
Industrial Engineer                 L8N 3J5 Canada
Tel: 905-548-7200 x3665             Fax: 905-548-4580

max x
c: x<=1
d: x<=1
x>=0

Bob Daniel
Dash Associates, Blisworth House, Blisworth, Northants NN7 3BX, UK
Phone: +44 1604 858993        Fax: +44 1604 858147
Email: rcd@dash.co.uk         WWW: http://www.dash.co.uk/
      XPRESS-MP - Software for Modelling and Optimisation

peter

Date: Fri, 15 May 1998 00:50:49 GMT
From: Trifonov@my-dejanews.com
Subject: LP problem and pseudo inverse matrices

Hi, all,

I am looking for the reference for the application of the pseudo inverse matrices to represent a solution for linear programming problem. Quite a long time ago I saw such article by some italian mathematicians.

Pls answer by email to nurmi@math.dvgu.ru (as I am not a regular reader of news).

Date: 04 May 1998 12:14:59 -0700
From: Nicky Sandhu <nsandhu@water.ca.gov>
Subject: Piecewise linear constraint on LP?
Sorry about that. It should read as C = A1/x1 + A2/x2 + A3/x3 + ...

The question can be generalized as if one has a non-linear constraint under what conditions ( if any ) can that constraint be represented as a linear piece- wise constraint to the LP.

From the replies so far and from my understanding of the problem, here's what I think is the answer.

One can represent non-linear constraints with piecewise linear functions if the constraints all agree on the non-feasible regions of space. In other words if the feasibile region is on the concave side of the constraint such a linearization is possible.

Take for example two variables x1 and x2 where the non-linear constraint on them is

x1**2 + x2**2 <=4 :

The above constraint defines the region in the x1-x2 space which lies within a circle of radius 2 and has the centre at (0,0).

In a gross approximation this constraint can be approximated by the following linear inequalities x1<=2, x2<=2, x1>=-2, x2>=-2. That would be the square enclosing the circle and is a set of inequalities which are an approximation to the non-linear constraint. The inequalities can be further refined by more line segments, such as enclosing the circle in a polygon.

The reason this approach works is because the non-linear constraint can be represented as a set of independent inequalities. The only time this would work is when we are looking at feasibility on the concave side of the constraint function.

Any discussion/followup on this would enlighten me further. Thanks

--Nicky

Date: 5 May 1998 10:06:43 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: Piecewise linear constraint on LP?
It can't.

More precisely, "piece-wise linear" works when the feasible set is convex. Since you have an equality, the feasible set is not a convex set, it is the boundary of a convex set.

To exclude x from the outside, you can solve the separation problem and add constraints to your heart's delight.

Excluding x from the interior is harder. You might try using branch and bound with the disjunctions chosen on the fly. If x has to be on the circumference of a circle, e.g. the one above, it must not be inside any inscribed polygon. If a branch finds an intermediate x value is (1.5, 0), then it could do any of at least four things:

1. decide (1.5, 0) is close enough to be considered on the circumference and terminate the branch
2. decide the nearpoint (2.0, 0) is close enough to optimum and terminate the branch
3. split three ways: x1<=1 or
   sqrt(3)x1+x2>=2*sqrt(3) or
   sqrt(3)*x1-x2>=2*sqrt(3)

   This disjunction requires that x not be inside the triangle with vertices (2, 0), (1, sqrt(3)), (1, -sqrt(3)).

4. split according to some other disjunction that excludes the current x, but includes the circumference

Mike hennebry@plains.NoDak.edu
"I think, therefore it missed." -- The Doctor

Date: 4 May 1998 10:05:24 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: Elimination of variables in inequalities

In article <6ifb8a$e2i$1@goldenapple.srv.cs.cmu.edu>,
Fabio Gagliardi Cozman  wrote:
:               Suppose I have a row vector Z = [X, Y],
:               where X and Y are row vectors. Now I have
:               inequalities
:                       A Z^t <= 0,
:               where A is a matrix of appropriate
:               dimension (^t means transpose).
:
:               How do I find the inequalities just
:               for X? I.e., I want to eliminate Y
:               from the inequalities and obtain
:                       B X^t <= 0

Probably you need a mechanism for finding the constraints you need. Finding all of them may well be out fo the question.

I suspect you need a separation algorithm, i.e. given X0, either find b such that b X0^t > 0 and A Z^t <= 0 implies b X^t<=0 or determine that there exists Y such that A [X0, Y]^t<=0. One way to do this is to solve min |X0-X| subject to A [X, Y]^t <= 0 . b=X0-X .

Finding a facet is harder.

Mike hennebry@plains.NoDak.edu
"I think, therefore it missed." -- The Doctor

Date: Sat, 02 May 1998 15:47:22 -0400
From: Joao Soares <jsoares@corc.ieor.columbia.edu>
Subject: reoptimization with an interior-point (or penalty) algorithm
Hello

I would be grateful if someone could let me know of references (articles, parts of books) in how to perform reoptimization with an interior-point method for linear programming, or more generally a penalty method for nonlinear programming.

By this I mean, what is the right way to setting the penalty parameter and starting point assuming that you already know the optimal solution to a given problem and you want to solve a slightly different problem, for example, one that has an additional constraint.

Any reference is appreciated,

Joao Soares

Date: Sat, 02 May 1998 13:53:53 -0700
From: Hans D Mittelmann <mittelmann@asu.edu>
Subject: reoptimization with an interior-point (or penalty) algorithm
Hi, the authors of both the codes BPMPD and HOPDM have built warmstarts into their codes. Links are on http://plato.la.asu.edu/guide.html#LP

You may have to contact the authors to get the versions with this feature. Concerning theory, check the papers of the authors through their webpages.

Hans Mittelmann

Date: 30 Apr 1998 12:32:28 -0700
From: Nicky Sandhu <nsandhu@water.ca.gov>
Subject: Piecewise linear constraint on LP?
Hi,

I have the following problem. I am using LP to solve a system with various linear constraints except a couple. These constraints are of the following form:

C = A/x where C and A are constants and x is a decision variable. However over the range of possible solutions it is possible to write this constraint as a piecewise linear function where each piece is valid for a certain range of x. In other words of the form:

C = B1*x for X1 < x < X2
C = B2*x for X2 < x < X3 ....

Furthermore this constraint is monotonic that is the slopes B1, B2, ... are either decreasing or increasing

My question is

• Is it possible to somehow represent this constraint for LP?
• If not what is the best possible approach, both in terms of stability and speed?

Thanx. And feel free to give any pointers to material that could be referred to...

--Nicky

PS email replies are welcome ;-)

Date: Thu, 30 Apr 1998 18:51:41 -0400
From: Dale A Robertson <76312.3057@CompuServe.COM>
Subject: Piecewise linear constraint on LP?
This is sometimes treated by introducing {0,1} variables and writing the condition as a single expression. Alas you are now into the domain of mixed integer programming. The idea is discussed (inter alia) in the book by Papadimitrio and Steiglitz "Combinatorial Optimization" (I hope that is the right title - my copy is at work). Cheers

Date: Fri, 01 May 1998 11:13:19 -0400
From: "J.T. Linderoth" <jeff@akula.isye.gatech.edu>
Subject: Piecewise linear constraint on LP?
Actually, it depends. If your slopes are increasing and the problem is a minimization problem, then you can write it as an LP. (Conversely, if the slopes are decreasing and you have a maximization problem, you can write it as an LP).

> --> If not what is the best possible approach, both in terms of stability
> and speed?

Asn early reference to this is

@article{beal:globa,
        AUTHOR = "Beale, E. M. L. and J. J. H. Forrest",
        TITLE = "Global optimization using special ordered sets",
        JOURNAL = "Mathematical Programming",
        YEAR = 1976,
        VOLUME = 10,
        PAGES = "52-69"
}

Sorry for the terse explanation. If you need more help modeling this, let me know.

Cheers,

-Jeff

-----------------------------------------------------------------------------
Jeffrey T. Linderoth                               jeff@akula.isye.gatech.edu
Logistics Engineering Center               http://akula.isye.gatech.edu/~jeff
Industrial and Systems Engineering                      Phone: (404)-894-2366
Georgia Tech                                            Fax:   (404)-894-0390

Mike hennebry@plains.NoDak.edu
"I think, therefore it missed." -- The Doctor

Date: Thu, 30 Apr 1998 11:51:36 +0200
From: "Juan" <jrufilanchasXXX@financier.com>
Subject: LHS how ?
Hi,

I need a Latin Hypercube sampling function for Matlab but, as far as I know, such a software does not exist.

Could someone point me to some web, book, text or something else where I could learn how to program my LHS.

Thanks in advance

Juan Rufilanchas.

------------------------------

Date: Tue, 28 Apr 1998 14:35:32 +0200
From: Carlos Frontera <frontera@icmab.es>
Subject: LP Tutorial
Hi Everybody:

I am interested in learning Linear Programming. Does anybody know if there is any online tutorial or text about it?

Thanks in advance

Carlos Frontera
frontera@icmab.es

Date: 28 Apr 1998 07:35:21 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: LP Tutorial
yes, greenberg has done a good job on it: http://www-math.cudenver.edu/~hgreenbe/

hope this helps

peter

Date: Tue, 28 Apr 1998 11:17:03 +0100
From: James Tebboth <james@dash.co.uk>
Subject: LP Tutorial
John Beasley's OR Notes are pretty good too: http://mscmga.ms.ic.ac.uk/jeb/or/contents.html

James

James Tebboth
Dash Associates, Blisworth House, Blisworth, Northants NN7 3BX, UK
Phone: +44 1604 858993          Fax: +44 1604 858147
Email: james@dash.co.uk         Web: http://www.dash.co.uk/
        XPRESS-MP : Software for Modelling and Optimisation

ftp://garbo.uwasa.fi/pc/ts/tslin35b.zip

Friendly linear programming and linear goal programming.

All the best, Timo

Prof. Timo Salmi   Co-moderator of news:comp.archives.msdos.announce
Moderating at ftp:// & http://garbo.uwasa.fi/ archives 193.166.120.5
Department of Accounting and Business Finance  ; University of Vaasa
mailto:ts@uwasa.fi   ; FIN-65101,  Finland

I need help with a (simple, I believe) problem:

Suppose I have a row vector Z = [X, Y], where X and Y are row vectors. Now I have inequalities A Z^t <= 0, where A is a matrix of appropriate dimension (^t means transpose).

How do I find the inequalities just for X? I.e., I want to eliminate Y from the inequalities and obtain B X^t <= 0

Is this problem easy to solve? Complexity? Algorithms? I would *very* much appreciate any pointer to any clarification on these matters.

Please send email to fgcozman@cs.cmu.edu or fgcozman@usp.br, as I'm not able right now to check the bboards frequently.

Thanks much,

Fabio Cozman

Fabio G. Cozman

Robotics Institute, Carnegie Mellon University

That is right. The Fourier-Motzkin elimination method (F-ME) can be used to eliminate variables in a linear system, in step by step manner, by constructing a series of inequalities. See Dantzig \cite{da:bo}. This method may be regarded as an extension of Gaussian elimination method for a system of linear equations. In \cite{da:bo}, F-ME is used to discuss Linear Programming (LP) problems, and a LP example is investigated. There are many applications of F-ME. For example see the works of (arranged alphabetically): Bradley \cite{brad73}, Cabot \cite{cabo}, Chandru \cite{chan}, Duffin \cite{duff}, Eaves and Rothblum \cite{earo}, Kohler \cite{kohl}, Kuhn \cite{kuhn}, Lee \cite{lee}, and Williams \cite{will76}. In \cite{cabo}, F-ME is used to solve an inequality constrained Knapsack problem, and computational experiments are reported.

Another interesting fact is that there exists a dual of Fourier-Motzkin elimination (DF-ME) discussed by Dantzig and Eaves \cite{daea}. This method eliminates homogeneous equations of a LP problem step by step using a series of transformations of variables. In \cite{daea}, it is also suggested DF-ME might be applied to some particular types of Integer Linear Programming (ILP) problems. DF-ME is described by Beale \cite{bl:bo}, and discussed by Knolmayer \cite{knol76}. Williams \cite{will:fea} shows that DF-ME can be used to eliminate constraint equations of an ILP problem. Following the work of \cite{daea,will:fea}, DF-ME is applied to further discuss the structure of all feasible solutions to a Mixed Integer Linear Programming (MILP) problem, where only some nonnegative variables are restricted to integer values and the corresponding coefficients may be 1 in the absolute value, \cite{zhu:fea}. Using DF-ME, further investigation has been done.

Williams \cite{will:lp} uses DF-ME to study LP problems. F-ME and DF-ME are discussed further by Williams \cite{will:plp}. The theoretical insight given by the two methods are demonstrated, as well as their clear geometrical interpretation, in \cite{will:plp}.

Studying an equivalent form is of interest because this formulation may be easier to solve than the original one. As an elimination procedure, DF-ME is different from another reduction method, called aggregation method, in Integer Programming (see, for example, Glover and Babayev \cite{glba}). Using DF-ME, the optimality of the LP relaxation is always retained. It is not generally true when the aggregation method is used.

Some references:

\begin{thebibliography}{99}
\bibitem{beal} E.M.L. Beale, Cycling in the dual simplex algorithm, {\em Naval Res. Logist. Quart.} 2 (1955) 269-276.

\bibitem{bl:bo} E.M.L. Beale, {\em Mathematical Programming in Practice}, (Pitman, London, Reprinted 1971).

\bibitem{brad73} G.H. Bradley, An algorithm for integer linear programming: a
combined algebraic and enumeration approach, {\em Oper. Res.} 21 (1973) 45-60.

\bibitem{cabo} A.V. Cabot, An enumeration algorithm for knapsack problems, {\em Oper. Res.} 18 (1970) 306-311.

\bibitem{chan} V. Chandru, Variable elimination in linear constraints, {\em Comput. J.} 36 (1993) 463-472.

\bibitem{da:bo} G.B. Dantzig, {\em Linear Programming and Extensions}, (Princeton University Press, Princeton, Third Printing, 1966).

\bibitem{daea}  G.B. Dantzig and B.C. Eaves, Fourier-Motzkin elimination and its dual, {\em J. Combin. Theory (A)} 14 (1973) 288-297.

\bibitem{duff} R.J. Duffin, On Fourier's analysis of linear inequality systems, {\em Math. Programming Study} 1 (1974) 71-95.

\bibitem{earo} B.C. Eaves and U. Rothblum, Dines-Fourier-Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields, {\em Math. Programming} 53 (1992) 307-321.


\bibitem{gane} R.S. Garfinkel and G.L. Nemhauser, {\em Integer Programming}, (Wiley, New York, 1972).

\bibitem{gass} S.I. Gass, {\em Linear Programming: Methods and Applications}, (McGraw-Hill, New York, Third Edition, 1969).

\bibitem{glba} F. Glover and D.A. Babayev, New results for aggregating integer-valued equations, {\em Ann. Oper. Res.} 58 (1995) 227-242.


\bibitem{guan} M.G. Guan and H.D. Zheng, {\em Linear Programming}, (Shandong Scientific Technology Press, Shandong, China, 1983), (in Chinese).


\bibitem{knol76} G.F. Knolmayer, Balance equations and modelling principles, {\em 6th Annual International Mathematical Programming Symposium}, Brussels, Nov. 1976.


\bibitem{knol} G.F. Knolmayer, {\em Programmierungsmodelle f\"{u}r die Produktionsprogrammplanung}, Birkha\"{u}ser (1980).

\bibitem{knol82} G.F. Knolmayer, Computational experiments in the formulation of linear product-mix and non-convex production-investment models. {\em Comput. \& Ops. Res.} 3 (1982) 207-219.

\bibitem{kohl} D.A. Kohler, Projections of convex polyhedral sets, {\em Operations Research Centre Report}, ORC 67-29, University of California, Berkeley (1967).

\bibitem{kuhn} H.W. Kuhn, Solvability consistency for linear equations and inequalities, {\em Amer. Math. Monthly} 63 (1956) 217-232.

\bibitem{lee} R.D. Lee, An application of mathematical logic to the integer linear programming problem, {\em Notre Dame J. Formal Logic} 23 (1972) 279-282.

\bibitem{will76} H.P. Williams, Fourier-Motzkin elimination extension to integer programming problems, {\em J. Combin. Theory (A)} 21 (1976) 118-123.

\bibitem{will:fea} H.P. Williams, A characterisation of all feasible solutions to an integer program, {\em Discrete Appl. Math.} 5 (1983) 147-155.

\bibitem{will:lp} H.P. Williams, Restricted vertex generation applied as a crashing procedure for linear programming, {\em Comput. \& Ops. Res.} 4 (1984) 401-407.

\bibitem{will:plp} H.P. Williams, Fourier's method of linear programming and its dual, {\em Amer. Math. Monthly} 93 (1986) 681-694.

\bibitem{wols} L.A. Wolsey, Group-theoretic  results in mixed integer programming, {\em Oper. Res.} 19 (1971) 1691-1697.

\bibitem{zhu:fea} N. Zhu, On the structure of feasible solutions to  mixed integer linear programming problems, {\em Tech. Rep.}, The 2nd Scientific Discussion Conference, Sichuan Institute of Finance and Economics, Chengdu, China, Sept. 1984, (in Chinese).

\bibitem{zhu:lp} N. Zhu, A new algorithm for linear programming - the constraint reduction method, {\em Caijing Kexue}, (1984) {\em no.}6, 52-56, (in Chinese); \{{\em Current Mathematical Publications} 17 (1985)  {\em no.}14, page 1996\}.

\bibitem{zhu:plp} N. Zhu and S.L. Hu, A new algorithm for a parametric linear program, {\em Tech. Rep.}, The Operations Research Conference of Sichuan Province, Chengdu, China, Dec. 1984, (in Chinese).

\bibitem{zhbr} N. Zhu and K. Broughan, On aggregating two linear Diophantine equations, {\em Discrete Appl. Math.}  83 (1998) 91-106.

\end{thebibliography}

Nan Zhu

=================================================================
Nan Zhu, DPhil
Department of Mathematics    Fax:   +64 (7) 838 4666
The University of Waikato    Tel:   +64 (7) 838 4466 ex. 8801
Private Bag 3105, Hamilton   Email: znan@waikato.ac.nz
New Zealand                  http://www.math.waikato.ac.nz/~znan/
=================================================================

I don't really know much about optimization or linear programming, however, I have a little problem that I wish to find a solution to, and it seems to me it belongs to LP or similar disciplines.

Here's the problem: say I have a coal mine, and a station where I can get the coal to. Now, I have a certain amount of workers, say n, each worker can get 8 units of coal in 6 units of time. My question is, what is the number of workers I need to get the most amount of coal mined in the least time possible.

Here's what I've come up with (by oversimplifying the conditions):

n: number of workers
y: total amount of coal mined
t(y) : time needed to mine y amount of coal

t(u): unit time, the amount a worker needs to get 8 units of coal = 6 time
units


t : total time needed.  t(y) = t / t(u)

this gives the equation:

y = 8 * t (y) * n / 6

how do I get the max values though? it seems that either my assumptions are faulty, or that I need to make more relations. Please help.

Note: this is by no means a homework problem, it's actually, to tell the truth, about a game that I'm trying to find the best model for working with.

Thank you and have a nice day,

AB

Date: 22 Apr 1998 19:53:37 GMT
From: borchers@nmt.edu (Brian Borchers)
Subject: Linear Ordering Problems
I'm interested in obtaining examples of large scale linear ordering problems. I'm already familiar with the LOLIB problems, but these are relatively small and can be solved relatively quickly.

Brian Borchers                              borchers@nmt.edu
Department of Mathematics                   http://www.nmt.edu/~borchers/
New Mexico Tech                             Phone: 505-835-5813
Socorro, NM 87801                           FAX: 505-835-5366

Robin Becker

Date: Tue, 21 Apr 1998 07:57:08 +0200
From: Jostein Vada <Jostein.Vada@itk.ntnu.no>
Subject: complexity in LP and QP
Thanks for your answer to my question. Yes, by "fastest", I meant "best known complexity result".

Based on your answer, I have the following question:

Are the best known complexity results equal for both LP and QP?

-The background for my question is that I have two options for solving a specific problem, either by

1. solving 2 QP-problems and s LP-problems with n variables and m constraints, or by
2. solving a single QP problem with n+m variables and 2m constraints.

What I really want to find out is which of the two options is the preferred one due to complexity.

Jostein

Date: 21 Apr 1998 07:29:57 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: complexity in LP and QP
the complexity bounds are the same for LP and (convex, of course) QP. but this says little regarding your practical question, because these complexity bounds cannot take into account the specific nature of your problem. I think some practical investigation is needed in order to decide what is best to do. to get an impression how large the gap between theoretical- best and practical-best might be, take a look at the benchmarks in http://plato.la.asu.edu/guide.html or at the paper of Seifi and Tuncel in "computational optimization and applications" vol9, no2, 1998.

to answer robin beckers question: the final phase consists in a change of the basis. from the theoretical results it follows, that you can read off the correct basis from the interior point solution, if this is sufficiently close to the solution. so you have simply to solve one linear system of equations. usually in the textbooks this is described as a sequence of basis changes a la LP-simplex, hence the O(n**3) complexity. but of course you can use some strassen like procedure to get a better complexity bound. but don't forget: practical large scale LP's and QP's are sparse, hence taking sparsity must be taken into account for efficiency (this is the reason why i did not use the algebraic complexity bound, rather the bound on the number of steps to be taken). this however rules out strassens solution method. hope this helps

peter

Date: 15 Apr 1998 10:37:07 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: Question on real dollar costs and discounting in an LP

In article <6h29ss$f93$1@nnrp1.dejanews.com>,   wrote:
:I have an LP with a ten-year time horizon.  The LP minimizes total costs and
:reports the result in discounted dollars.  My question is whether or not to
:use nominal or real dollar costs in the LP.  Does it even matter?  Also, do I
:need to be consistent between the costs and  my discount rate. That is, if
:the costs are in real dollars should I be using a real discount rate.  Are

can somebody answer the following question:

What is the complexity of the fastest LP and QP-solvers (preferable with text-book references)?

Jostein Vada (PhD student)

Date: 20 Apr 1998 14:22:00 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: complexity in LP and QP
what do you mean by "fastest"?. If you search for a answer in terms of cpu-time, your question will remain unanswered, I guess. But I assume that you meant "best known complexity result". these are clearly the primal dual path-following infeasible interior point methods with an iteration count of O(sqrt(n)L) to obtain an approximate solution from which the true solution can be obtained directly. here L is the so called information length (binary coding length of input). each step of these methods requires the solution of a linear system of a quite special structure (and dimension about 3n*3n), possibly with some right hand sides. but O(n**3) is not a good guess for the algebraic complexity of a single step because of the special structure. I don't know whether there is a proof that the bound O(sqrt(n)L) is unbeateble. references: st. wright: interior point methods (siam) 1997. schrijver: theory of linear and integer programming, chichester 1987. hope this helps

peter

Date: Wed, 04 Mar 1998 11:01:56 +0100
From: Arnold Neumaier <neum@cma.univie.ac.at>
Subject: Nearest Multiple of a Vector
Are there fast algorithms for computing the multiple of a vector $b$ nearest to a vector $a$ in the 1-norm and the max norm,

$\min_\lambda ||a-\lambda b||_1$,
$\min_\lambda ||a-\lambda b||_\inf$,

$\min_\lambda max_i (a_i-\lambda b_i)$ ?

More precisely, I would like to know the corresponding active sets after $O(n)$ operations, if possible with a constant independent of the length of the data.

I'd appreciate any pointers to the literature or to software. If you post to sci.op-research, please send an email copy to me since I read the newsgroup only every few weeks.

Arnold Neumaier
neum@cma.univie.ac.at

Date: 5 Mar 1998 09:49:45 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: Nearest Multiple of a Vector
To: Arnold Neumaier <neum@cma.univie.ac.at>
Your functions to be minimized are convex piecewise linear in one variable \lambda. It suffices therefore the check the "kinks" (points of nondifferentiability) and this is O(n).

peter

Date: Thu, 05 Mar 1998 16:55:46 +0100
From: Jens Weber <weber@euv-frankfurt-o.de>
Subject: Nearest Multiple of a Vector
You can also try to rewrite it as linear problem:

Minimize c

s.t. a_i - lambda*b_i <= c for i=1, ...,n

and solve it with simplex method. (Although it cannot guarantee O(n) it usually behaves rather good in problems like this.

Perhaps this helps.

Greetings to Darmstadt

Jens

-------------------------------------------------------
Jens Weber
Europa-Universitaet Viadrina, Faculty of Economics
P.O. Box 776, D-15207 Frankfurt (Oder), Germany
-------------------------------------------------------
Voice   +49.335.5534.413
Fax     +49.335.5534.675
E-Mail  weber@euv-frankfurt-o.de
-------------------------------------------------------

$\min_\lambda ||a-\lambda b||_1$,
$\min_\lambda ||a-\lambda b||_\inf$,

$\min_\lambda max_i (a_i-\lambda b_i)$ ?

More precisely, I would like to know the corresponding active sets after $O(n)$ operations, if possible with a constant independent of the length of the data.

I'd appreciate any pointers to the literature or to software. If you post to sci.op-research, please send an email copy to me since I read the newsgroup only every few weeks.

Arnold Neumaier
neum@cma.univie.ac.at

Date: 5 Mar 1998 09:49:45 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: Nearest Multiple of a Vector
To: Arnold Neumaier <neum@cma.univie.ac.at>
Your functions to be minimized are convex piecewise linear in one variable \lambda. It suffices therefore the check the "kinks" (points of nondifferentiability) and this is O(n).

peter

Date: Thu, 05 Mar 1998 16:55:46 +0100
From: Jens Weber <weber@euv-frankfurt-o.de>
Subject: Nearest Multiple of a Vector
You can also try to rewrite it as linear problem:

Minimize c

s.t. a_i - lambda*b_i <= c for i=1, ...,n

and solve it with simplex method. (Although it cannot guarantee O(n) it usually behaves rather good in problems like this.

Perhaps this helps.

Greetings to Darmstadt

Jens

-------------------------------------------------------
Jens Weber
Europa-Universitaet Viadrina, Faculty of Economics
P.O. Box 776, D-15207 Frankfurt (Oder), Germany
-------------------------------------------------------
Voice   +49.335.5534.413
Fax     +49.335.5534.675
E-Mail  weber@euv-frankfurt-o.de
-------------------------------------------------------

:a=max Xi in linear form?
:     i
: and another one a=Sum XiYi
:                                 i
: where Xi is real and Yi is binary.

Date: 5 Mar 1998 09:51:59 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: linearization problem
impossible. piecewise linear is _not_ linear .

peter

Date: Mon, 09 Mar 1998 18:29:24 +0100
From: Roberto Cordone <cordone@elet.polimi.it>
Subject: linearization problem
Hello.

If you are looking for (mixed integer) linear forms, you can try these:

1) a = max Xi
             i

  Xi - Xj >= M (Vi - 1) (for all i and all j)

  Sum Vi = 1
     i

  Vi in {0,1}

Therefore:

max Xi = Sum Vi Xi
  i              i

By the way, I suppose you do not simply need to minimize function 'a'. In this case, it would be enough to require:

a >= Xi (for all i)

and the minimization condition would force 'a' to be what you require.

***************************************************************************

2) a = Sum Vi Xi
        i

Xi + (Vi - 1) M <= Wi <= Vi M (for all i)

0 <= Wi <= Xi

should impose Wi = Vi Xi.

Therefore:

a = Sum Wi
     i

Roberto

Date: Mon, 09 Mar 1998 12:40:35 -0500
From: "Joseph T. Adams" <jadams@tc3net.com>
Subject: Monte Carlo Simulation
I am new to the field of OR and to this news group. I need some help with Monte Carlo simulations. Specifically, what type of computer software or programming do we need to consider for such a simulation? I would also appreciate any references in the literature that would give me more back ground on Monte Carlo.

Thanks.

Joe

Date: Mon, 02 Mar 1998 07:39:35 GMT
From: A. Bisi
Subject: Help: a "real" LP problem !
I don't know if this NG is the best place into post this, but I hope someone can help me, I'm a software engineer not a mathematician so my op-research knowledge level is very low.

I've to solve a problem, and I think that LP is the right solution: a little farm has a warehouse with about 8000+ components used to produce 200-250 final products. I need to maximize the profit _reducing_ warehouse.

I've tried to simplify writing an example with 2 products and 6 components: P1 (build using c1,c2,c3 components) and P2 build using c2,2*c4,c5,c6; my warehouse is: 10 of type c1, 3 of c2, 4 of c3, 6 of c4, 8 of c5, 3 of c6. I sell P1 at 100$ and P2 at 150$. Using LP: (here c1=c2=...=c6=1, because I've write 2*c4 else c4=2)

max z = 100*P1 + 150*P2
         c1*P1          <= 10
         c2*P1 +  c2*P2 <= 3
         C3*P1          <= 4
                2*c4*P2 <= 6
                  c5*P2 <= 8
                  c6*P2 <= 3

        int p1,p2 >= 0
<.pre>
Solving ILP (I think I'll use a branch-and-bound algorithm, do you
agree ?) I can find how many P1 and P2 I can build using my warehouse and the max profit z. (For the example above: z=450, P1=0, P2=3)


I hope that everything above is right.


But (finally) the problem is: I need to minimize warehouse too !!!
(The best solution is the one with warehouse equal zero !).
And I need to reduce the total value of warehouse, so I need to give
priority in using those components with higher value.


How can I solve this ??


Thanks, and please answer _ONLY_ by e-mail !!

Andrew Bisi <a.bisi@iol.it>



Date: 3 Mar 1998 10:59:08 GMT

From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)

Subject: Help: a "real" LP problem !

To: A. Bisi


this is a multiple criteria optimization problem , usually transformed in a single criterion problem via weighting , e.g.
  f(z,P1,..,P8000) = -profit + factor*sum (Pi*cost(pi)) = minimum .


having warehouse=0 is not a good idea, since delivery time will also
be some kind of cost, I guess.


Then one plays with "factor" in order to assess the influence of the
two different aims on the solution.


This is clearly a very rough advice, there are lots of books on multiple criteria decison making.


hope this helps

peter




Date: Tue, 3 Mar 1998 18:47:16 +0100

From: "Juan Rufilanchas" <jrufigo@santandersupernet.com>

Subject: Help: a "real" LP problem !


You have a multiple criteria function to optimize: as I understand you have to maximize your return and minimize your warehouse
costs,I suggest a net profit function.


Something like:


Netprofit=number_of_units*(price_per_unit - unit_cost) - fixed_costs, obviously you need a warehouse cost per unit and, if you want, some other fixed costs.


You have to say to your software what do you prefer: more benefits or less warehouse, that 's why you must "price" your warehouse occupation.


If you want, you can evaluate when you will be paid and when you paid for the warehouse materials, then you have a capitalised cost and a discounted price. This is better than the first solution because you are comparing all your incomes and expenses in present values.



You shouldn't have  any problem to solve this with a LP software.



Bye



Date: Tue, 03 Mar 1998 14:37:27 -0700

From: "Hans D. Mittelmann" <mittelmann@asu.edu>

Subject: Help: a "real" LP problem !

To: A., Bisi


Hi,

maybe, you take a look at the multiple criteria LP code PROTASS listed in http://plato.la.asu.edu/guide.html#LP


Hans D. Mittelmann                      http://plato.la.asu.edu/
Arizona State University                Phone: (602) 965-6595
Department of Mathematics               Fax:   (602) 965-0461
Tempe, AZ 85287-1804                    email: mittelmann@asu.edu




SCI.OP-RESEARCH Digest     Mon, 2 Mar 98 Volume 5: Issue  9

 

Date: Mon, 23 Feb 1998 20:47:30 GMT

From: maryrose@iname.com (Maryrose Ball)

Subject: Need help with Linear programming

On Tue, 17 Feb 1998 20:46:26 -0500, "Crap"  wrote:

>Hey, I'm stuck here!  I just started Linear Programming and I have no clue
>as to what to do when ever I start the problem... I don't know which is the
>constraints and i don't know how to figure out any of the equations that i
>need to use with the problem...If any one could help me i would greatly
>appreciate it.  Any hints would be helpful...ANYTHING...Please some one
>E-mail me and help me out here...
>                Thanx a bunch,
>                                            Tiffany
>
>


Try reading chapter 3 of 'Operations Research: Applications and Algorithms'
by Wayne L. Winston.  This has lots of examples of problem formulation and I
found it to be clearly written.  


M.




SCI.OP-RESEARCH Digest     Mon, 19 Jan 98 Volume 5: Issue  3

 


Date: Wed, 14 Jan 1998 15:17:21 +0100

From: Jens Weber <weber@euv-frankfurt-o.de>

Subject: LP-relaxation NP-complete?

Hi Martin,


LP problems are polynomial solvable (as long as the coefficients are
rational numbers) - for instance using the Ellipsoid Algorithm (by
Khachiyan) or the Projected Facet Algorithm (by Karmarkar), but those
algorithms are just very rarely used. There is no widespread efficient
implementation of them.


The main reason for considering relaxed integer problems is that the LP
relaxation can be solved by the Simplex method (or some other very
efficient method). - That means, you can use standard software or
standard routines.


The Simplex method itself is (in the worst case) not polynomial. (There
is a counter-example by Klee and Minty, already about 30 years old. But
it seems that such hard types of problems occur actually very seldom.)


Jens

-------------------------------------------------------
Jens Weber
Europa-Universitaet Viadrina, Faculty of Economics
P.O. Box 776, D-15207 Frankfurt (Oder), Germany
-------------------------------------------------------
Voice   +49.335.5534.413
Fax     +49.335.5534.675
E-Mail  weber@euv-frankfurt-o.de
-------------------------------------------------------




Date: Wed, 14 Jan 1998 16:37:55 -0500

From: "J.T. Linderoth" <jeff@akula.isye.gatech.edu>

Subject: LP-relaxation NP-complete?

Hello All,

Jens Weber wrote:

> The Simplex method itself is (in the worst case) not polynomial. (There
> is a counter-example by Klee and Minty, already about 30 years old. But
> it seems that such hard types of problems occur actually very seldom.)


Not to split hairs, but the above is not known to be true.
( If anyone knows this to be true, please include me as co-author on
  the paper  :-)


What is known to be true is that the simplex method with the Dantzig
pivot rule (that is, pivoting the variable whose reduced cost
is largest into the basis) is in the worst case not polynomial.
This is what the Klee-Minty example proves.


For just about any pivot rule you can think of, someone has contrived
an example for which the simplex method will not be polynomial.


Recently, Gil Kalai and (independently) Matousek, Sharir, and Welzl
have developed a randomized "subexponential" pivot rule for the
simplex method.


Best wishes for the new year,

-Jeff
-----------------------------------------------------------------------------
Jeffrey T. Linderoth                               jeff@akula.isye.gatech.edu
Logistics Engineering Center               http://akula.isye.gatech.edu/~jeff
Industrial and Systems Engineering                      Phone: (404)-894-2366
Georgia Tech                                            Fax:   (404)-894-0390

------------------------------


Date: Thu, 15 Jan 1998 11:27:13 +0100

From: Jens Weber <weber@euv-frankfurt-o.de>

Subject: LP-relaxation NP-complete?

Hello all,


to put it right (and not to split hairs): The simplex method is (as far as I know) not proved to be polynomial - in the sense that there is a type or modification of it which can solve
all problems polynomially.  (But this has nothing to do with the basic idea of LP relaxation.)


Jeff - thanks for your comment and also best wishes for 1998


Greetings from Germany

Jens



SCI.OP-RESEARCH Digest     Mon, 12 Jan 98 Volume 5: Issue 2



 
Date: Fri, 09 Jan 1998 00:28:53 +0000

From: pepe@pepe.com

Subject: Info Simplex restricted basis entry rule

Hello,


I'm searching for information about the "simplex method with restricted basis entry rule" (it's for inverting Feedforward Neural Networks)  What do I need?  All kind of information (the algorithm of course, internet links, demos, ....)  Thanks in advance 

VLEUGELS Peter
KHK Geel
Belgium
II 4EM5cw
peter.vleugels@village.uunet.be




 
Date: Mon, 12 Jan 1998 11:25:33 +0100

From: "M. Zwaal" <mzwaal@wins.uva.nl>

Subject: LP-relaxation NP-complete?

Hi,


I know that integer LP problems belong to the class of NP-complete problems. Can anybody tell me if this is true for the LP-relaxation (normal LP) as well? If so, is there a quantitative (or other qualitative) argument for solving the LP-relaxation instead of the ILP? 

Thanks in advance,


Martin.




Date: 12 Jan 1998 17:20:54 +0100

From: Dmitrii Pasechnik <dima@duti515a.twi.tudelft.nl>

Subject: LP-relaxation NP-complete?

LP is polynomially solvable - pick up any recent book on linear optimization; e.g. (the one by my bosses): 


"Theory and Algorithms for Linear Optimization: An Interior Point Approach" by C. Roos, T. Terlaky and J.-Ph.Vial, Wiley, 1997,
ISBN 0471 95676 7


Dmitrii



 
Date: 6 Jan 1998 12:17:21 GMT

From: "Troost" <Troost@glo.be>rr;

Subject: Lp distribution problem

I am looking for an lp distribution or location problem for maths. It has to be a realistic one. Therefor I 'll ask if someone can help me. An MPS file will not satisfy so i am asking for a complete one ( ev. + solution)  if ya can help please answer or mail at Troost@glo.be 

THNX



 

Date: Tue, 06 Jan 1998 13:48:19 -0500

From: Paul Na <:paulna@uga.cc.uga.edu>

Subject: Absolute Value

Dear Friends:


Does anyone have some explanation or references to convert the absolute value objective function into equivalent LP format?  Thank you. 


Paul Na, University of Georgia.




Date: 6 Jan 1998 19:13:58 GMT

From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)

Subject: Absolute Value

I assume you mean


         min  max{ |f(x;a)|  x in X } with respect to a ?

in this case use the equivalence


        |b|<=c  iff -c <= b <= c


here this gives

             -eps <= f(x;a) <= eps for all x in X  (*)

Now minimize g(a,eps)==eps with respect to a and eps under the constraints (*)

If X is a finite set and f(x;a) linear in a, this is an LP.


hope this helps

peter





Date: Tue, 06 Jan 1998 20:33:45 -0500

From: Dale A Robertson <76312.3057@CompuServe.COM>

Subject: Absolute Value

A standard trick to incorporate absolute value is to write  x = y -z (x free, y,z >=0) and to minimize y+z.



~{:-) or in current vernacular {:-)~



 
SCI.OP-RESEARCH Digest     Mon, 5 Jan 98 Volume 5: Issue  1



Date: 17 Dec 1997 11:25:23 GMT

From: squetzal@I_should_put_my_domain_in_etc_NNTP_INEWS_DOMAIN (Lina Maria Goncalves Dos Santos)

Subject: FLP

Hello.
  I am using FLP program to solve a problem, but I am having troubles with
the way of declaring variables that can assume only 0 or 1 value.
  Can someone please give me a hint on it ?



                          Thanks in advance



Crawl back to  front page.