Date: 6 Apr 1995 07:39:55 GMT
From: murakami@bayes.ece.cmu.edu (Kazutaka Murakami)
Subject: Disjunctive optimization: min() type constraints
I have an optimization probelm which involves y=min(f1,f2,..,fn) type
constraints. I know this problem can be formulated as IP using disjunctive
optimization technique. I would like to know a recent reference or survey on
this topic. I am especially interested in a work specific to optimization
with min() type constraint rather than disjunctive optimization in general.
I am new to this type of problem, and I would appreciate any recommendation
on where I should start. Also appreciate any suggestion on other possible
approach to this type of problem. Finally, I would like to hear how these
approaches work in practice (reasonably fast, just theoretical interest,
etc.)
Thank you for your attention, Kazu
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
Crawl back to front page.
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