|
|
 | | From: | bob | | Subject: | Preferring integers in LP | | Date: | 20 Jan 2005 03:21:12 -0800 |
|
|
 | Hi all!
I have a MIP problem where I want to relax the integer condition to "I
prefer integers". Thus I want to introduce some penalty term for
deviation from the nearest higher integer into the objective function.
My first approach is this:
F(x , q) = F(x) + sum_p(sum_q(sum_i(1-q_{p,d,i})*B)))
s.t.
q_{p,d,i}<=1 for all p, d, i
sum_i(q_{p,d,i}>=x_{p,d}) for all p, d
other constraints
x>=0 and real
q>=0 and real
the other symbols are indices.
But the magnitude of x is known only very roughly so I would end up
with an enourmous number of additional q_{p,d,i} variables and
constraints.
Could anybody give me a hint on how to model this problem in a better
way so that I am able to solve it with a pure LP solver?
Thanks a lot for your considerations in advance!
Bob
|
|
| | From: | Michael Hennebry | | Subject: | Re: Preferring integers in LP | | Date: | 21 Jan 2005 11:42:37 -0800 |
|
|
| Get your first solution by treating it as a continuous problem.
Given any solution, call it y, substitute x=floor(y)+f,
where the elements of f are free variables.
For each f[j], add a penalty term proportional
to max(0, 1-(2f[j]-1)**2).
It peaks at f[j]=1/2 and is 0 if f[j] is outside the open range (0, 1).
The last iteration occurs when none of f's elements are outside [0, 1).
Note that with the penalty terms,
you will not have a convex programming problem.
A local optimum might not be a global optimum.
|
|
| | From: | Bob | | Subject: | Re: Preferring integers in LP | | Date: | 21 Jan 2005 10:43:11 -0800 |
|
|
| Oh no, of course not! That's wrong, thanks for the hint, Michael!
Any working ideas on how to do "preference" for integral numbers in an
LP objective function?
(I could add a second sum to repair my first-shot-idea but in general,
this approach generates too many new variables - and it's dirty...)
Thanks,
Bob
> Are you sure that is what you want?
> According to your formula, which is discontinuous,
> 0.00001 gets a bigger penalty than 0.5.
|
|
| | From: | Michael Hennebry | | Subject: | Re: Preferring integers in LP | | Date: | 20 Jan 2005 09:07:07 -0800 |
|
|
|
bob wrote:
> I have a MIP problem where I want to relax the integer condition to
"I
> prefer integers". Thus I want to introduce some penalty term for
> deviation from the nearest higher integer into the objective
function.
Are you sure that is what you want?
According to your formula, which is discontinuous,
0.00001 gets a bigger penalty than 0.5.
|
|
|
