Non-Integral Solutions for Parametric Optimization Problem ?
visq
I recently learned about PiP, and got curious whether it could solve
the following parametric optimization problem:
maximize objective
s.t. objective <= 38 a + 7 b + 10 C
a+b <= 1
C <= 10 b
a,b >= 0 integral unknowns, C >= 0 parameter
Intended Solution:
| C <= 3 = 38
| C <= 10 = 7 + 10 C
| otherwise = no solution
I finally managed to get some solution using the bigparm trick, but it
is not quite what I'd expected: despite of requesting an integer
solution, the objective value is only integral for certain values of
the parameter. The solution is an interesting overapproximation on its
own, though. I've attached the PiP input for the problem below.
Solution 1: 38 + 6.9 C if C <= 10
My second attempt was to replace the parameter C by an unknown c in
the objective function and add another constraint c <= C. This leads
to a (problem to complex) message. When increasing the maximal size
for solutions as suggested in the manual, I get a solution, but it is
very large and hard to understand, with no less than 159 newparams in
total. Also, there is an overflow with the 32 bit version, and the
time needed to solve the problem with the 64-bit version (3.5s) seems
way too long for this easy problem.
Is there a better way to formulate this toy example, or is PiP not the
right choice for this kind of problem?
Kind Regards,
Benedikt Huber
P.S.: Thanks for providing PiP and the nice documentation for free !
-- Problem 1 --
((
maximize 38 a + 7 b + 10 C
s.t. obj,a,b,C >= 0
obj <= 38 a + 7 b + 10 c
a+b <= 1
C <= 10 b
------------
Expected Solution: if(C<4) 38 else 7 + C*10
)
3 2 7 0 4 1
(
#[-1 0 0 0 1 0]
#[ 0 -1 0 0 1 0]
#[ 0 0 -1 0 1 0]
#[ 0 0 0 0 0 1]
#[ 1 -38 -7 0 44 10]
#[ 0 1 1 1 -2 0]
#[ 0 0 -10 0 10 -1]
)
( )
)
-- Problem 2 --
((
maximize 38 a + 7 b + 10 c
s.t. obj,a,b,c,C >= 0
obj <= 38 a + 7 b + 10 c
a+b <= 1
c <= 10 b
c <= C
)
4 2 9 0 5 1
(
#[-1 0 0 0 0 1 0]
#[ 0 -1 0 0 0 1 0]
#[ 0 0 -1 0 0 1 0]
#[ 0 0 0 -1 0 1 0]
#[ 0 0 0 0 0 0 1]
#[ 1 -38 -7 -10 0 54 0]
#[ 0 1 1 0 1 -2 0]
#[ 0 0 -10 1 0 9 0]
#[ 0 0 0 1 0 -1 1]
)
( )
)
Sven Verdoolaege
> Hello,
> I recently learned about PiP, and got curious whether it could solve
> the following parametric optimization problem:
>
> maximize objective
> s.t. objective <= 38 a + 7 b + 10 C
> a+b <= 1
> C <= 10 b
> a,b >= 0 integral unknowns, C >= 0 parameter
> Intended Solution:
> | C <= 3 = 38
I believe that should be C <= 0.
> | C <= 10 = 7 + 10 C
> | otherwise = no solution
>
> I finally managed to get some solution using the bigparm trick, but it
> is not quite what I'd expected: despite of requesting an integer
> solution, the objective value is only integral for certain values of
> the parameter.
What does the output look like and why do you say that the output
is non-integral? Note that PIP assumes that the parameters are
integeral. Perhaps that explains your confusion?
skimo
visq
> On Tue, Jun 15, 2010 at 04:57:01AM -0700, visq wrote:
> > Hello,
> > I recently learned about PiP, and got curious whether it could solve
> > the following parametric optimization problem:
>
> > maximize objective
> > s.t. objective <= 38 a + 7 b + 10 C
> > a+b <= 1
> > C <= 10 b
> > a,b >= 0 integral unknowns, C >= 0 parameter
> > Intended Solution:
> > | C <= 3 = 38
>
Thank you for replying.
> I believe that should be C <= 0.
| C == 0 = 38
| 1 <= C <= 10 = 7 + 10 C
| otherwise = no solution
Thanks for the correction
> > I finally managed to get some solution using the bigparm trick, but it
> > is not quite what I'd expected: despite of requesting an integer
> > solution, the objective value is only integral for certain values of
> > the parameter.
>
> What does the output look like and why do you say that the output
> is non-integral?
I'm not actually confused, I hope, but maybe I misunderstood PiPs
output:
(()
(if #[ 0 -1 10]
(newparm 2 (div #[ 0 9 0] 10))
(list #[ 1 21 -31 -38]
#[ 1 1 -1 -1]
#[ 1 -1 1 0])
()
))
which, after removing the big paramter translation (x ==> B - x)
corresponds to
if C <= 10
let ?2 = 9/10 C
obj = 38 + 31 ?2 - 21 C = 38 + 69/10 C
a = 1 + ?2 - C = 1 - 1/10 C
b = C - ?2 = 9/10 C
else
void
> Note that PIP assumes that the parameters are integeral. Perhaps that explains your confusion?
for rational objective values (respectively rational solutions to
unknowns)?
In the motivating example in the manual, the unknowns are loop
iteration variables, so this seems strange to me.
I'm also curious, in case anyone cares to explain, why PiP cannot find
a satisfactory solution for the second problem.
cheers, benedikt
>
> skimo
Sven Verdoolaege
> On Jun 15, 2:32�pm, Sven Verdoolaege <skimo-pip...@kotnet.org> wrote:
> > What does the output look like and why do you say that the output
> > is non-integral?
>
> I've already posted the beautified output:
> > > Solution 1: 38 + 6.9 C if C <= 10
>
> But the answer I'd like to have is e.g. 57 for C=5, not 38+34.5=72.5
And that's what you get:
38 + 31 * ((5 * 9)/10) - 21 * 5 = 38 + 31 * 4 - 21 * 5 = 57
> I'm not actually confused, I hope, but maybe I misunderstood PiPs
> output:
> (()
> (if #[ 0 -1 10]
> (newparm 2 (div #[ 0 9 0] 10))
> (list #[ 1 21 -31 -38]
> #[ 1 1 -1 -1]
> #[ 1 -1 1 0])
> ()
> ))
> which, after removing the big paramter translation (x ==> B - x)
> corresponds to
> if C <= 10
> let ?2 = 9/10 C
No, ?2 = (9 * C)/10
> obj = 38 + 31 ?2 - 21 C = 38 + 69/10 C
integer division is not a linear operation.
> > Note that PIP assumes that the parameters are integeral. Perhaps that explains your confusion?
> So the 'integral' mode assumes integral parameters, but still allows
> for rational objective values (respectively rational solutions to
> unknowns)?
No, parameters are always integral. Unknows are rational is rational mode.
> I'm also curious, in case anyone cares to explain, why PiP cannot find
> a satisfactory solution for the second problem.
No idea. I no longer support piplib.
In isl, you get essentially the same answer in both cases:
lexmax [C] -> {[obj,a,b] : obj <= 38 a + 7 b + 10 C and a+b <= 1 and C <= 10 b and a,b,C >= 0};
[C] -> { [obj, a, b] : 31a = -7 - 10C + obj and 31b = 38 + 10C - obj and C >= 0 and C <= 10 and 10obj <= 380 + 69C and 10obj >= 101 + 69C }
lexmax [C] -> {[obj,a,b,c] : obj <= 38 a + 7 b + 10 c and a+b <= 1 and C <= 10 b and c <= C and a,b,c,C >= 0};
[C] -> { [obj, a, b, c] : 31a = -7 - 10C + obj and 31b = 38 + 10C - obj and c = C and C >= 0 and C <= 10 and 10obj <= 380 + 69C and 10obj >= 101 + 69C }
skimo
visq
> On Tue, Jun 15, 2010 at 07:15:48AM -0700, visq wrote:
> > But the answer I'd like to have is e.g. 57 for C=5, not 38+34.5=72.5
>
> And that's what you get:
>
> 38 + 31 * ((5 * 9)/10) - 21 * 5 = 38 + 31 * 4 - 21 * 5 = 57
>
> No, ?2 = (9 * C)/10
> > obj = 38 + 31 ?2 - 21 C = 38 + 69/10 C
> integer division is not a linear operation.
with the solution.
> > > Note that PIP assumes that the parameters are integeral. Perhaps that explains your confusion?
> > So the 'integral' mode assumes integral parameters, but still allows
> > for rational objective values (respectively rational solutions to
> > unknowns)?
> No, parameters are always integral. Unknows are rational is rational mode.
> > I'm also curious, in case anyone cares to explain, why PiP cannot find
> > a satisfactory solution for the second problem.
>
> No idea. I no longer support piplib.
> In isl, you get essentially the same answer in both cases:
> lexmax [C] -> {[obj,a,b] : obj <= 38 a + 7 b + 10 C and a+b <= 1 and C <= 10 b and a,b,C >= 0};
> [C] -> { [obj, a, b] : 31a = -7 - 10C + obj and 31b = 38 + 10C - obj and C >= 0 and C <= 10 and 10obj <= 380 + 69C and 10obj >= 101 + 69C }
>
> lexmax [C] -> {[obj,a,b,c] : obj <= 38 a + 7 b + 10 c and a+b <= 1 and C <= 10 b and c <= C and a,b,c,C >= 0};
problem.
This is hopefully the problem I had in mind originally, with the
solution (0<=C<4 ==> 38, 4<=C<=10 ==> 7 + 10 C)
cheers, benedikt
Sven Verdoolaege
> On Jun 15, 4:49�pm, Sven Verdoolaege <skimo-pip...@kotnet.org> wrote:
> > On Tue, Jun 15, 2010 at 07:15:48AM -0700, visq wrote:
> > [C] -> { [obj, a, b] : 31a = -7 - 10C + obj and 31b = 38 + 10C - obj and C >= 0 and C <= 10 and 10obj <= 380 + 69C and 10obj >= 101 + 69C }
> >
> > � � lexmax [C] -> {[obj,a,b,c] : obj <= 38 a + 7 b + 10 c and a+b <= 1 and C <= 10 b and c <= C and a,b,c,C >= 0};
> that should be (lowercase) c <= 10 b, otherwise it is indeed the same
> problem.
Right,
lexmax [C] -> {[obj,a,b,c] : obj <= 38 a + 7 b + 10 c and a+b <= 1 and c <= 10 b and c <= C and a,b,c,C >= 0};
[C] -> { [obj, a, b, c] : (obj = 7 + 10C and a = 0 and b = 1 and c = C and C >= 5 and C <= 6) or (exists (e0 = [(9C)/10], e1 = [(-47 + obj + 9a + 20e0)/30]: b = 1 - a and 10c = -7 + obj - 31a and C >= 0 and C <= 10 and 10e0 <= 9C and 10e0 >= -9 + 9C and 20e0 >= -141 + 3obj + 27a and 20e0 <= -121 + 3obj + 27a and 30e1 <= -47 + obj + 9a + 20e0 and 30e1 >= -67 + obj + 9a + 20e0 and 15e1 >= -94 + 2obj + 18a and 10e1 >= -27 + obj - 11a and 10e1 <= -17 + obj - 11a and 69a <= 107 - obj)) or (C = 4 and obj = 47 and a = 0 and b = 1 and c = 4) or (a = -7 - 10C + obj and b = 8 + 10C - obj and c = 21 + 31C - 3obj and 4obj >= 35 + 39C and 8obj <= 78 + 77C and C <= 10 and obj >= 7 + 10C and 3obj <= 28 + 29C and 7obj <= 59 + 69C and obj <= 8 + 10C) or (obj = 107 and a = 0 and b = 1 and c = 10 and C >= 11) }
> This is hopefully the problem I had in mind originally, with the
> solution (0<=C<4 ==> 38, 4<=C<=10 ==> 7 + 10 C)
Looks like it, except that there's also a C >= 11 case.
I should tell you, though, that your example uncovered a bug in isl,
so you'll only get the answer above is you use the very latest version
of isl.
skimo