Date: Thu, 10 Dec 1998 20:41:21 GMT
From: ch_greiner@yahoo.com
Subject: Mixed IP solver
Is there a website from where I can download a routine (preferably in C/C++)
for solving a Mixed Integer Program ? It will be helpful if I can download
the source code too. Thanks. If I am happy with it, I am willing to pay for
it after a trial period.
-CG
Date: 11 Dec 1998 11:51:14 GMT
From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Mixed IP solver
If your problem is linear, then lpsolve will help you.
see http://plato.la.asu.edu/guide.html
hope this helps
peter
Date: Fri, 11 Dec 1998 07:34:26 -0700
From: Hans D Mittelmann <mittelmann@asu.edu>
Subject: Mixed IP solver
Hi,
check http://plato.la.asu.edu/guide.html#LP for free software and check the LP-FAQ (link further down on the above page) for commercial codes. As you probably know, commercial typically means no source.
Hans Mittelmann
Date: Sun, 13 Dec 1998 18:05:11 +0000
From: Sandman <Sandman101@nightmail.com>
Subject: Mixed IP solver
Old hat now and not C but there is a complete set of Linear and Integer
programming source code in
What is more, the code actually works since I implemented it some years ago.
Hope that helps
Date: 18 Nov 1998 09:16:14 GMT
From: hillsp@cs.curtin.edu.au (Steve Hill)
Subject: Lifted Cover Inequalities
Hi,
With the availability of shareware to solve ILP's, I was wondering if there is also source code available for generating lifted cover inequalities. Ultimately I'd like to program the method of Gu, Nemhauser and Savelsbergh(1995) "Lifted Cover Inequalities for 0-1 Integer Programs : Fast Algorithms" but at the moment am having a little difficulty with their algorithm.
thanks for your help,
Stephen
Date: 9 Sep 1998 09:22:00 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: Non-Linear Programming, for Integers
I nowhere implied the quoted are trival applications. But, quite frankly I have not a clue what they are. They do not enter my life of scientific computing!
Paul
Date: 10 Sep 1998 10:15:03 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: Non-Linear Programming, for Integers
Perhaps you should clarify what it was that you were denying.
It seems to me that you denied using Emacs, Linux, GCC, etc.
Without a clue regarding Emacs, Linux, or GCC, it would seem dishonest
to deny use of "etc."
Linux and GCC have entered my life of scientific computing.
Emacs, Linux, and GCC are distributed as both source code and as executables.
I do RBFNN, NLP and MONLP and have not seen any linking to these. I only assumed these were heavy duty programs as claimed!
Paul
Date: 5 Sep 1998 05:34:43 GMT
From: cram@csee.uq.edu.au (Colin Ramsay)
Subject: Non-Linear Programming, for Integers
G'day all,
I'm looking for a public-domain package that will solve some non-linear optimisation problems where all the variables and coefficients are integers. I've had a look at the FAQ, but it wasn't much help.
Anyone know of anything that might fit the bill?
Try Prof. Robert Fenton at the University of Toronto. A paper was published some time ago that had mixed integer, discrete and continous variables. It should collapse to just having integer variables I would think.
Paul Birke, Elelctrical Engineer in Guelph, ON CANADA
PS There is also Prof P. Hajela at the Rennsselaer Polytechnic Institute in Troy NY USA
Date: Sat, 05 Sep 1998 13:13:45 GMT
From: Paul Victor Birke <nonlinear@home.com>
Subject: Non-Linear Programming, for Integers
Dear Colin
The paper I referred to is:
Fu,J-F, Fenton, R.G, and Cleghorn, W.L., "A MIXED INTEGER-DISCRETE-CONTINUOUS PROGRAMMING METHOD AND ITS APPLICATION TO ENGINEERING DESIGN OPTIMIZATION", Eng. Opt. Vol 17 pp.263-280 1991
I have Prof. Fenton at 416.978.3043 and the 416 might now be 905
You should go to UoT and look up Robert and or William Cleghorn. Robert may be retired but I think Bill is still there. Fu last time I talked to them was a High School teacher in Toronto.
all the best,
Paul
PS I have tried to modify my direct search method but failed. I think Integer Programming is very tough. The answer for the failure is as follows, at least the major hurdle. ==> There is a diagram in a book by Richard L. Fox: Optimization Methods for Engineering Design 1971 page 250 fig 5.3 says it all for me.
Date: Sat, 05 Sep 1998 12:43:37 -0700
From: "Hans D. Mittelmann" <mittelmann@asu.edu>
Subject: Non-Linear Programming, for Integers
Hi,
if you learn about a free-for-research package, please, let me know! Mostly you have to pay some fee for codes that can solve problems larger than a few variables. See, for example, the following link and contact its author:
http://www.mcs.dundee.ac.uk:8080/~sleyffer/
I could not agree more!!!
Some of us has spent a goodly part of our lives and energies on our codes. They should indeed be worth something. We should not be paid at an equivalent low wage of these types of efforts. Software is a hard process especially since so must testing is involved. Little understood by most unless one has done it first hand!!
Frankly I am sick of the various people asking for very serious code for free.
There is obviously no conception of the intellectual effort and hard work that goes into such codes.
Paul Birke, P. Eng.
Guelph IN CANADA
Date: Sat, 05 Sep 1998 18:10:19 -0700
From: "Hans D. Mittelmann" <mittelmann@asu.edu>
Subject: Non-Linear Programming, for Integers
Hi again,
a non-free program you may already know about is http://titan.princeton.edu/MINOPT/minopt.html
yoy may ask: Peter Roosen roosen@telemann.ltt.rwth-aachen.de> for a genetic algorithm.
I'm not aware of any MINLP code that is in the public domain.
Here's an old posting of mine on MINLP that contains references to some web sites and papers:
The intellectual effort argument is spurious. Intellectual effort is not worth more or less than other effort.
How did you live whilst carrying out the effort? I was supported by the public and/or a business for many years while doing such work. As scientists/engineers/mathematicians we stand on the shoulders of giants and should be prepared to support those preparing to stand on us (assuming we have in fact made any contribution).
A secret technique is no better than magic. I don't pay magicians to do my optimisation etc.
It follows that 'serious codes should be public domain' has some justification.
Robin Becker
Date: Sun, 06 Sep 1998 12:30:34 GMT
From: Paul Victor Birke <nonlinear@home.com>
Subject: Non-Linear Programming, for Integers
Robin Becker wrote: .......
Well some of us do this for a living and like to think it is worth more than perhaps that of a gas station attendant!!
I did this work on my own time when I was an R&D engineer for Westinghouse. (I was and am deeply interested in the subject of Nonlinear Programming and Multi-Objective NLP. I have developed original codes for both.) Later they supported what I had initially achieved which was just window dressing and test proving.
I very much agree here and in this one case I am indebted to researchers at McMaster University and to some gentlemen in Israel! But I find it most difficult to give away what I have. Part of my intellectual coinage as it were!
Some stuff sure looks like magic! Usually magic in more in the eyes of the observer. You don't know what is exactly behind what you are looking at!
I don't see how the "public" per se, can pay for it!
Robin, your comments are very good,
thanx Paul
Date: 06 Sep 1998 10:35:50 -0400
From: David Bakhash <cadet@bu.edu>
Subject: Non-Linear Programming, for Integers
Consider all the great things that have come about from painstaking efforts that are available to you for free (e.g. Emacs, Linux, GCC, etc). Surely you have used several of these things. Please don't claim that you have risen up to your pedestal in the clouds without the use of such things.
right now I am a student. I do my best to develop new things, and I would be happy to let anything useful go to the public. I have found that when your hands are open in giving, you tend to receive more too.
dave
Date: Sun, 06 Sep 1998 08:40:00 -0700
From: Hans D Mittelmann <mittelmann@asu.edu>
Subject: Non-Linear Programming, for Integers
Hans Mittelmann
Date: Sun, 6 Sep 1998 11:09:22 -0700
From: "Brien Alkire" <brien@alkires.com>
Subject: Non-Linear Programming, for Integers
Aren't you being a bit harsh? Obviously asking for a free package to solve
general integer programs efficiently is asking for too much. However, I'm
sure that many people post such requests because they have a practicle
application that needs to be solved and the individual may have no concept
of what they're asking for (they may come from different fields).
Those of us with an appreciation for the difficulty should simply educate the requestor of the difficulties rather than flame them. Perhaps some of these individuals will gain an interest and contribute back to the field.
Brien Alkire
Date: Sun, 06 Sep 1998 21:14:03 GMT
From: Paul Victor Birke <nonlinear@home.com>
Subject: Non-Linear Programming, for Integers
David Bakhash wrote:
all the best,
Paul
Date: Sun, 06 Sep 1998 21:27:37 GMT
From: Paul Victor Birke <nonlinear@home.com>
Subject: Non-Linear Programming, for Integers
Brien Alkire wrote:
***********************************************************************************************************
I am surprised my comments have stirred up so much interest. You will notice you have to pay Mr. Gates for his wonderful codes and so we should. Software is costly to make. It takes a lot of time just to do the researching to get a workable algorithm if you are developing orginal code. Let alone write bullet proof stuff!
Clearly the comments so far show a lack of appreciation for what software specialists are doing and seemingly count for little in society.
Paul Birke, P. Eng. NN Researcher in Guelph ON CANADA
Date: Thu, 11 Dec 1997 22:50:50 +0100
From: "John Håkon Husøy" <jhusoy@online.no>
Subject: Underconstrained linear equations with constraints on the solution vector
Hello,
while speculating on data compression problems, the following problem has popped up:
Given the linear equation
Ax=b
which is underconstrained, i.e. we have infinitely many solutions. However, I want to impose constraints on the solution vector, x, so that, for example, each element in x is allowed to assume values in a finite set S={s1, s2, ...., sK} or in another case any value given by an integer times a specific, selected value, delta.
If anyone has come across this type of problem and have any directions for its soulution, please contact me!
Sincerely,
then take the objective function z == 0 and minimize with respect to x . If you succeed in making the f_j linear functions, then you would have a integer linear programming problem for which there are ready to use solutions, see http://plato.la.asu.edu/guide.html#lp .
Otherwise, you have to combine the branch and bound techniques from (M)ILP with a nonlinear optimizer, you should however be aware of the fact that there may be no solutions at all. a_11 x_1 + a_12 x_2 = b_2 is underconstrained, as you name it, but the line defined by this equation does not necessarily have integer points on it.
hope this helps
peter
Date: Fri, 12 Dec 1997 08:45:41 -0500
From: "W. R. Smith" <See_My_Sig@somewhere.org>
Subject: Underconstrained linear equations with constraints on the solution vector
A quick thought:
How about expressing the general solution in terms of a particular solution plus a linear combination of a null-space basis? Then the number of free parameters is n - rank(A). You might be able to work with these.
Date: 20 Jun 1997 07:54:55 GMT
From: mr844345@cs.nthu.edu.tw (mr844345)
Subject: Verify Optimality for ILP??
I have seen the category file in the MIPLIB, there are some problems have
solutions that have been verified, and others have not.
The question is:
How to verify a given solution's optimality?? Since theoretically, to verify a solution is as hard as to solve it. If it is not sure that a given solution is optimal, how can one guarantee a verification is correct??
The ones that have a verified solutions have actually been solved (the hard part), which usually means that the branch and bound tree has been completely covered.
The problems that have a solution are those for which a feasible solution has been found, either by a heuristic of as part of a branch and bound, but where the enumeration has not been completed and the solution therefore not has been proven optimal.
Arne Stolbjerg Drud
Date: 18 Jun 1997 10:21:56 -0500
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: solving highly constrained integer problems
--
Mike hennebry@plains.NoDak.edu
Date: Fri, 20 Jun 1997 14:10:20 +0200
From: Arne Stolbjerg Drud <adrud@arki.dk>
Subject: solving highly constrained integer problems
When you say that the model is highly constrained you probably mean that there are very few feasible integer solutions. However, there may be very many feasible solutions to the LP relaxation that is used by the Branch and Bound algorithm. You may need at 'tighter' LP formulation, i.e. a formulation where the feasible space for the relaxed LP is not much larger than the convex hull of the feasible space for the integer solution. Much work in Integer Programming recently has been on how go formulate the best tight LP.
Anyone know of a shareware or public domain IP solver for the case where all co-efficients are integer?
This particularly includes problems where the co-eff matrix contains only 0/1/-1 and is unimodular *but* the problem can't be formulated as a transportation/min-cost/assignment/shortest-path etc problem. The problem has 1K-10K variables, 100 - 5K eqns; matrix approx. 1% dense.
Alternatively if you know of a method to map the above type of problem to some network solver please let me know.
BTW The 0/1 IP solvers I tried aborted or took too long; I'm reluctant to pursue that route.
Email me at adi@aptix.com if you can help. Thx much.
Date: 18 May 1995 12:56:30 GMT
From: ricardo@isr.uni-stuttgart.de (Ricardo Esparta)
Subject: [Q] Literature on MINLP using B&B
Could anybody indicate literature on MINLP using Branch & Bound? (all
I've found are MILP using B&B and MINLP using Benders generalized or
outer approximation).
Is the reference on the FAQ ("Constrained non-linear 0-1 programming"
by Hansen, Jaumard, and Mathon, ORSA Journal on Computing, 5, 2,
Spring 1993.) OK? I've already ordered a copy of the article but I
haven't found it in the engineering index!
Please, answers to my email (I'll sumarize the mails and post them to the group). Thank you.
Ciao, Ricardo., Ricardo Esparta, ISR - Universitaet Stuttgart, 70550 Stuttgart, Germany, ricardo@isr.uni-stuttgart.de * http://www.isr.uni-stuttgart.de/~ricardo
Date: Fri, 19 May 1995 16:26:22 GMT
From: borchers@nmt.edu (Brian Borchers)
Subject: [Q] Literature on MINLP using B&B
The paper by Hansen, Jaumard, and Mathon is certainly interesting, but it
does limit itself to pure 0-1 problems.
One reference on a branch and bound algorithm for *mixed* integer nonlinear programming problems is:
Brian Borchers and John E. Mitchell, "An Improved Branch and Bound Algorithm for Mixed Integer Nonlinear Programs", Computers & Operations Research, Vol. 21, No. 4, April 1994, pages 359-368.
Basically, this paper described an implementation of B&B with some tricks (particularly in calculating lower bounds) to improve the performance.
There are a couple of important points to consider. First, if the continuous relaxation of your problem is nonconvex, then you should really be looking at the global optimization literature- straight forward branch and bound is not the way to go.
Second, there are a couple of other approaches that have been used on these problems, Generalized Bender's Decomposition and Outer Approximation. Unfortunately, I'm not aware of any research that has really established which method (if any) is "best".
Brian Borchers, Department of Mathematics , New Mexico Tech, Socorro, NM 87801, borchers@nmt.edu, 505-835-5813
Date: 19 May 1995 14:25:58 GMT
From: hofmeist@cantor.informatik.uni-dortmund.de (Thomas Hofmeister)
Subject: How to formulate problems as ILPs?
I am looking for references to books/articles
which do not emphasize on "how the Simplex method works"
but which mainly point out "how to transform problems into
(M)ILP-problems".
Thanks in advance, Thomas
Date: 19 May 1995 22:07:13 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: How to formulate problems as ILPs?
You might try _Model Building in Mathematical Programming_ by H. P.
Williams (2nd ed., John Wiley & Sons, 1985). It covers integer programming
(along with other optimization models), it emphasizes model construction
(vs. solution), and it has some nifty examples in it.
Paul
Date: 20 May 95 12:28:49 +1200
From: znan@waikato.ac.nz
Subject: How to formulate problems as ILPs?
Hi, there.
One of the readable and useful books on how to build a formulation of Mixed Integer Programming, in my personal point of view, is:
H.P. Williams, Model Building in Mathematical Programming, (1990, 3rd Edn, Wiley, Chichester).
In the paper "The age of optimization: solving large-scale real-world problems" (G.L. Nemhauser, Operations Research, 1 (1994) 5-13), we can also find on how to build "a good formulation" of MIP. That is the corresponding Linear Programming relaxation is a good approximation of the convex hull of integer solutions.
Thanks., N.Z.
From: Ian Boyd >boyd@bgers.co.uk< Fri May 19 10:10:39 1995
I have just seen your post on sci.op-research. To answer your first question, I can point you to the following reference:
"An Improved Branch and Bound Algorithm for Mixed Integer Nonlinear Programs", Brian Borchers and John E. Mitchell, Computers and Operations Research, Vol 21. No. 4, p 359-367, 1994.
I haven't actually got hold of this myself yet so I can't vouch for its contents.
As for the reference from the FAQ, I did get hold of this and must admit to being rather disappointed since, by 'nonlinear 0-1', the title actually refers to pure (i.e. *not* mixed) binary problems in which the (binary) variables appear nonlinearly whereas I am interested in methods for mixed 0-1 nonlinear programming.
I hope this is of some use to you.
[...stuff deleted...]
From: Nalini Dayanand
Here is a reference. I used a solver developed by these folks for
some MINLPs.
[...stuff deleted...]
From: Brian Borchers >borchers@mailhost.nmt.edu<Fri May 19 17:30:15 1995
The paper by Hansen et al. is restricted to pure 0-1 problems with no
continuous variables. It might not be of any help to you.
One paper that does discuss mixed integer NLP's is
"An Improved Branch and Bound Algorithm for Mixed Integer Nonlinear
Programs", by Brian Borchers and John E. Mitchell, Computers And
Operations Research, Vol 21, No. 4, April 1994, p359--368.
This paper disucsses mixed problems with 0-1 integer variables, convex
objective function and constraints.
If you're interested in problems where the continuous relaxation is non
convex, then you should forget about B&B and instead look at global
optimization techniques.
It's important to be aware of competing techniques- For problems of the
type that we addressed, there are two other popular approaches, Generalized
Bender's Decomposition, and Outer Approximation. I haven't seen enough
to convince me that any of the three approaches is generally best.
[...stuff deleted...]
From: Ricardo Esparta >ricardo@isr.uni-stuttgart.de< Mon May 22 15:17:49 1995
[...stuff deleted...]
As my confidence grows I'll sure use global optimization
techniques. The following literature will be considered:
Still of interest:
Ciao, Ricardo.
Ricardo Esparta, ISR - Universitaet Stuttgart, 70550 Stuttgart, Germany
ricardo@isr.uni-stuttgart.de * http://www.isr.uni-stuttgart.de/~ricardo
Could anyone tell me something about the decidability of the following
problem:
Let Psi be a system of linear (possibly non-homogeneous) disequations with
integer coefficients.
Does Psi augmented with a set of disequations of the form
x*y >= z (where z,y and z are variables appearing in Psi)
admit nonnegative integer solutions ?
I think this is better known as quadratic integer programming.
It is a simplified version however, since there is no objective function
to be minimized.
I am just interested in the decidability of verifying the existence of
any nonnegative integer solution. Actually, I do not even need the
solution itself.
If Psi is homogeneous or the non-homogeneous disequations are all of
the form
x >= b (for some variable x and constant b)
then the problem can be decided in polynomial time.
What about the more general problem, admitting also disequations
of the form x <= b, together with the nonlinear constraints.
Is this problem decidable?
Can anybody provide some hints and references to literature?
Thank you,
I am looking for any information (Web-pointers, articles, books, etc.)
about combining branch-and-bound algorithm with cutting planes
(also known as branch-and-cut algorithm) for my Masters Thesis.
Thanks!
Juha M{ntysaari
Juha M{ntysaari, Research assistant, Systems Analysis Laboratory,
juha.mantysaari@hut.fi , Helsinki University of Technology, Finland.
Tel. 358-0-4513065, URL: http://www.hut.fi/HUT/Systems.Analysis
Date: 2 Jun 1995 17:57:20 +0100
Bob Daniel rcd@dashbh.demon.co.uk Phone:+44 1604 858993 Fax:+44 1604 858147, Dash Associates, Blisworth House, Blisworth, Northants NN7 3BX, UK
Thanks for any info.
Raju Balakrishnan
I'm using lp_solve to solve a MILP (branch & bound) with ~ 100
binary variables. After one solution is obtained, the right-hand
side of the constraints (i.e. b in A*x <= b) changes and i
re-solve, i need to do this continuously. The change in b is minor,
the new b is just the previous one shifted down one row (a new data
point is added and the oldest one is dropped). So the new solution
should be very similar to the previous one and one could drastically
reduce solution time by starting to solve from the previous solution
rather than starting at the top of the b&b tree again.
I was wondering if anyone has experience with this in lp_solve specifically
or in another solver and would appreciate any pointers/references.
thanks, saurabh
Date: 15 Jun 1995 23:09:23 -0400
" . . . The change in b is minor . . . So the new solution should be very
similar to the previous one".
In MILP, small changes in the right-hand-side can cause mammoth changes in
the solution. I don't think any warm-starting approach can be of great
help.
Milt Gutterman
Date: 16 Jun 1995 20:42:29 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: warm-starting MILPs in lp_solve
If you delete one constraint and add one new constraint, you may make a
node previously fathomed as infeasible become feasible. I don't think
you'll be able to avoid restarting the search at the root of the tree. If
you previously optimal solution remains feasible (albeit possibly no longer
optimal), you can use its objective value as the initial incumbent in your
next b-&-b search, and perhaps prune the tree more quickly on subsequent
passes than on the initial pass. If the previous optimal solution is no
longer feasible, depending on the nature of your problem you may be able to
diddle it slightly to get a feasible solution and use that as the initial
incumbent.
Paul
SCI.OP-RESEARCH Digest, Mon, 26 June 95 Volume 2: Issue 26
Date: Mon, 19 Jun 1995 22:30:56 GMT
if x=1
where x is a 0-1 variable
Any hints or pointers would be appreciated in formulating the above in
the 'least' amount of constraints as possible. Thank you in advance.
--
------------------------------
Date: 20 Jun 1995 10:32:06 +0100
BUT, if y really is the sum of other variables then this might not
be the best way. Searching for the 'least' number of constraints is
not necessarily the best way of formulating MIPs. See Williams' book
for a nice easy explanation.
--
------------------------------
Date: 20 Jun 1995 21:41:36 GMT
y=0 or 1 (1)
Good Luck!
------------------------------
Date: 20 Jun 1995 13:17:29 GMT
y <= 1 - x
to achieve this.
Vishy Visweswaran
--------------------------------------------------------------------------
Date: 21 Jun 95 19:22:27 +1200
x + y <= 1,
where x=0,1; and y=sum y_{j}, y_{j}=0,1. ?
-N.Z.
------------------------------
Date: Tue, 20 Jun 95 15:33:24 GMT
Gordon Sande
___________________________________________
Date: (null)
Please, be aware of the fact that, in integer programming, "least" amount
of constraints does not generally imply "easier to solve"; often it is
the exact opposite!
Fabio Schoen Assoc. Prof. Operations Research
------------------------------
Date: Sun, 23 Jul 1995 18:52:47 GMT
------------------------------------------
Date: 3 Aug 1995 10:57:24 GMT
I'm a young researcher and I'm supposed to write a parallel
MIP solver. To earn some experience in this field I began
writing a sequential B&B solver, as described by Fletcher's
"Practical Optimization".
All the strategies I've tried till now are quite differents, and
a bit rough, but nevertheless the behaviour of the solver seems
to be constant; a good incumbent is found after the first steps,
and usually the optimal integer solution soon follows.
The bad news is that the solver spends the remaining time (usually at
least 50% of the total computing time) expanding and pruning the rest
of the Search Tree, without any hope of getting
any better choice. In other words, it wastes time and effort!
In one case the situation was peculiarly odd:
solving the bm23 test problem, available from netlib,
my own solver has found the optimal solution as the
first incumbent, after only 15% of the total execution time;
and then it has spent the remaining 85% fixing variables
of the unexapanded nodes, just to fathom them in the following
stage. Should I have stopped it after, say, a fixed (and limited)
number of steps, I could state I have written an ultra-fast
MIP solver!
My question is quite simple: knowing a very good incumbent,
is there a way to get rid of the unexpanded nodes in the search tree?
Is there a good strategy to clean up the pending subproblems,
better than the well-known 'Bound Phase' described in
any textbook ? Or, stated with different words, is there any point in computing a good incumbent, if after all I still have to traverse a
wide part of the Search Tree?
Please leave me a note, or even a word of faith.
daniele rizzi -> d.rizzi@lpac.ac.uk
ps. I know August is NOT the best moment for asking for advice...
Date: Fri, 04 Aug 95 11:22:14 GMT
To point out the obvious, if you are looking for a proven optimal solution then you have to go on to explore the tree usuing the best IP solution you have found so far as a cutoff. It may be possible to tighten a bit at each outstanding node or use extra fathoming criteria.
(I hope this counts as a word of faith).
Bob Daniel rcd@dashbh.demon.co.uk,Dash Associates, Blisworth House, Blisworth, Northants NN7 3BX, UK
Date: Sun, 6 Aug 1995 18:19:27 GMT
The crux of the matter is what you mean by "knowing a very good incumbent". If you know that it is the very best possible incumbent, then you are done. If you know that it is "a very good incumbent" in some quantitative sense, then you may be able to use that knowledge to prune branches from the search tree even if you do not have a better solution with which to fathom them. Pruning a branch does not require that you have something better, just that you know that it exists. If all you know is that your solver usually or always produces a good initial solution, then more branch and bound is your only choice if you want a known optimal solution. I'm surprised a parallel solver let you keep fifteen percent.
Mike hennebry@plains.NoDak.edu
"Wednesdays I feel better, just for spite." -- I. Forget
Date: 10 Aug 1995 21:45:24 GMT
That is just the way B&B solvers work: they expend a large amount of time to proving that the solution found early is the best one. Prunning
better your search tree depends on the kind of problem are you solving.
For example, if it is a scheduling problem you can make use of the
planning cuts sugested by Applegate and Cook, the logical inferences
proposed by Raman and Grossmann or the task intervals proposed by
Caseau and Laburthe.
Marcio Dutra
Date: 30 Aug 1995 18:46:36 GMT
Michael Daskal.
Date: 1 Sep 1995 23:25:10 GMT
Youfeng Wu
Date: 5 Sep 95 09:35:09 CDT
Also, good commercial codes have various algorithm controls, that can be used when it's difficult to find even that first feasible solution in an
ordinary Integer LP problem, and might be highly effective in your case.
You described your problem as rostering, but I'm not quite sure what that might be in practice. If it fits one of the standard OR problems classes such as set-partitioning, you might look into the literature that covers it; heuristics abound. Also, if you can reformulate, such as with
Special Ordered Sets, a commercial LP code might have a better chance.
Non-LP methods like Simulated Annealing and Genetic Algorithm could be considered - though they would not be able to provide a proof of infeasibility (is that a likely outcome?).
For other thoughts on solving Integer LP, which might give you some
leads for your problem, have a look at the LP FAQ, which I posted to
this newsgroup just today, or you can get it at
< a href="http://www.skypoint.com/subscribers/ashbury/linear-programming-faq.html">http://www.skypoint.com/subscribers/ashbury/linear-programming-faq.html
ftp://rtfm.mit.edu/pub/usenet/sci.answers/linear-programming-faq
I hope some of these ideas prove useful (and don't contain any speeling errurs).
John W. Gregory Applications Div Cray Research, Inc. Eagan, MN 55121 612-683-3673 jwg@cray.com or ashbury@skypoint.com 612-683-3099 (fax)
Thought for today:
Date: Fri, 8 Sep 1995 17:16:45 GMT
John
Date: 5 Sep 1995 22:01:41 GMT
Dear Colleagues :
I would like to bring to your attention the publication of my textbook
"Nonlinear and Mixed Integer Optimization : Fundamentals and Applications" by Oxford University Press, 198 Madison Avenue, New York, N.Y. 10016, (ISBN : 0-19-510056-5; List price : $75.00; 460 pp.).
This book will be available on September 22, 1995.
A brief description and a table of contents is attached.
C.A. Floudas
Date: 13 Sep 1995 04:28:05 GMT
The problem is the global minimization of the cost function.
Ideally the cost function would be minimized over all sets of
image partitions or all possible image segmentations. The
minimization is inherently a combined hypothesis testing/paramter
estimation problem. A new coding cost would be computed for each
image segmentation. Of course we can expect to find many local
minima in the problem.
This looks to me like a combinatorial optimization problem. Each
image segmentation map would represent one possible configuration.
We must find the best one in terms of the cost function. One way
to perhaps look at the problem is to assume to two states for each
pixel. These would be: LYING ON A REGION PARTITION and NOT LYING ON A REGION PARTITION. That leaves 2^(wXh) possible configurations. Where w and h are the image width and height. This is obviously a pretty heavy task.
My question is: Is there a combinitorial optimization problem
that I can map my problem to so as to look at existing research for
a solution?
Any ideas on how to efficiently compute this problem?
Also, any ideas on how to find a sub-optimal, fast solution? Parallel
implementation would be nice.
I was thinking about perhaps applying multigrid methods here.
There has been some work done on applying multigrid methods to
discrete optimization problems. This involves computing small
scale changes when deciding on large scale changes, etc. I could
have different resolutions of the image or something.
Regards,
Date: Thu, 26 Oct 1995 18:45:19 -0400
I have to transform logic statements given in Conjunctive Normal Form
[ e.g. !a or c becomes (1-A) + C >= 1 with A,C in {0,1} ]
we can consider the Conjunctive Normal Form as a 0-1 LP domain
, and the wanted Disjunctive Normal Form clauses as the feasible
solutions of the 0-1 LP.
[ e.g. (!a and b and c) is for the feas. sol.(A,B,C)=(0,1,1) ]
The number of feasible solutions may be exponential in nb of variables, but if it happens to be small, I would like to enumerate these solutions (in nonexpo time ?)
Does someone know a not-too-inefficient way to do this ?
My specific problem domain might behave relatively well with respect to linear relaxation, but I don't know how to see this.
Perhaps someone knows a better approach !?
Thanks in advance for any suggestion/reference.
Michel
------------------------------
Date: 27 Oct 1995 21:46:35 GMT
Assuming that the LP hull is not the integer hull, I doubt that fiddling
with the objective function would do you any good in the context of a
branch-and-bound solution approach, because any change to the objective function would potentially revive all nodes in the enumeration tree that had previously been fathomed on the basis of bound (rather than infeasibility). In essence, you would be starting from scratch each time you changed objective functions.
It seems, therefore, that some sort of cutting-plane approach would be your best shot. There is a primal all-integer algorithm, based on work by Young and Glover, described in Chapter 7 of Salkin & Mathur's book _Foundations of Integer Programming_. I've never used it, but let's say for the sake of argument that it solves your initial model reasonably efficiently, giving solution (A',B',C',...) [where A' is either a or !a, etc.]. Add the following constraint (where N is the number of variables you started with):
One immediate problem with this is that you can never discard one of these cuts, since to do so would introduce the possibility of revisiting a
solution already found.
Paul Rubin
Date: 24 Oct 1995 02:57:22 GMT
Date: 22 Oct 1995 10:13:17 GMT
Many thanks, Jonathan.
Date: 27 Oct 1995 08:34:15 GMT
Fabio Schoen
Date: 27 Oct 1995 11:23:55 GMT
> There was an up-to-date survey in one of the last issues of ORSA
> Journal on Computing by Pierre Hansen and Brigitte Jaumard.
being more precise..
Ciao,
--
Ricardo Esparta, ISR - Universitaet Stuttgart, 70550 Stuttgart, Germany
Date: 1 Nov 1995 13:40:13 GMT
I think that using cutting-planes methods for that weel-known problem is not the best thing to do in particular if your problems have a small size.
You can use the Davis-Putnam enumeration procedure with several heuristics. It is really easy to implement it and really efficient to find ALL solutions. Otherwise you can use the Finite Domains solver : express the relaxed problem and then enumerate over all 0/1 variables. There are freeware Constraint Programming Languages that can do that (e.g.clp(FD)). See the comp.constraints newsgroup.
The cutting-planes approach is superior in case of an integer optimisation problems.
Cheers.
Philippe
Date: 27 Oct 1995 11:23:55 GMT
Ciao,
Date: 9 Nov 95 05:49:27 GMT
Many thanks, Ron Sorli, School of Math. Sci., Uni. of Technology, Sydney
Date: Fri, 10 Nov 1995 00:10:58 GMT
An (old) reference on implicit enumeration is:
Geoffrion, AM, 1967. Integer Programming by Implicit Enumeration
and Balas' Method, SIAM Review, Vol. 9, No. 2 (April), pp 178 - 190.
You can also try some RAND Corporation reports by Geoffrion. For
example, RAND Corporation Memorandum RM-5627-PR "User's Instructions for 0-1 Integer Linear Programming Code RIP30C" contains a complete Fortran listing of Geoffrion's implicit enumeration approach. This and other RAND Corp. reports are available from the University of Sydney Fisher Library.
Another potentially useful reference to Fortran code is:
Keuster, JL and Mize, JH, 1973. "Optimization Techniques with
Fortran" (McGraw-Hill: New York).
I realise that these are old references but I don't know of any more
recent ones.
Peter Trout
Date: Mon, 6 Nov 1995 12:20:49 GMT
Is it possible to extract multiple solutions from 0-1 LP.
With LP this can be done by looking at non-basis variables
equal to zero, or something like that. Is this also possible with 0-1 LP ?
I am using lp_solve at the moment, but would like to get at
least two or three solutions.
Thanks in advance
Berend Reitsma csg676@cs.rug.nl
Date: 7 Nov 1995 23:59:14 GMT
Note that such an extra constraint doesn't work in each case. E.g. if you
have an assignment problem (like assigning n jobs to n machines to minimize total time of work) you will get in the optimal solution exactly n variables =1 and the rest =0. No matter if there is one or more optimal solutions, the variables always sum up to n. I think that in such a case several multiple optima can be found by forcing a variable which was equal to 1 in one of optimal solutions to be zero and resolving the problem.
Regards,
Przemyslaw Kowalik
Date: Fri, 10 Nov 1995 10:55:30 +0000
Actually, it's just a matter of writing a different constraint. Imagine
that you have a set of binary variables Xi and want to write a constraint that excludes a certain combination of values from occuring. The constraint can be written as follows:
Sum(i \in A, Xi) - Sum(i \in B, Xi) <= Card(A) - 1
where A is the set of i for which Xi = 1
You can easily check that this constraint can exclude _any_ specific
combination defined by sets A and B.
Hope I have been of help
Veniamin Dimitriadis
Date: 10 Nov 1995 15:01:39 +0100
To force a given solution out of a 0-1 LP problem, without writing
special purpose code, the technique is using what is called integer
cuts, I believe. At the moment I seem to be unable to find a
reference, but there should be some out there.
Such an integer cut are formulated as an additional equation to the
model, as described in an earlier posting (I've lost the name, sorry).
The equation should include all the binary variables in the model, and
force this exact combination of 0s and 1s to be illegal. If your
model has N integer variables y(1) to y(N), and y0(1) to y0(N) is a
set of constants describing the solution you want to exclude, you
should add the equation:
sum(i=1..N,(y(i)y0(i) + (1-y(i))(1-y0(i)))) <= N-1
The equation adds together the term y(i) for y0(i)=1 and (1-y(i)) for
y0(i)=0. The moment at least one of the variables change from the
values of y0, the equation is satisfied. This can then be repeated to
exclude other sets of y also. Note that the y0(i)'s have to be
constants for this to remain MILP.
I hope this helps someone, if there is questions, just drop me a
mail...
-Harald
Date: 11 Jan 1996 02:20:26 GMT
Hi. As I'm not an optimization guru, I wonder if someone could give
a little info on a problem I'm working on. The basics of the problem
is that I have a whole bunch of "bits", as it were, which can take
the values 0 or 1. There is some complicated cost function on the
bits, and I need to find which set of bits to set to one to minimize
the cost. The cost function does not have a closed analytical form,
and must be evaluated after making a selection of bits to turn on.
It's also really expensive to evaluate, which I think makes simulated
annealing impractical.
Anyway, my basic questions are 1) does this map on to a "standard"
problem on the field, i.e., I need some keywords to search the
literature, and 2) does anybody know if there's a particular heuristic
which works well on this type of problem?
Thanks.
Date: 18 Jan 1996 21:46:25 GMT
Without more information on the mathematical structure of the cost
function, all you can do is select the best one that you have
evaluated. If you can afford to do them all, you get the optimal
answer. By sampling fewer bit patterns, you are taking your chances
with probabilities.
If there are some monotonic relations (some sequence of bit patterns
that can be guaranteed to have increasing costs), then you're in a
situation much like the Branch and Bound of Integer Programming. You can trim the search space by cutting off obvious losers.
The more you know about the theory of your cost function, the fewer bit patterns you'll have to evaluate on the way to your optimum. Your
tradeoffs may vary.
Good luck.
Date: 28 Jan 1996 17:27:34 GMT
I was wondering if anyone was aware of reoptimizing techniques for 0-1 integer programming problems. Specifically, given a current optimal solution of a 0-1 integer program (obtained by say, a branch and bound procedure), is there a way to obtain the optimal solution when exactly one constraint is added without having to resort to branch and bound again ?
I have a paper by Geoffrion that appeared in Management Science in 1977. Has any work been done since that deals with the above question ?
Any pointers will be greatly appreciated.
Thanks.
Gautham Vemuganti.
Date: 24 Jan 1996 16:36:39 GMT
I'm looking for some implemented code of the Balas-Martin pivot and complement heuristic, so if you have some please tell me.
CU
Date: Wed, 24 Jan 1996 12:21:53 -0500
-Craig '
Date: Thu, 01 Feb 1996 00:25:00 -0800
Prof. R. Trippi
Date: 31 Jan 1996 13:47:36 GMT
That can't be so easy as you describe,
because
Mechthild Stoer
Date: Thu, 1 Feb 1996 11:24:51 +0000
Won't do, I'm afraid. Consider the (never seen) descendents of nodes
that were cut off.
Bob Daniel
Date: 1 Feb 1996 21:45:33 GMT
If you believe that the previous solution may contain information about the next solution, you can do some snooping and force some of the variables to be 1.
This all forces you to re-enter the branch-and-bound tree from scratch, but without selective variable fixing, I don't think there's another way.
First...
This summer I plan to teach an introductory graduate course
in Integer Programming, worth roughly 1.5 credits. I was
wondering if I could get some feedback on (a) what you might
consider an appropriate mix of topics, given that it's only
about half a semester's worth of time, and (b) what are some
decent introductory texts that I could recommend to students ?
I do plan on making up instructional notes of my own based on the
material I finally choose to cover, so the texts would probably
be used for supplementary reading (and for me to prepare my material).
Second...
I have an identical request as the one above, except that I ask you to
substitute Dynamic Programming for Integer Programming in the previous paragraph :-)
Thanks muchos for any feedback. You could either post to
this newsgroup or send me e-mail - either way is fine.
--jr--
Date: Wed, 31 Jan 1996 12:08:17 -0800
Significantly greater improvement has been achieved, however, by designing
a TS method which directly undertakes to exploit the fact that 0-1 solutions
are found at extreme points, without relying on the Pivot & Complement
choice rules. This new approach succeeds in obtaining optimal solutions
to all of the 57 problems from the set of benchmarks established by Drexl [3],
compared to the P&C heuristic which only obtains optimal solutions in 20 of
the cases. See Lokketangen and Glover [4,5]. This method has also been used
as a sub-problem (scenario) solver in a general tool for solving mixed
integer (0,1) multistage stochastic programming problems by use of the
progressive hedging algorithm. See Lokketangen and Woodruff [6].
References:
(Paper copies of the papers I'm involved in can be ordered from me.
Soon (hopefully) they will also be directly available on the WWW)
Paper [6] can be retrieved from
http://www-gsm.ucdavis.edu/~woodruff/home.html
)
Yours Truly
Arne Lokketangen
Date: Sun, 18 Feb 1996 18:28:39 +0100
I would be grateful if anyone provides pointers and references regarding the use of mixed integer programming in forest harvest planning and scheduling. Does anyone have experiance of using mathematical programming for long term (sustainable) forest harvest planning and scheduling? I would love to hear about it. Questions like how large was the problem, what was the planning horizon, area of forest in question etc. etc
Thanks,
To: jad@si.sintef.no
Murray,A.T. and Church, R.L. "Measuring the efficacy of adjacency
constraint structure in forest planning models". Canadian Journal of
Forest Research 25, 1416-1424. 1995.
Garcia, O. "Linear Programming and related approaches in forest
planning". New Zealand Journal of Forestry Science 20, 307-331. 1990.
For LP-based systems used routinely, see for example:
Johnson,K.N., Stuart,T.W. and Crim,S.A. "FORPLAN Version 2: an overview".
USDA Forest Service, Land Management Planning Systems Section,
Washington, D.C. 1986.
Manley,B. et al. "Application of FOLPI, a Linear Programming estate
modelling system for forest management planning". Forest Research
Institute, Rotorua, New Zealand. FRI Bulletin No.164. 1991.
Manley,B.R. and Threadgill,J.A. "LP used for valuation and planning of
New Zealand plantation forests". Interfaces 21, 66-79. 1991.
Walters,K.R. "Design and development of a generalized forest management
modeling system: WOODSTOCK". In: Paredes,G.L. (ed) "International
Symposium on Systems Analysis and Management Decisions in Forestry".
Valdivia, Chile. 1994. (see also in there papers by Murray & Church,
Liley, Braier & Nautiyal, Tarp, Manley, Nelson et al,, etc.)
Hope this helps.
I'd be very grateful if someone could point me in the right direction
with the following problem:
I have a set-up whereby
I've spent a considerable time looking for info on this problem in the
usual sources, but to no avail... Any tips/pointers very welcome!
Pete Tonkin
Date: 22 Feb 1996 10:09:54 +0100
people keep posting that they need to obtain _all_ (basic) feasible solutions
to linear (integer) programs. This task is usually _not_ performed by a
standard linear program solver.
Actually, what you need in this case is a program that transforms the linear
description of a polyhedron (in terms of (in-)equalities) into a description of
the convex hull (in terms of extreme points and rays).
A varity of algorithms have been developped for this purpose. There already exist implementations of such algorithms (and I am about to contribute another one to the bunch - based on a linear program solver). If you wish to have further information on this just mail me!
Best regards
Date: Tue, 27 Feb 1996 14:31:46 -0500
Can anybody comment as to which mixed-integer linear codes can
take an objective function of the form
maximize r, where
r=min of the vector A.x,
where x is the vector of beam weights, and A is a matrix of constants.
The mixed integer part comes in because there are auxilliary
conditions of the form
B.x
I've seen a reference to XMP, though I'm not sure how to obtain it.
There is an archive news not that CPLEX is, uh, the stronger
son of XMP, if I read it right.
It looks as though lp_solve will only do an objective function
which is linear; though I'm open to ideas on how to covert it if
such is possible.
Any other thoughts, comments? Any appreciated.
If I get substantial feedback I'll post a summary.
Joe Deasy
Date: Wed, 28 Feb 1996 09:03:40 -0500
I got two responses pointing out that this IS actually a
linear objective function, i.e. the constant r can be the objective
function. One needs only add
auxilliary conditions that all the target doses by less than r.
I guess I didn't realize you could put the objective function,
which changes as the algorithm progresses, into the auxilliary
conditions.
This was pointed out to me by Jeroen J. Dirks and John Davis.
My pride is bruised a bit but this is the best possible answer
as I have Matlab, lp_solve, and the lp_solve toolbox which should
be able to handle this class of problems.
This was pointed out to me by Jeroen J. Dirks and John Davis.
Now it turns out that you might want to have only 10% of the organ
receive more than, say, dose Dc.
As shown by Langer and coworkers this can be recast as a
mixed-integer linear problem by introducing 0/1 variables,
such that the discrete variable
is 1 when the dose to that voxel exceeds Dc and 0 when the
dose is less than Dc.
Linear inequalities can then be written which put bounds on the
sum of the discrete variables. And inequalities can be written
using the discrete variables so that the voxels which are to stay
below Dc do so.
If there is any more interest in this type of radiotherapy optimization
problem I would be glad to continue discussions, including possible
collaboration if appropriate.
Joe Deasy,
Date: Wed, 28 Feb 1996 14:37:05 GMT
Date: 28 Feb 1996 04:44:37 GMT
Date: Thu, 21 Mar 1996 10:36:52 -0500
I am trying to solve an optimization problem like
the following,
Pointers to refereces are appreciated. Thanks in advance
Dennis
The kind of problems you describe are called Integer Programming
problems (IP), and in your case you have binary variables. The standard way to solve these problems is through an algorithm called branch and bound (B&B). The basic idea is as follows:
Replace the constraint that your x variables be binary with the looser
constraint that 0<= x(i) <= 1. Then solve the problem as an LP. Some
of the x(i) will probably be fractional. Pick a fractional variable
(such as the one closest to 0.5), call it x(j), and split the problem
into 2 cases: one where x(j)=1, and the other where x(j)=0. Fix x(j) to
1 and 0, and resolve the LP's (which will be fast if you use the basis
of the previous solution as a starting point). In each of these two
cases, pick another fractional variable, and split those into two cases.
This branching is commonly drawn as a tree. Continue this splitting
until you get all the variables to be binary. Often you will have to do
much less branching than the complete case, since some variables will
naturally turn out to be 1 or 0 in the LP solution.
What I just described is the "branch" part of the algorithm. The good
news is that you can often skip some of the subproblems by proving that the optimal solution can not be contained in the subproblem. If you get a solution that has binary x(i), you know that is a lower bound on your optimum solution (assuming you're maximizing). The solution satisfies your original problem, so at worst you can use that solution's
objective. Let this lower bound be z(lb). Any subproblems that you
haven't examined yet that have objectives z < z(lb) can be discarded.
That is because each time you fix a variable to 0 or 1, the objective
will always go down. (You are increasing the constraints on the problem by branching, so the objective must get worse.) Thus any binary solution resulting from branching on one of these subproblems will have a worse solution than your previous "best" solution. Each time you find a new binary solution, see if it is better (z(new) > z(lb)) than your current z(lb), and if so, remember it instead.
Anyway, in a nutshell that's how B&B works. Your example has the look of a homework problem. If your professor wants you to do it by hand, you can do the procedure I just described. If you just want the answer, any LP package can do branch and bound as one of its standard tricks. LINDO or GAMS, for example, let you define integer or binary variables, and then do this automatically. (Integer is fine, as long as you specify an upper bound of 1.)
If you want references, look in any introductory book on operations
research such as Winston (Operations Research Applications &
Algorithms), under integer programming or branch and bound.
Hope this helps,
Craig
Date: 3 Apr 1996 01:58:15 GMT
Date: 2 Apr 1996 08:37:23 GMT
I have an MINLP model
=> for Branch&Bound this means the opt. gap is 0
=> only a few _combinations_ of binaries lead to
the optimum
ANY COMMENTS AND HINTS ARE WELCOME !
Thanks !
Date: Tue, 02 Apr 96 12:43:34
Date: 2 Apr 1996 11:27:54 -0600
Make the big M's as small as possible, maybe smaller.
Find a lower bound on Ai - Yi and make it the value of MAi.
If you have an estimate of the optimum, it can be used as an additional constraint to reduce the value of MAi.
If you can find them, constraints such as Yi >= Ai + DAYi, might be
useful. DAYi is a lower bound on Yi - Ai .
--
Mike hennebry@plains.NoDak.edu
"The tighter your jeans, the more your heredity shows." -- Barbara Cooper
Date: 11 Apr 1996 01:11:22 GMT
It is well-known that Bender's Decomposition can be used to
solve some mixed integer programs (MIPs). I am wondering if there
is any recent (after 1985) paper in the literature that successfully
applies Bender's Decomposition to MIPs. I would appreciate if you could point me to some references or books or net sites.
Thanks in advance.
Zhi-Long
Date: Mon, 22 Apr 1996 14:49:27 +0200
I am searching for new references on totally dual integral systems,
especially characterizations resp. criteria to check linear systems
Ax<=b for the TDI-property.
I know about the results in the book of Schrijver (1986) and the
paper of Kabadi and Chandrasekaran (Discrete Applied M., 1990).
Date: 31 May 1996 15:41:20 GMT
min ||a-Bx||+h*||x||
Someone could help us ?.
Date: 31 May 1996 17:18:00 GMT
Let n be the dimension of x and m the dimension of a. (Sadly, it will be easier to write what follows with subscripts than in vector notation.) Introduce new nonnegative integer variables y_1, ..., y_n and z_1, ..., z_n. Also introduce nonnegative divisible variables u_1, ..., u_m and v_1, .., v_m. I claim the following problem is equivalent to yours:
If, in fact, you require x to be integer and nonnegative, just omit the z variables.
The kicker here is that you now have a mixed integer program with twice as many integer variables as what you started with. Any mixed integer programming solver should be able to solve the problem, assuming your dimensions (primarily n) are small enough.
Hope this helps.
Paul
Date: 29 May 1996 22:49:19 GMT
I am looking for a package to perform nonlinear
mixed integer optimization. The formulation has both nonlinear
inequalities and equalities. The problem size is around 50-100
variables and 100-200 constraints.
Shareware packages allowing C user-functions will be great!
Many thanks!
Bye,
Date: Sat, 15 Jun 1996 16:19:15 GMT
I'm practising and solving this problem with the aditiv
algorithm of Balas, and his results about the complexity of time don´t
satisfy me. This problem for n=32=2**5 was executed in 6 hours
aproximately in one Pentium 100 Mhz. I'm interesting to solve the
maximum number of variables about this problem.
All suggestions or recomendations about this problem, or
bibliography to see will be gratefully.
Regards. I hope your mail or news.
Alberto Caprara, Matteo Fischetti and Paolo Toth: 'A heuristic algorithm for the Set Covering problem'. This is published in the Proceedings of the 1996 IPCO, held in Vancouver.
They solve problems of up to 2500 rows and over one million columns in the A-matrix.
RJ
Mike
Date: Fri, 28 Jun 1996 17:07:19 -0400
Hi,
I need to minimize a function f(x), with the constraint that x is
discrete, that is x can take only a set of predefined values?
As an example:
There are no other constraints on the elements of the vector x.
I have worked with optimization of continuous functions, but have never worked with integer optimization. Can you help me?
Thanking you in advance,
Any good textbook (e.g. Williams' Model Building in Mathematical
Programming) should have a fuller description of SOSs, and why in your problem they are a lot better than using binary variables.
Hope this helps.
Date: 2 Jul 1996 21:45:35 GMT
Paul
Date: 3 Jul 1996 10:42:01 -0500
Date: 8 Jul 1996 11:52:00 GMT
your help will be really appreciated..
Several problems have been deleted, and new ones added. Also, there is now information describing the structure of the constraint matrix for each problem.
A technical report explaining these changes can be accessed via this page. Also, the older problems are available through this page.
Date: 28 Aug 1996 19:52:33 GMT
We would like to know whether there are any extensive reviews or
comparative studies of discrete optimization methods and results of
their application on cases of scheduling, TSP or other NP-hard
problems.
Specifically, we are interested in either integer programming based
methods such as Langrangian relaxation or/and non-integer programming
types such as tabu search, genetic algorithms, simulated annealing,
etc.
We are aware of NEOS work done at the optimization center but would
appreciate any pointers to more methods with real-life test cases.
Thanks and we really appreciate it.
-Saleh
saleh@npac.syr.edu
Date: 6 Sep 1996 14:06:36 GMT
I was wondering if anyone could give me some ideas on how to handle a single
highly dense kanpsack-type of constraint of the form:
$$\sum_i \sum_j a_{i,j| X_{i,j} \leq M$$
where integer coefficients $a_{i,j}$ range in value between 20 and 200, $X_{i,j}$ are binary decision variables and $M$ is a large integer constant, say 20,000. This constraint is part of a larger MIP problem (30,000 rows and 50,000 columns).
-- Any help is appreciated
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: Thu, 10 Oct 1996 15:48:21 +0100
Does anyone out there have any introductory references to
the subject of column generation. I ama especially interested
in its application to solve mixed integer linear problems.
I would appreciate any help.
Thanks
PS Please forward any replies to my personal account as well.
Date: Thu, 10 Oct 1996 13:28:32 -0400
You might try Barnhart et. al:
"Branch-and-Price: Column Generation for Huge Integer Programs"
It can be found at http://akula.isye.gatech.edu/~mwps/cg3.ps
This paper gives a lot more references for column generation for solving integer programs.
Cheers,
I would like to thank the people that replied with respect to the above
query. I am posting my findings as someone suggested so that they can be
of help to anyone out there interested in column generation.
Again, I would like to thank all the people who answered.
Cheers
Date: 14 Oct 1996 16:46:55 GMT
sum (over i in U, j in U) x_ij <= |U| - 1; 2 <= |U| <= |V| - 2.
I want to write a subroutine in C/C++ to include these constraints into
my MIP model. If anyone has done this, please let me know how because I'm
having difficulty.
Thanks,
Date: 02 Jun 1995 09:49:17 GMT
From: diego@cantor (Diego Calvanese)
Subject: Decidability of a quadratic integer programming problem?
I already posted this question a few days ago on comp.theory, but I realized
I had a wrong reply-to address. So I give it a second try.
diego
Date: 2 Jun 1995 12:43:24 GMT
From: jamu@snakemail.hut.fi (Juha A M{ntysaari)
Subject: Any pointers to Branch-and-cut algorithms?
Hello!
From: Bob Daniel >rcd@dashbh.demon.co.uk<
Subject: Any pointers to Branch-and-cut algorithms?
Date: 6 Jun 1995 19:46:29 GMT
From: nbalak@hubcap.clemson.edu (Nagraj Balakrishnan)
Subject: Bender's decomposition
I am currently looking into using Bender's decomposition to solve a
scheduling problem. Turns out that the master problem is a multiple TSP
to which a Bender's cut is appended at each iteration of the procedure.
Clearly, using standard IP codes to solve this master problem would not
be the way to go and I am exploring alternate soluion procedures.
However, I thought this newsgroup may be a good resource to check if
anyone else has encountered similar situations and if so, how they
handled it.
Date: 13 Jun 1995 21:00:07 GMT
From: saurabh thapliyal <sthapliy@mozart.helios.nd.edu>
Subject: warm-starting MILPs in lp_solve
Hi,
From: mgutterman@aol.com (MGutterman)
Subject: warm-starting MILPs in lp_solve
saurabh thapliyal writes:
From: John Chionglo
Subject: integer programming, disjunctive constraints
Hello.
I would like to model the following into my integer program:
then y=0
else
if x=0
then y=0 or 1
y is actually the sum of several 0-1 variables
John Chionglo, P.Eng.
Research Assistant
Department of Industrial Engineering
University of Toronto
email: chionglo@ie.utoronto.ca
WWW: http://www.ie.utoronto.ca/EIL/profiles/chionpro.html
From: Bob Daniel
Subject: integer programming, disjunctive constraints
x+y<=1
Bob Daniel rcd@dashbh.demon.co.uk Phone:+44 1604 858993 Fax:+44 1604 858147
Dash Associates, Blisworth House, Blisworth, Northants NN7 3BX, UK
From: Zhi-Long Chen
Subject: integer programming, disjunctive constraints
The logical relations imply that y is a 0-1 variable too.
It seems that the following linear system can model these
logical relations:
y<= (1-x)M, where M is a big positive integer (2)
(2) implies: y<=0 if x=1, which means y=0 if x=1 due to (1).
Zhi-Long
From: vishy@engrs8.engprn.mobil.com (Viswanathan Visweswaran)
Subject: integer programming, disjunctive constraints
Since y is a positive integer (>= 0), all you need is the constraint
Vishy Visweswaran | Tel: (609) 737-4948 (Office)
Process Engineering Division | (609) 497-9454 (Home)
Mobil Research & Development Corp. | Fax: (609) 737-5047
Pennington-Rocky Hill Road | Email: vishy@engprn.mobil.com
Pennington, NJ 08534 USA | vishy@titan.princeton.edu
--------------------------------------------------------------------------
From: znan@waikato.ac.nz
Subject: integer programming, disjunctive constraints
How about the following formulation:
From: sande@haven.ios.com (Gordon Sande)
Subject: integer programming, disjunctive constraints
If you allow the coefficients to be large, you can combine constraints
with formulae that look like solutions to the Chinese Remainder Problem.
Extreme case is only one constraint with very large coefficients.
From: (null)
From: schoen@ingfi1.ing.unifi.it
Newsgroups: sci.op-research
Subject: Re: integer programming, disjunctive constraints
Date: 20 Jun 1995 11:44:03 GMT
Organization: Dip. Sistemi e Informatica - Univ. di Firenze
Lines: 28
Distribution: world
Message-ID: <3s6ca3$v38@serra.unipi.it>
NNTP-Posting-Host: schoen.ing.unifi.it
X-Newsreader:
tel: +39 (55) 4796.358 fax: 4796.363 Email: schoen@ingfi1.ing.unifi.it
Dipartimento di Sistemi e Informatica Universita' di Firenze
via di S.Marta 3, 50139 FIRENZE (Italy)
WWW home page: http://www-dsi.ing.unifi.it/~schoen/home.html
From: aa576@FreeNet.Carleton.CA (Robert Hilchie)
Subject: Master Mind as an integer program
A while ago I came to the realization that the game of Master Mind can be
expressed as a system of linear equations whose variables are non negative
integers. What I mean is several equations express the structure of the
game, and every guess yields two equations. The solutions to this system
are the possible values of the hidden code. I have actually taken real
games, converted them to equations and fed them to lp_solve, and in no
time lp_solve spits out valid solutions. So far I have not seen any
mention of Master Mind's linearity in any articles on the game.
My question is: does this linearity of Master Mind have any implications
in developing a strategy for the game?
Am I the only one who finds this intriguing?
Thanks
Rob Hilchie
aa576@FreeNet.Carleton.CA
From: Daniele Rizzi <D.Rizzi@qmw.ac.uk>
Subject: Bad behaviour in a MIP solver...
Hi all,
From: Bob Daniel <rcd@dashbh.demon.co.uk>
Subject: Bad behaviour in a MIP solver...
In article <3vqa2k$d9f@gateway.lpac.ac.uk> D.Rizzi@qmw.ac.uk writes:...
From: hennebry@plains.NoDak.edu (Michael J. Hennebry)
Subject: Bad behaviour in a MIP solver...
From: Marcio Francisco Dutra e Campos <dutra@dca.fee.unicamp.br>
Subject: Bad behaviour in a MIP solver...
To: dutra@dca.fee.unicamp.br
Hi,
State University of Campinas
Dept. of Computer Engeneering and Industrial Automation.
From: mdaskal@ulb.ac.be
Subject: Binary linear programming -powerful algorithm searched
I am trying to solve rostering problems in the following context:
If you have an algorithm which could handle this problem or if you have some suggestions to find one, please contact me. ("Branch and bound" as well as "Ballas" were inadequate.)
mdaskal@ulb.ac.be
From: ywu@gomez.intel.com (Youfeng Wu ~)
Subject: Upper Bound on the number of solutions to IP
I am searching for a method to estimate the upper bound on the
number of solutions to a given integer programming problem (IP).
I can view the IP as a closed convex polyhedron. So I basically
look for a method to esitmate the size of the enclosed space.
TIA for any lead or suggestion.
ywu@gomez.sc.intel.com
From: jwg@ceres.cray.com (John Gregory)
Subject: Binary linear programming-powerful algorithm searched
In article <424td5$sk9@aadt.sdt.com>, allanmac@sdt.com (Allan S. MacKinnon, Jr.) writes:
Behind every successful man is a surprised mother-in-law.
From: johnf@atl.com (John Flynn)
Subject: Binary linear programming -powerful algorithm searched
In article <1995Sep5.093509.25479@walter.cray.com>, jwg@ceres.cray.com says...
From: Ioannis Androulakis <androula>
Subject: New Book, "Nonlinear and Mixed Integer Optimization:
Fundamentals and Applications"
Professor
Tel. : 609-258-4595, Fax : 609-258-2391, E-mail : floudas@titan.princeton.edu
From: wareham@eleceng.ee.queensu.ca (P. Wareham)
Subject: Combinitorial Optimization/Multigrid Methods
Hi, I am working on an image coding application where I am
attempting to find a computationally efficient method of
arriving at an optimal image partition. Essentially I have
a cost function which is associated with the coding cost of
the image. The idea is to minimize a coding cost function to
find the optimum compression assuming certain parameterization
of motion between frames within disjoint image regions.
Paul Wareham
Image Processing and Communications Lab
Dept. of Electrical and Computer Engineering
Queen's University
Kingston, Ontario K7L 3N6
E-Mail wareham@vision.ee.queensu.ca
http://ipcl.ee.queensu.ca/wareham/wareham.html
From: Michel Tourn <tourn+@andrew.cmu.edu>
Subject: Enum.feas.sols of a 0-1 LP
Hi
From: rubin@msu.edu (Paul A. Rubin)
Subject: Enum.feas.sols of a 0-1 LP
If every extreme point of the linear programming relaxation is integral (which I doubt), then the problem reduces to finding all the vertices of the LP hull; that problem has been studied, and I have a few references buried in my office someplace. I do not think your case fits, though.
From: Bob Youmans <71511.3636@CompuServe.COM>
Subject: Mixed Integer Tool
I'm an analyst with Teledyne in Huntsville Alabama. Naval
Postgraduate School alumni, and I'm looking for any info on
existing branch & bound or other NLP type of tools out there in
the public/shareware domain. Thanks.
From: J C Rougier <J.C.Rougier@durham.ac.uk>
Subject: Non-linear 0-1 programming
Can anyone help me with a recent reference? My problem has an objective function which is highly non-linear, and my main interest is in the possibility of multiple local maxima. The best book that I have found in my library was written in 1979, and has tantalising references to on-going work in this area.
From: Fabio Schoen <schoen@ingfi1.ing.unifi.it>
Subject: Non-linear 0-1 programming
There was an up-to-date survey in one of the last issues of ORSA Journal on Computing by Pierre Hansen and Brigitte Jaumard.
From: ricardo@isr.uni-stuttgart.de (Ricardo Esparta)
Subject: Non-linear 0-1 programming
In article <46q5i7$vvg@serra.unipi.it>, Fabio Schoen
(schoen@ingfi1.ing.unifi.it) wrote ....:
From: Philippe Refalo <pr>
Subject: Enum.feas.sols of a 0-1 LP
Hi,
From: ricardo@isr.uni-stuttgart.de (Ricardo Esparta)
Subject: Non-linear 0-1 programming
In article <46q5i7$vvg@serra.unipi.it>, Fabio Schoen
(schoen@ingfi1.ing.unifi.it) wrote:
From: ron@maths.uts.edu.au (Ron Sorli)
Subject: 0-1 implicit enumeration algorithm
I have been looking for code to handle a (big) 0-1 LP problem.
While I have checked out the feasibility of my model using LP
packages which allow integer variables (eg. Lingo (PC) and lp_solve),
they look to be too slow to be tried on the "real" problem. Several
text books have mentioned an "implicit enumeration" approach, which
should be more efficient than the more general branch-and-bound
approach. I did find some Algol 60 code (Algorithms from the
Communications of the ACM, Algorithm 341) but nothing recent and in
Fortran or C. Can anyone help either with comments on the implicit
enumeration approach or (hopefully) working code for this algorithm?
email: ron@maths.uts.edu.au
From: Peter Trout <lptrou@mim.com.au>
Subject: 0-1 implicit enumeration algorithm
ron@maths.uts.edu.au (Ron Sorli) wrote:
From: csg676@cs.rug.nl (Berend Reitsma)
Subject: Q: Multiple solutions with 0-1 LP
Hello all,
csg676@wing.rug.nl
From: Mark <mark@uta.geo.orst.edu>
Subject: Q: Multiple solutions with 0-1 LP
I've been finding alternate optimal solutions to 0-1 MIP's for a while now. Since you are dealing with 0-1 variables, the most straightforward way to do this is, after finding a solution, say (x1,x2,x3)=(1,1,1), add a row to your constraint matrix that says x1+x2+x3 <= 2 and then re-solve. This probably isn't the quickest method of finding multiple solutions, since it will restart the branch-and-bound tree, instead of using knowledge already gained. But, it
is fairly simple, and the bookkeeping of other methods isn't worth it if you only want to get 2 or 3 solutions. If you're finding 5000 or more solutions, you'll have to get a bit more creative. Hope this helps. I've some OSL code that does this sort of thing.
From: przemko@antenor.pol.lublin.pl (Przemyslaw Kowalik)
Subject: Q: Multiple solutions with 0-1 LP
From: "V. Dimitriadis" <umeca73@ps.ic.ac.uk>
Subject: Q: Multiple solutions with 0-1 LP
On Fri, 10 Nov 1995, Przemyslaw Kowalik wrote .....:
B is the set of i for which Xi = 0
Centre for Process Systems Engineering
Imperial College
London SW7 2BY
U.K.
From: hhansen@kjemi.unit.no (Harald Nordgerd-Hansen)
Subject: Q: Multiple solutions with 0-1 LP
It seems this isn't totally clear to all people, so I'll try a general
version myself.
From: Dave Dixon <dixon@agouti.ucr.edu>
Subject: Help- optimizing a binary cost function
(sorry about the double posting - forgot the subject line the first
time.)
Dave
From: shepherd@ix.netcom.com(Roger Shepherd )
Subject: Help- optimizing a binary cost function
In <4d1rvj$lgj@galaxy.ucr.edu> Dave Dixon <dixon@agouti.ucr.edu>
writes ..... :
From: ghv@acsu.buffalo.edu (Gautham H. Vemuganti)
Subject: 0-1 integer programming and addition of a new constraint
Hi!
From: Joerg Heitmann <heitman2>
Subject: Balas-Martin Pivot & Complement
Hello,
Joerg Heitmann
From: Craig Schmidt <cs76+@andrew.cmu.edu>
Subject: Balas-Martin Pivot & Complement
The ZOOM solver that comes with the GAMS modeling system can do this heuristic. See p. 226 of the GAMS manual for more information.
From: "Robert R. Trippi" <rtrippi@ucsd.edu>
Subject: 0-1 integer programming and addition of a new constraint
If you are adding only one constraint, just save the bit-strings representing all fathomed nodes
(i.e. feasible early candidates for optimal solution) in the order they are generated. After you have solved the original problem, work backwards through your list plugging in the variable values
until you reach the first bit-string that satisfies the new constraint.
From: stoer@hal.nta.no (Stoer Mechthild)
Subject: 0-1 integer programming and addition of a new constraint
In article ....:
From: Bob Daniel <rcd@dash.co.uk>
Subject: 0-1 integer programming and addition of a new constraint
In article <311078DC.7CF1@ucsd.edu>, "Robert R. Trippi" ...
writes....:
From: hachey@stat.orst.edu (Mark Hachey)
Subject: 0-1 integer programming and addition of a new constraint
The easiest way I can think to do this is to create a vector, say B, where b[i] = x[i], and x[i] are the decision variables from your first solution. then add the constraint SUM [all i] {b[i]*x[i]} <= n - 1 (or 1 less than the number you just had). This way, the exact same x vector of 0's and 1's can not be created.
From: gunner1+@pitt.edu (Gunner)
Subject: Integer Programming / Dynamic Programming Questions...
From: Arne Lxkketangen <Arne.Lokketangen@hiMolde.no>
Subject: Some new results in the Pivot and Complement area
Some recent postings have addressed the Pivot & Complement heuristic by
Balas and Martin, and I would like to point to some recent improvements
in this area. I will start off by mentioning the work by Lokketangen,
Jornsten and Storoy [1], where tabu search (TS) is used to provide
superior guidance, (and superior results) by incorporating TS mechanisms
both in the search and improvement phase of the P&C heuristic. Then there
is the work by Aboudi and Jornsten [2], which uses the P&C heuristic
as a sub-problem solver in a TS framework.
Molde College
Molde
Norway
Email: Arne.Lokketangen@hiMolde.no
From: Junas Adhikary <jad@si.sintef.no>
Subject: Info Req: MIP in forest harvest planning and schedulig
Hello,
Junas
From: Oscar GARCIA <garcia@engref.fr>
Subject: Info Req: MIP in forest harvest planning and scheduling
From: prbt@lispstat.alcd.soton.ac.uk (Pete Tonkin)
Subject: Integer solutions to a system of equations
prbt@alcd.soton.ac.uk
From: marco@moc.math.nat.tu-bs.de
Subject: Integer solutions to a system of equations
Dear OR community,
Marco
From: Joe Deasy <jodeasy@roentgen.bcc.louisville.edu>
Subject: What mixed-integer codes can solve this?
Howdy,
Univ. of Louisville
From: Joe Deasy <jodeasy@roentgen.bcc.louisville.edu>
Subject: What mixed-integer codes can solve this?
I got some quick replies to my query:
Medical Physics
Dept of Radiation Oncology
Univ. of Louisville.
From: Irv Lustig <irv@dizzy.cplex.com>
Subject: What mixed-integer codes can solve this?
To: jodeasy@roentgen.bcc.louisville.edu
>I've seen a reference to XMP, though I'm not sure how to obtain it.
>There is an archive news not that CPLEX is, uh, the stronger
>son of XMP, if I read it right.
>
Just to clarify this a little bit. XMP Software terminated business operations
in 1994. The three principals of the company (myself, Roy Marsten, and Dave
Shanno) recommend that people look at CPLEX as a possible replacement for XMP's
products. There is no software relationship between XMP and CPLEX, except for
the fact that I've personally been involved with both companies.
From: jeckstei@rutcor.rutgers.edu (Jonathan Eckstein)
Subject: What mixed-integer codes can solve this?
Your description is still a little vague, but it seems to me
you could end up with a pretty "loose" LP relaxation. The
0/1 variables are kind of like the ones that appear in
fixed charge problems. Cutting planes might help. If you
get to the point of formulating some of these problems
and are having trouble solving them on conventional
equipment, they might make good test problems for a
parallel MIP solver (like mine).
Assistant Professor Jonathan Eckstein
From: wingate@clark.net (John Wingate)
Subject: What mixed-integer codes can solve this?
I can't help you with the mixed-integer aspects of your problem, but
the objective can be reformulated as a linear function by adding
new constraints:
Hi,
From: Craig Schmidt <cs76+@andrew.cmu.edu>
Subject: Help with Optimization Problem
Hi Dennis,
From: Dale A Robertson <76312.3057@CompuServe.COM>
Subject: mathematical programming
The fundamental reason that integer programs are difficult is that
it is a very general framework, and many intrinsically difficult
(i.e. NP hard) problems can be put into an integer program
formulation. Thus one does not expect general integer programs
to be easy to solve ever.
From: tina@unidoct.chemietechnik.uni-dortmund.de
Subject: Mixed Integer Nonlinear Problem
MINLP model formulation problem
===============================
The following features of my model formulation make it
hard to solve even simple and relatively small problems.
From: Rudolf.Vetschera@uni-konstanz.de
Subject: Mixed Integer Nonlinear Problem
Do you really need integers or are they just for the "min" constraints. In the latter case, you might also view your problem as
an NLP with non-diefferentiable constraints and solve it using some
search techniques. I once used a very straghtforward technique to
solve a probloem with min-constraints in a few seconds, where a MIP
took almost an hour. The method I used was the Hooke-Jeeves direct
search code published in: Spaeth, H.: Algorithmen fuer multivariate
Ausgleichsmodelle. Oldenbourg 1974 (I guess you can read German) The original references to the algorithm are: Hooke/Jeeves: "Direct
Search" Solution of Numerical and Statistical Problems. Journal ACM 8,
212-229 (1961) Kaupe, A.F: Direct Search. Collected Algorithms of the
ACM 178-R2
From: hennebry@plains.nodak.edu (Michael J. Hennebry)
Subject: Mixed Integer Nonlinear Problem
In article <4jqp03$pv1@nx2.HRZ.Uni-Dortmund.DE>,
<tina@unidoct.chemietechnik.uni-dortmund.de> wrote:
From: zhi-long chen <zhichen@dragon.princeton.edu>
Subject: Q: Bender's Decompsition for MIP
Dear Operations Researchers:
From: Andreas Fink <a.fink@tu-bs.de>
Subject: Q: refer. on totally dual integral (TDI) systems ?
Hi,
From: piloni@piaggio.ccii.unipi.it (Piloni Federico)
Subject: Integer linear programming
Our problem is to find the minimum af a linear multivariable function with the constrain that all the solutions must be integer and minimum in one norm.
x integer
thank you
From: rubin@msu.edu (Paul A. Rubin)
Subject: Integer linear programming
I'm going to assume that a and x are vectors, B a matrix, h a scalar, '*' means scalar multiplication and ||.|| is the 1-norm. I'm also going to assume that x is not restricted in sign. If any of those assumptions are wrong, oops.
From: byrav@cs.ucdavis.edu (Byrav Ramamurthy)
Subject: Solver for Nonlinear Mixed Integer constrained optimization problem
Hi all,
Byrav
From: mcamaral@madrid.idec.es (Miguel Angel Camara)
Subject: 0-1 integer programming
I'm interesting about solving this 0-1 integer programming
problem:
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: 0-1 integer programming
Disregarding the special properties of the matrix A, this is a
straightforward Set Covering problem. There are many specialised
algorithms available to solve this problem. If you would not mind going into heuristics, your best bet is probably in
From: Michael Trick <trick+@andrew.cmu.edu>
Subject: 0-1 integer programming
Almost any technique will have problems with this due to the symmetry (work on large set covering problems generally don't have such a super-symmetric matrix). It looks symmetric enough that you can show there exists an optimal solution containing any given column. If so, then you can fix any column to 1, breaking symmetry and doubtless leading to much more effective algorithms.
From: Kumar Chellapilla <kumarc@ece.vill.edu>
Subject: Question on Integer Programming.
Kumar
From: Bob Daniel <rcd@dash.co.uk>
Subject: Question on Integer Programming.
Kumar,
Are there really no other constraints?
Assuming there are, Special Ordered Sets are probably the best way to do things. If R(i,j) are the possible values of x(i), define variables
l(i,j). Then
From: rubin@msu.edu (Paul A. Rubin)
Subject: Question on Integer Programming.
SOS's may help, but that objective function is a trifle nonlinear (indeed, nonconvex). If it is indeed separable, and assuming the set of feasible values for each variable is finite, exhaustive search should work. If it is not separable, yee-hah!
From: hennebry@plains.nodak.edu (Michael J. Hennebry)
Subject: Question on Integer Programming.
If the sets are not finite, the the solution to the example is unbounded. With "exhaustive" search, at most 20 trigonometric function evaluations are needed. In fact, the example can be solved exactly if square roots are allowed as well as +-*/ . Decagons are among the regular polygons that can be inscribed in a given circle.
From: Sami Abed <dm95ssa@brunel.ac.uk>
Subject: research in MILP...
I am looking forward to do research in Mixed Integer (Non-)Linear
programming with the integration of Logic. I wonder if anyone could provide me with some references, ideas, or research (PhD) projects titles.
From: cmoore@rice.edu ( Cassandra Moore McZeal)
Subject: MIPLIB
MIPLIB has been updated and moved. Its new address is http://www.caam.rice.edu/~bixby/miplib/miplib.html
From: cmoore@rice.edu ( Cassandra Moore McZeal)
Subject: MIPLIB
I neglected to mention that this information is also available via anonymous ftp. The library and related files can be found in the directory /pub/people/bixby/miplib on the machine ftp.caam.rice.edu
From: saleh@npac.syr.edu (Saleh Elmohamed)
Subject: looking for reviews/roadmaps or comparative studies
Hi!
From: Christos Makrigeorgis <a341979>
Subject: Handling dense constraints
Hi all:
-- Thanks, Christos
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: "V. Dimitriadis" <umeca73@ps.ic.ac.uk>
Subject: Column generation references
Hi,
Veniamin
From: "J.T. Linderoth" <jeff@akula.isye.gatech.edu>
Subject: Column generation references
Hello Veniamin,
-Jeff
From: "V. Dimitriadis" <umeca73@ps.ic.ac.uk>
Subject: Column generation references
Hi again,
Veniamin
From: fsaad@ttiadmin.tamu.edu (Frida Saad)
Subject: Need help with subtour elimination constraints
I want to use the following subtour elimination constraints:
Frida.