Date: Mon, 10 Nov 1997 11:57:56 +0100
From: Jelasity Mark <jelasity@inf.u-szeged.hu>
Subject: Subset Sum variation
Philipp Gühring wrote:
The URL is: http://www.inf.u-szeged.hu/~jelasity/cikkek/icga.ps.gz
Yours: Mark
Date: Sun, 9 Nov 1997 22:18:26 +0100
From: p.guehring@xpoint.at (Philipp Gühring)
Subject: Subset Sum variation
Philipp Gühring/Sourcerer
Date: Wed, 05 Nov 1997 09:59:48 +0100
From: hm <johann.murauer@utimaco.co.at>
Subject: Davis-Putnam algorithm
Hi,
I am looking for an implementation of the Davis-Putnam algorithm, preferable in C / C++. (Pascal is also welcome).
I need it for demonstration and education purposes (no commercial use or product); so the implementation should be handy and without to much tricks. Performance is of (almost) no importance.
Paperware (implementation printed in books or papers) is also welcome.
Any help appreciated.
Johann Murauer
Date: Wed, 05 Nov 1997 04:47:55 -0700
you may look at OPBDP. It's in C++. compiles with g++ and has some
accompanying literature. See the links at the end of the LP-section:
http://plato.la.asu.edu/guide.html#LP
Hans Mittelmann
Date: Wed, 08 Oct 1997 20:42:39 +0200
Best regards
Kimon
Date: Tue, 07 Oct 97 01:47:17 GMT
A couple of people (including myself) pointed you towards Lagrangian
relaxation as the preferred method for solving this particular kind of problem
when you made your previous query. You have only about 20 units, which,
for a single period problem, are not too many if you want to solve them using
off-the-shelf lp solvers, even if you include transmission line transfer
limits using linear approximations such as the DC power flow, or spinning
reserve constraints. However, if you ever plan to extend your problem to
several time periods AND you have time-spanning constraints such as minimal up
or down times or ramping limits, or time-spanning costs such as warm start and
startup costs, then do not expect to be able to solve that using mixed-integer
lp solvers. Without some technique to decouple time-spanning constraints
(such as above) from system-spanning constraints (such as
generation=demand+losses, or perhaps a somewhat more accurate DC flow
approximation) the task is next to hopeless even for very small problems.
This is exactly what Lagrangian relaxation offers. If you do not have any
time-spanning constraint, then consider yourself very lucky that you can solve
your problem as n separate one-period problems.
As for techniques for casting constraints in mathematical form, I can only
suggest that you look outside of OR-specific literature. There is a lot of
creativity for this out there, but be warned that stressing this "art" to its
limit often yields formulations that are nothing but far fetched
monstrosities. Believe in simplicity, and always use critical judgment.
Date: Thu, 28 Aug 1997 17:52:31 -0600
I've long had this solution to a problem which I was able to
come up with an iterative solution to, but I'd really like to
know if it relates to Combinatorics or Dynamic Programming. I
work for an organization which creates objective exams made up
of some number of multiple choice test questions. Each question
has some number of independent classifications and I'm given a
specification which expresses the exact number of questions
needed with each of several discrete values in each of these
independent classifications.
In fact, the original formulation was for Veterinarians. They
devised a three dimensional classification: Animal Species,
Organ System and Discipline. All questions can be partitioned
into one of several groups of Species, or by the organ system
the question deals with or with the academic discipline dealt
with. Of course, people don't always write questions which deal
with ONLY one species or ONLY one organ system, etc., but each
question gets classified with ONLY ONE specific entry from each
of the three scales. The specification characterizes the exam
>from each of these three perspectives.
The problem I was presented with was to draw some combination of
items from the pool of available items to exactly satisfy the
specification. I devised a metric and an heuristic that seemed
reasonable, so that each time I needed to select some question,
I could rate each question in the pool with how well suited it
seemed to best move me toward the exact fulfillment of the
specification.
I won't bore you with a description of the specific algorithm I
devised, but it did seem to work quite well. I wondered if I was
essentially guaranteed that if some collection of items from the
pool would exactly fulfill the specification, then I was
guaranteed of finding that subset, or if a decision made early
on could come back to haunt me, but having led me into a blind
alley, thus requiring back tracking (I specifically wanted to
avoid any backtracking).
In connection with Donald Knuth's Tex algorithm for filling lines
of a paragraph with words, was the first time I came across the
term of Dynamic Programming. I attempted to read some of the
books written by Richard Bellman. All I can say is that it
seemed sort of like what I was trying to do, but I couldn't
quite understand where he was coming from. Combinatorics also
seems to deal with this sort of discrete sort of problem. It
seems like combinatorics might help in answering my question
about whether a dead end is possible, while dynamic programming
seems to offer an iterative approach and studying it.
I'd appreciate any comments, pointers or guidance you could
offer me in better understanding my little problem. I'd really
like to know what to label this with.
Thanks,
Date: Fri, 29 Aug 1997 11:59:23 -0700
I have the following problem.
A property of Al is that if I combine all m rows in Al, I get
the following,
Date: Mon, 18 Aug 1997 15:34:32 -0500
Does anyone know of existing methodologies commercial or research to
solve mixed/ integer programming problems on parallel architecures?
What i need to know is the following:
Thanks in advance,
shereef
Date: Tue, 19 Aug 1997 09:05:02 +0100
I think Dash were the first to have a commercial MIP offering, (in 1989,
on Transputers!). I personally did a port on a 4 transputer plug-in PC
board, but there was only 1 MByte per CPU, so computational testing was
confined to small problems.
We did a PVM version somewhat later, on networks of UNIX boxes to start
with, and got linear speedups on the 8 RS6K's that we had (frankly,
scaling to tens of processors is interesting in theory but not many OR
groups have that many boxes all at once).
We now have our own low overhead 'PVM lookalike', which we can use on
UNIX and Windows 3.11, 95 and NT. Again, we get linear speedup on non-
trivial problems. (By that, I tend to mean problems where it takes
several iterations to solve each LP relaxation.) People tend to use it
on several machines in a loaded office environment, so speedup is a
subjective matter.
We have worked on a couple of funded research projects and put a lot of
work into parallel MIP, so we know how to get good speedups.
IBM (OSL) and CPLEX followed, and have their own offerings.
There is a reasonable amount of research, but mainly in the pure IP
world. I can give you pointers if that would help, but the people there
concentrate on load balancing, which is not so much of an issue in large
scale MIP.
Bob Daniel
You'll probably be most interested in section 8.
I think the CPLEX people are continuing to parallelize their improvements to
the sequential version.
Regards,
-ram.
Date: 1 Aug 1997 05:34:56 GMT
Any help would be greatly appreciated.
Regards,
Marc van Dongen
Date: 1 Aug 1997 19:08:00 GMT
-- Praveen K. Murthy
Date: Thu, 10 Jul 1997 17:03:02 +0200
Hi,
I am working on a paper about routing mobile cranes.
It is a vehicle routing problem with precedence constraints,
but without time windows.
I can solve the problem for 50 jobs and 30 cranes. Using Cplex
I get a integer solution that is optimal.
The relaxation of the problem has the same value as the integer
solution. Most of the time the decision variables as integer, but some
times they are fractional. I tested 10 instances and 3 where fractional,
but the object value stayed the same.
Does anybody know why this is. Thanks for reading this.
Diego Faneyte
Date: 10 Jul 1997 20:34:25 GMT
(ILP means integer linear programming ).
However, if the problem (thus the inequalities/constraints) has special
structures, then yes, the problem may have integer extreme solutions.
Thus, yielding integer optimal solution.
(A good example is, of course, the network flow problems with integer deman/supplly).
For vehicle routing problems, you need to look at the facet-inducing constraints
of your ILP formulation and see if there are certain structures that
make the LP-relaxation yield an integer optimal solution for the instance.
Peh...
P/S For more information about this topic, you can check into
most ILP/LP texts, eg Integer and Combinatorial Optimization by
Nenhauser & Wolsey.
Date: Fri, 11 Jul 97 16:03:43 GMT
Cary
Date: Thu, 26 Jun 1997 13:17:23 +0000
There are techniques to reformulate the ILPs so that the constraints fit
the convex hull of the integer solutions better. This sometimes leads
to the better bounds, but not always.
Date: Thu, 26 Jun 1997 10:11:48 +0200
Two remarks:
Date: 21 Jun 1997 13:48:47 GMT
If yes, is it possible, toa mail me this solution ?
Date: Fri, 13 Jun 1997 09:08:46 -0700
Intuitively to me, it seems like the more integers and constraints you put
on the problem, the quicker it should solve, because there are far less
choices to choose from. On a highly integer-constrained problem, where
perhaps there might be only tens of thousands of combinations, it seems a
purely "brute force" alogrithim would be better than trying to use a linear
optimizer, because the latter takes (almost exponentially) longer when it
deals with integers.
Is there optimizers out there that are better in dealing with mostly
integers and a highly-constrained problem? Is non-liner optimization better
in this case? Is "brute force" better in this case? What optimizers would
be reccomended for these kinds of problems? We are also wanting to use an
optimizer that is multi-threaded and supports SMP. Our model is linear, but
it would be advantageous for us to use non-linear constraints in our
problems, so if non-linear worked well, it would be better.
Ian
Date: 5 Jun 1997 23:37:57 GMT
I am trying to solve a large MIP problem with binary integer variables. I
have been using GAMS with a CPLEX solver. Unfortunately, my problem has
grown from a very manageble one to one which is too large to usually even
find an initial feasible integer solution, or if it does, find a solution
anywhere close to optimal. While my constraint matrix is not unimodular
it may be close. When I relax my problem to an RMIP, my relaxed solutions
contain many dvs that are equal to their upper bound (1) or very close to
their lower bound (0). Some however linger in the middle. I have tried
rounding anything close to 1 to 1 and then fixing these dvs as 1 and
rerunning the MIP. This improves the run-times, but the problem is still
to large to solve. I'd like to try fixing things that are close to zero
and also rerunning the MIP. When I rerun the MIP with the fixed variables
I have an upper bound on how far I am from optimal by comparing my MIP
solution to the RMIP solution so I will know how well (or badly) my
rounding worked.
Has anyone had experience with a similar problem ? If so, are there any
guidlines on how to round. I know that I am trading off run time vs
optimality.
Also, are there any other techniques or heuristics that I could easily
call from GAMS that may help me here. I am open to all ideas.
thanks in advance,
Howard
Date: 9 May 1997 23:01:33 GMT
-- Paul Rubin
Date: Fri, 18 Apr 1997 10:29:26 -0400
Date: 15 Apr 1997 09:02:11 -0600
There are many possible explanations for the difference in what I saw
versus what Thomas reported, and it wouldn't be productive to speculate
in this forum; I offer this simply as an interesting data-point.
Date: 9 Apr 1997 15:27:49 GMT
Carlos
Date: 9 Apr 1997 11:07:37 -0700
Lawler, Eugene L.
A procedure for computing the $K$ best solutions to discrete
optimization problems and its application to the shortest path
problem. Management Sci. 18 (1971/72), 401--405.
I've always wondered whether it's practical or not. As I remember it,
he uses a very clever diagonalization to add constraints at each
iteration, in order to exclude the best solution(s). To exclude a
solution sol_i for the variables x_i, you simply add a negation
constraint:
~(x_1=sol_1 and x_2=sol_2 and ... and x_n=sol_n)
which deMorganizes into:
~(x_1=sol_1) or ~(x_2=sol_2) or ...
Does anyone have experience with how much these additional constraints
cost you in an IP or MIP solver? In other words, how much more
expensive is it to get the Kth-best solution as compared to the best?
RJ
Date: Sat, 05 Apr 1997 10:44:42 +0700
Any information about the homepages, the people who are experts in this
field, or anything would be a real help.
Thanks.
-Angela-
angela135@cyberlib.itb.ac.id
Date: Sat, 05 Apr 1997 15:37:47 -0800
Combinatorial Optimization is not a technique, but itself a (very)
special case of mixed integer linear programming. It involves 0,1
variables, and there is usually a certain structure in the constraints.
Examples are in routing, sequencing, assignment, packing & cutting, set
covering, and many, many more.
Do you perhaps mean Branch&Bound?
RJM
--
Roy Jonker, PhD @ MagicLogic Optimization Inc.
tel (604) 535 5133 (BC, Canada) - fax (on request)
email roy_jonker@magiclogic.com
www http://mindlink.net/magiclogic/magic.html
Date: 4 Apr 1997 02:24:58 GMT
Does anyone know where I can find some tough integer programming
examples? can be literature paper or ftp/web sites. Thanks
Joseph
Date: Fri, 04 Apr 1997 06:16:18 -0700
look at
http://www.caam.rice.edu/~bixby/miplib/miplib.html
Chung Cheong Ming wrote:
Hans Mittelmann
Date: 28 Mar 1997 10:56:08 -0500
Find the vector x which minimizes (x'Ax + b'x), subject to each x_i taking a value of
either 0 or 1; and A, a non-negative definite matrix. The ' in x' denotes transpose.
Questions
Any answers/references to the above questions would be greatly appreciated.
Thanks.
P.S. If you prefer, you can send a direct reply to: chandy@eng.umd.edu
Date: Fri, 28 Mar 1997 11:04:24 -0700
one code that should be applicable appears to be
http://www.mpi-sb.mpg.de/~barth/opbdp/opbdp.html
Probably, the order n must be not too large for that.
However, with 0-1 constraints, your feasible region is non-convex, and
the problem is NP-hard. To see this, start with the problem of
determining whether or not there is a 0-1 vector x such that Ax=b.
This problem is a well known NP-Complete decision problem. Now,
consider the Quadratic 0-1 programming problem:
If the optimal objective value is 0, then there is a 0-1 vector x such
that Ax=b. If the optimal objective value is greater than 0, then no
such vector x exists.
For the problem with A positive semidefinite and 0-1 constraints, your
best bet is probably to use a branch and bound approach. It'll take
exponential time, but for reasonable sizes of problems, it should work
fine. (For example, I've solved similar problems with up to 150 0-1
variables. See the papers listed below. ) You might also consider
outer approximation/generalized Bender's decomposition approaches.
However, I've run into some trouble in finding optimal solutions to
some problems using a commercially available implementation of the
outer approximation approach.
You might want to look at
Brian Borchers and John E. Mitchell, A Comparison of Branch and Bound
and Outer Approximation Methods for 0-1 MINLPs, To appear in Computers
and Operations Research. (see my web page for information on how to
get a preprint.)
Brian Borchers and John E. Mitchell, An Improved Branch and Bound
Algorithm for Mixed Integer Nonlinear Programs, Computers and
Operations Research. 21(4):359-367, 1994.
For code, I'd suggest that you look at BARON, which can be found pretty
easily by doing a web search on the Nonlinear Programming FAQ, and then
following the links.
In the 0,1 quadratic programming problem that we're considering here,
the quadratic programming relaxation with lower bounds of 0 and upper
bounds of 1 is a convex problem that is quite easy to solve.
It would be interesting to compare the performance of a branch and bound
code using the quadratic programming relaxation with a branch and bound
(or branch and cut) code using the SDP relaxation.
I'd place my bet on branch and bound with quadratic programming
relaxations.
Has anyone released a code that uses SDP relaxations in a branch and
bound framework to solve general quadratic +-1 programming problems?
Balas, E., "An additive algorithm for solving linear programs with
zero-one variables," Operations Research 13(4), 1965, 517-548.
You might also look at section 9.3 in Salkin and Mathur, _Foundations of
Integer Programming_ (Elsevier, 1989), which discusses several rules for
limiting branching in a zero-one integer linear problem.
-- Paul
Date: Thu, 20 Mar 97 14:52:59 GMT
I'm dealing with a large MINLP which I'm trying to solve by adjusting the
solution of the continuous relaxation. Currently, I'm doing this with a
problem specific depth first search where my goal is simply to determine an
integer feasible solution. During the search I choose one of the binary
variables for taking the value 1 and solve the relaxed with this constraint
added. The choice is based on problem related heuristics how to get a good
solution.
Obviously, I cannot avoid producing infeasible problems. For a reduced
problem, however, it seems that I can restrict the backtracking to one level, which will not work for the full problem.
Does anybody have a hint (or know a paper or book) how to choose these
heuristics such that the problems are likely to keep feasible. Hints to
problems which were solved in a similar manner are welcome, too.
Christian Schulz
Date: Fri, 07 Mar 1997 03:51:15 -0600
I've got the following problem:
I've got an Integer Programming Problem which solution I'm able to
obtain. I would like to know if I can easily compute other possible
solutions for the same problem without recalculating the whole
problem.
Thank you.
Date: 8 Mar 97 00:57:15 GMT
However, for many NP-complete problems, in practice one often finds 'clusters' of solutions close together, in which case finding a second is often easy.
Can someone who has experience finding multiple solutions to IP problems comment on their experience?
David
Date: Wed, 12 Feb 1997 13:40:50 +0100
Thank you in advance.
Date: 16 Feb 1997 05:17:10 GMT
In my ILP application, previously I used one evariable with 4 indices,
and found for problems more than 1000 variables, typical LP solver
like lp_solve are not capable to dealing with it within reasonable time.
The I use three variable with 2 indices each instead of above way,
I found the total number of variables for the same application drops,
while constraints (equation, inequation) increases, and the running time
is reduced dramatically.
So does this mean that less variables, more constraints will lead to
less compuation time in ILP?
Thanks,
Date: Wed, 22 Jan 1997 23:17:34 +0200
I am interested in any work related to this subject.
If you have something and know where I could find
something related, please contact me.
Thank's in advance,
have you done appropriate searches? An advanced Altavista search for
"parallel near mixed integer programming", for example, produces
http://www.cs.rice.edu/CS/faculty/bixby.html
and many more relevant links.
J. Pekny, D. Miller, G. McRae.
" An Exact Parallel Algorithm for Scheduling when Production Costs
Depend on Consecutive System States." Computers and Chemical Engeneering, Vol. 14, No. 9, pp. 1009--1023, 1990.
Arndt
http://rutcor.rutgers.edu:80/~jeckstei/
In particular
The first two are available as FTP-able postscript files, as they
haven't appeared in print yet.
Many other authors have made contributions in the area, some of which
you will find as references in the above papers.
CPLEX currently offers a commercial-level parallel MIP, but I think it is
presently limited to the SGI shared-memory parallel machines.
IBM offers a commercial parallel MIP (parallel OSL) for their SP-2 MPP.
Enjoy!
Assistant Professor Jonathan Eckstein
More platforms to follow, as we continue to develop our strategic
relationships with other vendors.
Date: 13 Jan 1997 07:24:36 GMT
Visit Live OR to experiment LIVE with the famous N-Queens problem and read
about solution strategies for this old combinatorial problem. The URL is
http://www.orsoc.org.uk/recreation/queens/
The material is particularly useful as supplement to courses on integer
programming, combinatorial optimization, constraint programming and related
topics.
And while there, have a look at other links we have to OR teaching
material. The URL is
http://www.orsoc.org.uk/resources/teaching.html
Best wishes and safe surfing!
Moshe Sniedovich
Date: 14 Jan 1997 14:54:19 GMT
try: http://www.gams.com and follow the link to the model library.
Regards, Alex Meeraus
Date: 9 Jan 1997 16:46:18 GMT
The question is this: how does one handle the fact that some
variables are constrained to be integers, while others are real
in the primal? What does that mean to the dual formulation?
Would appreciate any pointers.
Sachin
Date: 11 Jan 1997 00:47:46 GMT
If the dual is a network flow problem, then the coefficient matrix is
totally unimodular. In that case the coefficient matrix of the primal
problem is also totally unimodular. Consequently, for all integer right
hand sides for which the primal problem is feasible the extreme points are
integral (and so when you solve the LP relaxation of your MILP you will
obtain an extreme point solution where both the variables constrained to
be integer and the variables constrained to be real will have integer
solution values).
Hopefully this helps.
Thanks!
-Raghavan-
From: Hans D Mittelmann <mittelmann@asu.edu>
Subject: Davis-Putnam algorithm
To: hm
SCI.OP-RESEARCH Digest Mon, 13 Oct 97 Volume 4: Issue 41
From: Kimon Spiliopoulos <kimon@ath.forthnet.gr>
Subject: Another Question (RE:Best tool for optimizing with integer variables.)
You should read "Model Building in Mathematical Programming" by
H.P.Williams, John Wiley & Sons, 1990. ISBN: 0 471 92581 0
Most people will agree that it's the book you need.
From: cem14@cornell.edu (Carlos Murillo)
Subject: Another Question (RE:Best tool for optimizing with integer variables.)
SCI.OP-RESEARCH Digest Mon, 1 Sep 97 Volume 4: Issue 35
From: glen@proexam.org
Subject: What type of Problem/Solution is this?
Glen Brydon
glen@proexam.org
From: "Casimir Rommert J." <Casimir@KUB.NL>
Subject: What type of Problem/Solution is this?
To: glen@proexam.org
Your problem can be formulated as a 0-1 integer programming problem,
which measn that you extract a subset from a set of questions under
restrictions (for example, you need 3 questions on cows, 4 on blood
circualtion and 5 on pathology) Normally, integer programming algorithms
give a best solution in terms of some value (in business, usually
profit), to get a random solution you can assign random values to
questions. Small integer programming problems can be solved with
spreadsheet, for example with the Quattro Pro optimizer or the Excel
Solver.
From: John Chionglo <john_chionglo@dofasco.ca>
Subject: A 0-1 Integer Programing problem
Hello.
SCI.OP-RESEARCH Digest Mon, 25 Aug 97 Volume 4: Issue 34
From: "Shereef B. M. Shehata" <shehata@msp.sc.ti.com>
Subject: Integer Programming on parallel architectures
Hello,
From: Bob Daniel <rcd@dash.co.uk>
Subject: Integer Programming on parallel architectures
Dear Shereef
From: rrk@noel.cs.rice.edu (Ramakrishnan Rajamony)
Subject: Integer Programming on parallel architectures
CPLEX has been parallelized for shared memory, and has been (is being) used
with TreadMarks, a software distributed shared memory system. You can find
speedup numbers for the problems from the MIPLIB library. The results are in
a paper that appeared in the Feb 1996 issue of IEEE Computer. There is a
copy online in http://www.cs.rice.edu/~willy/papers/computer95.ps.gz
SCI.OP-RESEARCH Digest Mon, 4 Aug 97 Volume 4: Issue 31
From: dongen@cs.ucc.ie (Marc van Dongen)
Subject: Need this book
I was hoping someone could help me find this book:
dongen@cs.ucc.ie
From: murthy@price.eecs.berkeley.edu (Praveen Murthy)
Subject: Need this book
This is a great book IMO, but Amazon books lists it for $300!! That's the only place where I have seen it...(http://www.amazon.com )
SCI.OP-RESEARCH Digest Mon, 14 July 97 Volume 4: Issue 28
From: Diego Faneyte <dbc.faneyte@student.unimaas.nl>
Subject: The value of the integer solution = relaxation solution, WHY !
From: pehng@cds.mrs.umn.edu (Peh H. Ng )
Subject: The value of the integer solution = relaxation solution, WHY !
In general, it is NOT true that the LP-relaxation of an ILP problem
will yield the same optimal solution point (let alone optimial value)
of the ILP.
From: cary@rogers.wave.ca (Cary Swoveland)
Subject: The value of the integer solution = relaxation solution, WHY !
SCI.OP-RESEARCH Digest Mon, 30 Jun 97 Volume 4: Issue 26
From: "Michael M. Kostreva" <flstgla@clemson.edu>
Subject: Verify Optimality for ILP??
The best feasible solution found is evaluated for its objective
function. This value is compared with a lower bound (hopefully it is a
rather tight one) and then an upper bound on percent deviation from
optimality is calculated. People who do not need an absolute optimal
solution stop when one is found within a guaranteed 5% or so.
SCI.OP-RESEARCH Digest Mon, 30 Jun 97 Volume 4: Issue 26
From: Christian Holzbaur <christian@ai.univie.ac.at<
Subject: MIPLIB example NOSWOT
SCI.OP-RESEARCH Digest Mon, 23 Jun 97 Volume 4: Issue 25
From: nc-weidenma@netcologne.de
Subject: MIPLIB example NOSWOT
Has anybody got the solution -43 ?
SCI.OP-RESEARCH Digest Mon, 16 Jun 97 Volume 4: Issue 24
From: ian@peacesummit.com (Ian Upright)
Subject: solving highly constrained integer problems
Hi, I'm fairly new to understanding optimization, and I have a few
questions. We are currently using a commercial linear optimizer (Lingo) and
we've found that the more integers in the problem, and the more we constrain
it, the longer the problem takes to solve. Not only that, but it seems to
make solving the problem much more difficult, and sometimes it is unable to
find a solution where we know one does exist.
SCI.OP-RESEARCH Digest Mon, 9 June 97 Volume 4: Issue 23
From: ilinm@aol.com (ILINM)
Subject: need help solving large MIP by rounding/fixing parts of RMIP solutions
Hello,
ilinm@aol.com
SCI.OP-RESEARCH Digest Mon, 12 May 97 Volume 4: Issue 19
From: rubin@msu.edu (Paul A. Rubin)
Subject: MIP or Goal Programming
This is not a problem - it is not necessary that every variable in an
optimization problem appear in the objective function. Just be sure to
leave b_0 and b_1 unrestricted in sign (allow them to be either positive or
negative).
SCI.OP-RESEARCH Digest Mon, 28 April 97 Volume 4: Issue 17
From: Irv Lustig <irv@dizzy.cplex.com>
Subject: Integer programming examples ?
SCI.OP-RESEARCH Digest Mon, 21 April 97 Volume 4: Issue 16
From: ashbury@skypoint.com (John W Gregory)
Subject: Questions regarding a MIP setup
SCI.OP-RESEARCH Digest Mon, 14 April 97 Volume 4: Issue 15
From: Carlos Henggeler Antunes <cantunes@inescc.pt>
Subject: k-th best solution in ILP
I would appreciate if anyone could send me some information on or
pointers to algorithms to compute a 2nd best, 3rd best,...k-th best
solution to an integer (or mixed integer) LP problem.
Thanks in advance for your cooperation.
From: eppstein@euclid.ics.uci.edu (David Eppstein)
Subject: k-th best solution in ILP
I have a bibliography of k-shortest-path papers online at
http://www.ics.uci.edu/~eppstein/bibs/kpath.bib which also includes some
work on integer LPs, e.g.:
From: Othar Hansson <othar@thinkbank.com>
Subject: k-th best solution in ILP
There is also a paper by Lawler:
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: Help with Search Techniques
Steve Hill wrote:
SCI.OP-RESEARCH Digest Mon, 7 April 97 Volume 4: Issue 14
From: hendi171 <hendi171@cyberlib.itb.ac.id>
Subject: Mixed integer programming and combinatorial optimization
Does anybody know how to use the combinatorial optimization to solve the
integer part (the binary variables 0-1) of mixed integer linear
programming problems?
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: Mixed integer programming and combinatorial optimization
From: cmchung@se.cuhk.edu.hk (Chung Cheong Ming)
Subject: Integer programming examples ?
hello everyone,
From: "Hans D. Mittelmann" <mittelmann@asu.edu>
Subject: Integer programming examples ?
To: Chung Cheong Ming <cmchung@se.cuhk.edu.hk>
Hi,
SCI.OP-RESEARCH Digest Mon, 31 Mar 97 Volume 4: Issue 13
From: chandy@Glue.umd.edu (Chandrasekar Sankaran)
Subject: Question in Combinatorial Optimization
I have questions regarding the following problem:
From: "Hans D. Mittelmann" <mittelmann@asu.edu&gr;
Subject: Question in Combinatorial Optimization
Hi,
From: borchers@nmt.edu (Brian Borchers)
Subject: Question in Combinatorial Optimization
If the objective function matrix is positive semidefinite, then you
do have a convex optimization problem and things aren't so bad.
From: hwolkowi@orion.math.uwaterloo.ca (Henry Wolkowicz)
Subject: Question in Combinatorial Optimization
You have a variant of the Max-Cut problem, i.e. max a quadratic function
subject to 0,1 (or +-1) constraints on the variables.
There are many efficient heuristics for this NP-hard problem; as well as
some very, very elegant worst case bounds.
A good reference is the recent PhD thesis of Christoph Helmberg
new address in Berlin;
From: borchers@nmt.edu (Brian Borchers)
Subject: Question in Combinatorial Optimization
Henry Wolkowicz wrote:
From: borchers@nmt.edu (Brian Borchers)
Subject: Question in Combinatorial Optimization
Yet another approach- You could use an implicit enumeration code
such as OPBDP to solve the problem.
From: rubin@msu.edu (Paul A. Rubin)
Subject: Heuristical Solution of MINLP
I don't know how relevant this will be, since it applies to pure (not
mixed) integer linear (not nonlinear, if that's what the N in MINLP
represents) programs, but Egon Balas published a semi-enumerative algorithm
for bivalent linear problems in 1965 that includes some testing of the
effect on feasibility of impending changes to a variable. The citation is:
SCI.OP-RESEARCH Digest Mon, 24 Mar 97 Volume 4: Issue 12
From: schulz@ast.chemietechnik.uni-dortmund.de (Christian Schulz)
Subject: Heuristical Solution of MINLP
Hi,
SCI.OP-RESEARCH Digest Mon, 10 Mar 97 Volume 4: Issue 10
From: ftg@geocities.com
Subject: When solutions are not unique in Integer Programming question
Hello,
From: mitchell@cs.toronto.edu (David G. Mitchell)
Subject: When solutions are not unique in Integer Programming question
Finding a solution to an integer programming instance is NP-complete. From this it follows that, in the worst case, finding a second solution is no easier than finding the
first was.
SCI.OP-RESEARCH Digest Mon, 17 Feb 97 Volume 4: Issue 7
From: Baran Curuklu <frv96bcu@idt.mdh.se>
Subject: Integer Prog. with Genetic Algoritms
Hi There!
I am looking for articles and programs on the following topic:
"Integer Programming with Genetic Algoritms".
From: yangz@pascal.ics.uci.edu (Yang Zhang)
Subject: ILP size versus running time
Hi, ILP Experts:
ZY
SCI.OP-RESEARCH Digest Mon, 27 Jan 97 Volume 4: Issue 4
From: Efraimidis Paylos <efraimid@cti.gr>
Subject: (Mixed) Integer Programming
I am looking for books, papers or technical reports on
mixed integer programming and especially parallel mixed
integer programming.
From: "Hans D. Mittelmann" <mittelmann@asu.edu>
Subject: (Mixed) Integer Programming
Hi,
http://www.epfl.ch/SIC/SA/publications/SCR94/6-94-page15.html
http://www.parsytec.de/project/pamips1.html
http://www.iwr.uni-heidelberg.de/iwr/agbock/users/dieter/pamipspubl.html
http://softlib.rice.edu/CRPC/softlib/TRs_online.html
http://www.ieor.columbia.edu/~evakylee/parallel.html
http://www.cs.cornell.edu/Info/People/oktay/oktay.html
From: arndt <arndt@hamlet.et.uni-magdeburg.de>
Subject: (Mixed) Integer Programming
To: Efraimidis Paylos <efraimid@cti.gr>
Have a look at the field of scheduling of batch plants.
A parallel algorithm therefore is described in:
From: jeckstei@rutcor.rutgers.edu (Jonathan Eckstein)
Subject: (Mixed) Integer Programming
I have one published article on parallel MIP and two currently in
press, plus a proceedings paper. For more info and preprints, see
my web site:
From: Irv Lustig <irv@dizzy.cplex.com>
Subject: (Mixed) Integer Programming
Jonathan Eckstein wrote:
SCI.OP-RESEARCH Digest Mon, 20 Jan 97 Volume 4: Issue 3
From: moshe@mundoe.maths.mu.OZ.AU (Moshe Sniedovich)
Subject: Royal Optimization: The N-Queens Puzzle!
G'day:
Honorary Editor, Live OR
From: "Alexander Meeraus" <alex@gams.com>
Subject: Royal Optimization: The N-Queens Puzzle!
To find one solution is easy. How many solution are there? John Beauvais showed
a nice solution with 0/1 cuts in the EKKNEW, Issue 2, April 1991 (OSL Newsletter).
You can find a GAMS repsentation in the GAMS Model Library, the name of the
model is QUEENS. You will find a number of other recreational IP problems.
SCI.OP-RESEARCH Digest Mon, 13 Jan 97 Volume 4: Issue 2
From: sachin@iastate.edu (Sachin S Sapatnekar)
Subject: Dual of an MILP
I have an MILP whose constraint matrix is the transpose of an
incidence matrix. If I take the dual, I can translate it to
a mincost flow problem.
From: raghava@uswest.com (S. Raghavan)
Subject: Dual of an MILP
Your question is not clear to me.