Answers to: linearization of the sum functionhttp://www.or-exchange.com/questions/13718/linearization-of-the-sum-function<p>I am trying to do an optimization however the solver apparently does not perform well in the presence of a sum function.</p>
<p>how to linearize the following</p>
<pre><code>sum [u |v<>u and StringLength(PeriodDestination(u,t))>0 and edge(s)= PeriodDestination(u,t) ,PeopleAttraction(v,u,t)] ;
</code></pre>
<p>thank you :)</p>
<p>just in case please find below my code with the variables definitions the goal is to find optimal values of fa fr and co</p>
<pre><code> Constraint c4a {
IndexDomain: (v,s,t)| s in VehicleSocialSphere(v) and StringLength(PeriodDestination(v,t))>0;
Definition: {
SocialAttrPerLoc(v,s,t) <= maximumAttraction(v,t)+z1(v,s,t)+0.0001*z2(v,s,t)
}
}
Constraint c4b {
IndexDomain: (v,s,t)| s in VehicleSocialSphere(v) and StringLength(PeriodDestination(v,t))>0;
Definition: {
maximumAttraction(v,t)<=SocialAttrPerLoc(v,s,t) +z2(v,s,t)+0.0001*z1(v,s,t)
}
}
Constraint c4c {
IndexDomain: (v,s,t)|s in VehicleSocialSphere(v) and StringLength(PeriodDestinationID(v,t))>0;
Definition: z1(v,s,t)+chosenLocation(v,s,t)+z2(v,s,t)=1;
}
Constraint c2b {
IndexDomain: (v,s,t) | s in VehicleSocialSphere(v) and StringLength(PeriodDestination(v,t))>0;
Definition: {
maximumAttraction(v,t) >= SocialAttrPerLoc(v,s,t)
}
}
Constraint c2a {
IndexDomain: (v,t)|StringLength(PeriodDestination(v,t))>0;
Definition: sum( s | s in VehicleSocialSphere(v), chosenLocation(v,s,t) ) <= 1;
}
Constraint c1 {
IndexDomain: t;
Definition: {
co(t)+fr(t)+fa(t)=1
}
}
ElementParameter gmp1 {
Range: AllGeneratedMathematicalPrograms;
}
Variable co {
IndexDomain: t;
Range: [0, 1];
Default: 1;
}
Variable fr {
IndexDomain: t;
Range: [0, 1];
Default: 1;
}
Variable fa {
IndexDomain: t;
Range: [0, 1];
Default: 1;
}
MathematicalProgram MaximalMatchingPlan {
Objective: MatchingSum;
Direction: maximize;
Constraints: AllConstraints;
Variables: AllVariables;
Type: Automatic;
}
Variable MatchingSum {
Range: free;
Definition: {
! sum the number of chosen location that match the actual trace.
sum[(v,s,t) | s in VehicleSocialSphere(v) and StringLength(PeriodDestination(v,t))>0 and edge(s)=PeriodDestination(v,t),chosenLocation(v,s,t)]
}
}
Variable z1 {
IndexDomain: (v,s,t)|s in VehicleSocialSphere(v) and StringLength(PeriodDestinationID(v,t))>0;
Range: binary;
}
Variable z2 {
IndexDomain: (v,s,t)|s in VehicleSocialSphere(v) and StringLength(PeriodDestinationID(v,t))>0;
Range: binary;
}
Variable chosenLocation {
IndexDomain: (v,s,t)|s in VehicleSocialSphere(v) and StringLength(PeriodDestinationID(v,t))>0;
Range: binary;
Definition: {
!mark the location having the maximum attraction
}
}
Variable maximumAttraction {
IndexDomain: (v,t) |StringLength(PeriodDestinationID(v,t))>0;
Range: nonnegative;
Definition: {
! check the location with the maximum social attraction
}
}
Variable SocialAttrPerLoc {
IndexDomain: (v,s,t) |s in VehicleSocialSphere(v) and StringLength(PeriodDestination(v,t))>0;
Range: nonnegative;
Definition: {
!for each location in the vehicle v social sphere sum the attraction of its acquaintances u residing there
sum [u |v<>u and StringLength(PeriodDestination(u,t))>0 and edge(s)= PeriodDestination(u,t) ,PeopleAttraction(v,u,t)] ;
}
}
Variable peopleattraction {
IndexDomain: {
(v,u,t)|v<>u and StringLength(PeriodDestination(v,t))>0 !this condition to insure the exsistance of a trace at this period for this vehicle to allow the comparaison of the prduced destination guess
}
Range: [0, 1];
Definition: {
!the attraction of a vehicle to its aquaintances whether friends, family or coworkers
fr(t)*friends(v,u) + fa(t)*family(v,u) + co(t)*coworker(v,u);
}
}
}
</code></pre>enSun, 08 May 2016 15:41:54 -0400Answer by Paul Rubinhttp://www.or-exchange.com/questions/13718/linearization-of-the-sum-function/13719<p>You left out quite a few pertinent details: what language you are using (the first line looks like Python but the rest could be anything); what type of model this is (I'm guessing LP or MIP, but it could be a constraint program, which would be entirely different); in what way the solver "does not perform well". I'll go out on a limb and guess this is an LP or MILP, in which case one thing will be true across all solvers with which I am familiar: the conditions in the summation must involve only constant parameters and sets. In other words, the solver must know <em>before starting the solution process</em> exactly which terms to include in the sum. I can't tell from a quick reading whether that is true in your case.</p>Paul RubinSun, 08 May 2016 15:41:54 -0400http://www.or-exchange.com/questions/13718/linearization-of-the-sum-function/13719