Questions Tagged With linear-programminghttp://www.or-exchange.com/tags/linear-programming/?type=rssquestions tagged <span class="tag">linear-programming</span>enThu, 10 May 2018 06:22:36 -0400Solving a large number of very similar LP problemshttp://www.or-exchange.com/questions/15664/solving-a-large-number-of-very-similar-lp-problems<p>I have to solve a large number (from 2 to 10 millions) of very similar small (maybe 100 constraints) problems where only a small number of constraints, always the same change.</p>
<p>Essentially I want to minimize the cost of covering consumption. The rules are more or less the following:</p>
<ul>
<li>Each customer (we have millions of them) consume a number of units of different items, this is different for each customer.</li>
<li>We have a number of products, each of them include one or many items, at a given cost. The products and costs are common for all customers</li>
<li>Further there are some additional constraints that link which products can be combined for each customer, but the constraints are again the same for all customers.</li>
</ul>
<p>I am planning on solving this using Spark and I am not familiar with the performance of algorithms and my question is, should I try to solve a very large number of small problems, or should I combine them in a large problem repeating the constraints between products for each customer?</p>
<p>Can I somehow leverage that the individual problems are very similar? </p>
<p>Thanks</p>Luis SisamonThu, 10 May 2018 06:22:36 -0400http://www.or-exchange.com/questions/15664/solving-a-large-number-of-very-similar-lp-problemslinear-programmingHow can i solve lp problem by benders decomposition in gams?http://www.or-exchange.com/questions/15643/how-can-i-solve-lp-problem-by-benders-decomposition-in-gams<p>Hello I have a lp problem and I want to solve it by Bender's decomposition, I try to code it in games but I can't get the result.</p>
<p>Can anyone there help me?
My model is:</p>
<p>Min z=2x1+2.5x2+0.5x3+4x4+3x5</p>
<p>Subject to</p>
<p>-2x1+3x3-4x5<=-4</p>
<p>2x1+4x2+x5<= 2.5</p>
<p>2x3-x4-x5<=0.5</p>
<p>-0.5x3-x4+3x5<=-3</p>
<p>x1,x2,x3,x4,x5>=0</p>KenkavazaWed, 02 May 2018 08:53:21 -0400http://www.or-exchange.com/questions/15643/how-can-i-solve-lp-problem-by-benders-decomposition-in-gamsbenders-decompositionlinear-programminggamscodingInequality Constraint in a Linear Program (with a constant RHS)http://www.or-exchange.com/questions/15604/inequality-constraint-in-a-linear-program-with-a-constant-rhs<p>Is it possible to forbid a LP variable from being a specific constant?</p>
<p>ex X <> 0.5</p>gtg489pWed, 25 Apr 2018 13:21:08 -0400http://www.or-exchange.com/questions/15604/inequality-constraint-in-a-linear-program-with-a-constant-rhslinear-programminglinearProblem with GAMS code ***(MANY ERRORS)http://www.or-exchange.com/questions/15491/problem-with-gams-code-many-errors<pre><code>SETS
i streams /1*7/
j components /CO2,CH4,CO,H2,H2O,CH3OH,N2/
k reactions /1*2/
l equipments /m, r, s1, s2/;
SCALAR
T total flowrate /1/;
PARAMETERS
A(j,i) stream 1;
A('CO2','1')=0.1;
A('CH4','1')=0.05;
A('CO','1')=0.184;
A('H2','1')=0.59;
A('H2O','1')=0.008;
A('CH3OH','1')=0;
A('N2','1')=0.068;
TABLE
n(j,k) stoichiometric coefficients
1 2
CO2 0 1
CH4 0 0
CO 1 1
H2 2 1
H2O 0 1
CH3OH 1 0
N2 0 0 ;
TABLE
v(j,k) extent of reaction
1 2
CO2 0 1280
CH4 0 0
CO 1 -1280
H2 2560 1280
H2O 0 -1280
CH3OH -1280 0
N2 0 0 ;
VARIABLES
*Mixer, Reactor, Product, Seperator 1, Seperator 2/Recycle , Purge
pv product value
fc feed cost
p(l) processing cost
profit profit;
EQUATIONS
*Mass Balances (Stream 2)
EQ1
*Mass Balances (Stream 3)
EQ2
*Mass Balances (Stream 4)
EQ3
*Mass Balances (Stream 5)
EQ4
*Mass Balances (Stream 6)
EQ5
*Mass Balances (Stream 7)
EQ6
*Product Value
EQ7
*Feed Cost
EQ8
*Processing costs
EQ9
EQ10
EQ11
EQ12
*Profit
EQ13;
EQ1..sum('2',A(j,'2'))=E=T+sum('6',A(j,'6'));
EQ2..sum('3',A(j,'3'))=E=sum('2',A(j,'2'))-sum(k,v(j,k)*n(j,k));
EQ3..sum('4',A(j,'4'))=E=(0.99*sum('3',A('H2O','3')))+(0.96*sum('3',A('CH3OH','3')));
EQ4..sum('5',A(j,'5'))=E=sum('3',A('C02','3'))+sum('3',A('CH4','3'))+sum('3',A('C0','3'))+sum('3',A('H2','3'))+sum('3',A('N2','3'));
EQ5..sum('6',A(j,'6'))=E=0.9*sum('5',A(j,'5'));
EQ6..sum('7',A(j,'7'))=E=0.1*sum('5',A(j,'5'));
EQ7..pv=E=1000*sum('4',A(j,'4'));
EQ8..fc=E=1.5*T;
EQ9..p('m')=E=0.1*(T+sum('6',A(j,'6')));
EQ10..p('r')=E=0.2*sum('2',A(j,'2'));
EQ11..p('s1')=E=0.15*sum('3',A(j,'3'));
EQ12..p('s2')=E=0.15*sum('5',A(j,'5'));
EQ13..profit=E=pv-fc-p('m')-p('r')-p('s1')-p('s2');
MODEL QA /all/;
SOLVE QA using LP maximising profit;
</code></pre>Tall AlMon, 05 Mar 2018 11:42:43 -0500http://www.or-exchange.com/questions/15491/problem-with-gams-code-many-errorssummationlinear-programmingcodegamserrorLinearize fractional constraintshttp://www.or-exchange.com/questions/15420/linearize-fractional-constraints<p>How to linearize below LP problem : </p>
<p>\[
\max x_1 + x_2 + \ldots + x_n + y_1 + y_2 + \ldots + y_m\\
\text{s.t.}~ x_i + y_i \leq a_i ~\forall ~i \in N=M\\
x_1 + x_2 +..+ x_n \leq b_1\\
y_1 + y_2 +..+ y_m \leq b_2\\
x_1 + x_2 +..+ x_n + y_1 + y_2 +..+ y_m \leq b_3\\
x_1 * f_1/(x_1 + x_2 +..+ x_n) + .. + x_n * f_n/(x_1 + x_2 +..+ x_n)\\
~~~~- y_1 * g_1/(y_1 + y_2 +..+ y_m) + .. + y_m * g_m/(y_1 + y_2 +..+ y_m) \leq b_4\\
x_1,\ldots,x_n,y_1,\ldots,y_m \geq 0
\]</p>
<p>\(f_1, \ldots, f_n, g_1, \ldots, g_m\) are constants.</p>Amit SarkarThu, 22 Feb 2018 03:18:44 -0500http://www.or-exchange.com/questions/15420/linearize-fractional-constraintslinear-programmingoptimizationlinear-fractional-programmingMethod to encourage straight/smooth paths for TSPhttp://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tsp<p>I have a TSP modeled as a integer program with euclidean distance in the objective function. Often, the optimal solution will take a zig zagged path, which my customer finds less than ideal. In every case, there exists a very-near optimal solution which takes a more smooth and predictable path.</p>
<p><a href="https://imgur.com/a/Gif72">Example</a></p>
<p>Does anyone have any suggestions for encouraging such a path? What I have tried so far is changing the objective function from euclidean to a sum of the distance in each dimension:
SUM( Abs(x2-x1) ) + SUM( Abs(y2-y1) ) + SUM( Abs(z2-z1) )</p>
<p>This does indeed discourage zig zagging, but it is not 100% reliable on all problem sets, and I really wish there was a more reliable way to do this that would not sacrifice the euclidean distance consideration, which I would prefer to keep as a driver.</p>gtg489pWed, 31 Jan 2018 12:17:37 -0500http://www.or-exchange.com/questions/15348/method-to-encourage-straightsmooth-paths-for-tspintegeroptimizationlinear-programmingadditional constraint does not deliver a feasible solutionhttp://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution<p>Hello. I made a linear model in Excel and I use add-in OpenSolver in order to manage the resolution. The model works with 2112 variables, all of them boolean. There are 2112 constraints (which indicate that variables are boolean) and 264 constraints which requires to choose at least one boolean variables for each set (constraint=1). The target of model is minimize a total cost. I get a feasible satisfactory solution. I have tried to add an additional constraint which would limit the min value obtained (the target is : minimize value in cell XX ; the constraint indicates that such value should be not lower than a specific number). With this constraint I cannot get a feasible solution. I tried to manually change variables and I can find more than one feasible solution. So, despite of I dif not get any error message from model, I wonder in what direction I'd investigate to solve the problem. Thanks</p>cla68Tue, 30 Jan 2018 08:46:08 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solutionlinear-programmingconstraintConstraints vs Bounds for Decision Variableshttp://www.or-exchange.com/questions/15317/constraints-vs-bounds-for-decision-variables<p>What difference does it make to define the bounds of decision variables versus defining the bounds through constraints? Is one method better over the other in any way?</p>
<p>Just to clarify: In this context I am only comparing constraints that are of the nature of just describing what the upper limit or lower limit of a decision variable is.</p>Naveen DivakaranMon, 29 Jan 2018 10:58:29 -0500http://www.or-exchange.com/questions/15317/constraints-vs-bounds-for-decision-variableslinear-programmingboundsconstraintslinearization of a conditioal constrainthttp://www.or-exchange.com/questions/15315/linearization-of-a-conditioal-constraint<p>Hello,
I liniarized the following constraint:</p>
<pre><code>if(r1<r2)
A1<A2
</code></pre>
<p>r1 and r2 are integers in [1,30]
A1 and A2 are deciimals in ]0,10]</p>
<p>the linear form:</p>
<pre><code>r2 * b1 + 30 * ( 1-b1 ) - r1 >= 0
b2 - b1 >= 0
A2 * b2 + 30 * ( 1-b2 ) - A1 >= 0
</code></pre>
<p>Where b1 and B2 are two binary variables</p>
<p>However this is not working. Your hel is highly appreciated</p>nardinebastaMon, 29 Jan 2018 10:08:36 -0500http://www.or-exchange.com/questions/15315/linearization-of-a-conditioal-constraintlinearizationlinear-programmingBest Bound of LP during column generation?http://www.or-exchange.com/questions/15256/best-bound-of-lp-during-column-generation<p>Hi, I am solving an minimization LP with a subset of variables, and then calculating the reduced costs of all the variables in the master problem using shadow prices, then adding those to the master problem and iteratively re-solving until there are no variables with good reduced costs.</p>
<p>My problem is, many of the last iterations of the column generation loop only add a few variables and only improve the objective function by an infinitesimal and meaningless amount.</p>
<p>My question is, is there any way to calculate a best bound using results from the initial solve, so that I can terminate the column gen when the objective converges to that number? I remember reading something about taking the objective of the initial solve and subtracting/adding all the dual costs or something, but I keep getting a negative number. Thanks, Nathan Petty</p>gtg489pThu, 11 Jan 2018 11:29:19 -0500http://www.or-exchange.com/questions/15256/best-bound-of-lp-during-column-generationlinear-programmingoptimizationcolumn-generationlowerboundLinearize Ceiling Function in LPhttp://www.or-exchange.com/questions/15175/linearize-ceiling-function-in-lp<p>Is there a way to linearize the ceiling function so that it can be used as a constraint in an LP?</p>
<p>I want to include costs per every 50 units (x) as that is the capacity of the transportation vehicle. If the cost per transportation vehicle is 100, then the cost would be 100(<ceiling function="">x/50) so that in effect the number is rounded up so that both 51 units and 100 units will be charged 200 for the use of two transportation vehicles.</p>vilstratSat, 02 Dec 2017 17:39:20 -0500http://www.or-exchange.com/questions/15175/linearize-ceiling-function-in-lplinear-programmingHow to “fix” and solve this mathematical linear program?http://www.or-exchange.com/questions/15137/how-to-fix-and-solve-this-mathematical-linear-program<p>Hi,</p>
<p>I am working on an optimization problem dealing where the objective is to find a best placement of Virtual Machines given a physical network composed of several servers connected via switches/routers. The goal in the objective function is to maximize a profit. We associate to each server s a profit P_s.</p>
<p>The inputs of the mathematical program are the set of request R (which are the virtual machines and their inter-connectivity) and the physical network topology defined as a bidirectional graph.</p>
<p>I have two decision variables defined as follows :</p>
<pre><code>a[r,u,x] = 1 if virtual machine u of request r is deployed on server x 0 otherwise.
b[r,u,v,x,y] = 1 if physical link (x,y) of request r is allocated to virtual link (u,v) 0 otherwise.
</code></pre>
<p>Each virtual machines asks for a set of resources (cpu, memory, storage) and each server has a set of available resources (cpu, memory, storage). Each physical link has a capacity in terms of bandwidth and delay(latency) and connects two servers.</p>
<p>I have defined following this a set of constraints regarding the non violation of the servers and links capacity. </p>
<p>Here is the <a href="https://github.com/aziz86/test/blob/master/test.py">link</a> to the mathematical program I have implemented using Gurobi via Python API for a complete description.</p>
<p>For the sake of simplicity suppose we have a request of 3 VMs connected together in a linear topology say : </p>
<p>VM1<---> VM2 <---> VM3. </p>
<p>I am getting this output :</p>
<pre><code>Optimal solution found (tolerance 1.00e-04)
Best objective 9.200000000000e-02, best bound 9.200000000000e-02, gap 0.0000%
Optimal objective: 0.092
Variable X
-------------------------
a_request_id_i_j[0,1,7] 1
a_request_id_i_j[0,2,4] 1
a_request_id_i_j[0,3,1] 1
b_request_id_uv_xy[0,1,2,7,6] 1
b_request_id_uv_xy[0,1,2,3,4] 1
b_request_id_uv_xy[0,1,2,2,4] 1
b_request_id_uv_xy[0,2,3,4,3] 1
b_request_id_uv_xy[0,2,3,2,1] 1
b_request_id_uv_xy[0,2,3,4,2] 1
b_request_id_uv_xy[0,2,3,3,1] 1
b_request_id_uv_xy[0,2,3,3,4] 1
b_request_id_uv_xy[0,2,3,2,4] 1
</code></pre>
<p>The thing is that, the last two values are not correct i.e the constraint c1 and c2 if we verify them at hand will not yield the same value (I am not sure where is the mistake though!) while other values for beta are correct:</p>
<pre><code>b_request_id_uv_xy[0,2,3,3,4] 1
b_request_id_uv_xy[0,2,3,2,4] 1
</code></pre>
<p>The meaning of c1 and c2 is given a virtual link (u,v) connecting two VMs say u and v : if VM u is placed on x or VM v is placed on v then allocate a physical link where they are placed.</p>
<p>I formulated a constraint saying that if b[r,u,v,x,y] equals 1 then either VM u is placed on x or VM v is placed on y or both VMs are placed on x and y respectively by : b[r,u,v,x,y] <= a[r,u,x] + a[r,v,y]. This fixed the issue I mentioned earlier and gives this result :</p>
<pre><code>Optimal solution found (tolerance 1.00e-04)
Best objective 9.200000000000e-02, best bound 9.200000000000e-02, gap 0.0000%
Optimal objective: 0.092
Variable X
-------------------------
a_request_id_i_j[0,1,7] 1
a_request_id_i_j[0,2,4] 1
a_request_id_i_j[0,3,1] 1
b_request_id_uv_xy[0,1,2,7,6] 1
b_request_id_uv_xy[0,1,2,3,4] 1
b_request_id_uv_xy[0,1,2,2,4] 1
b_request_id_uv_xy[0,2,3,4,3] 1
b_request_id_uv_xy[0,2,3,2,1] 1
b_request_id_uv_xy[0,2,3,4,2] 1
b_request_id_uv_xy[0,2,3,3,1] 1
</code></pre>
<p>I am having an issue where several physical links are allocated to a virtual link. For instance, physical link (3,4) and (2,4) are allocated to the virtual link (1,2) i.e b_request_id_uv_xy[0,1,2,3,4]=1 and b_request_id_uv_xy[0,1,2,2,4]=1. I need to have only one. Do I have to reformulate it in such a way to say : allocate only one physical link where the VM (or the pair of VMs) is(are) placed ?</p>
<p>Another point is, I need to find a constraint that will help me to build a path between each pair of virtual machines. The model so far is not able to perform this task, I understand it has to be formulated first and I do not know how and where to start from to do so.</p>
<p>Any suggestions will be highly appreciated.</p>src_srcWed, 01 Nov 2017 21:53:01 -0400http://www.or-exchange.com/questions/15137/how-to-fix-and-solve-this-mathematical-linear-programlinear-programmingmathematical-modelingmathematical-optimizationPricing Out a New Variablehttp://www.or-exchange.com/questions/15047/pricing-out-a-new-variable<p>I am doing column gen on a min problem. I solve a relaxation of my problem using a subset of vars and calculate shadow prices for the constraints. Then I compute the reduced cost of new candidate variables using: objective coefficient of the new var minus the sumproduct of the shadow prices and the
constraint coefficients.</p>
<p>I solved one time and used the results to price 3 new variables. 1st variable priced out at -1.69. 2nd var priced out at -0.12. 3rd var priced out at 100.38. This is a min problem, so I know negative is good, positive is bad here, so the 3rd var is clearly not a good add to the problem. But how do I interpret the two negative ones? Since both are negative, do I know with certainty that adding both will result in both being used in the basis? Or is it only the variable with the most negative value that is certain to enter the basis?</p>
<p>For testing: I added the 2nd var(-0.12) and NOT the 1st var (-1.69) and solved again and the 2nd var I just added was not even used in the solution. If I add the 1st var(-1.69), it gets used in the solution and the reduced cost of 2nd var changed to positive number.</p>
<p>My main question is: is my calculation for pricing new vars wrong? (I don't think it's wrong because when I price vars in the basis, they price out at 0 - so atleast that checks out) Should all candidate vars with negative reduced cost enter the basis? Or is it only the most negative one with certainty? And the others with some likelyhood, perhaps after future iterations of solves with the new vars? Thanks, Nathan</p>gtg489pWed, 04 Oct 2017 15:06:00 -0400http://www.or-exchange.com/questions/15047/pricing-out-a-new-variableshadow-pricelinear-programmingoptimizationcolumn-generationreduced-costCan this problem be written as a linear program?http://www.or-exchange.com/questions/15029/can-this-problem-be-written-as-a-linear-program<p>I have this objective function:</p>
<p>\(
\text{minimize} \quad \frac{\sum^n_{i=1} {c_i x_i}}{1 - \sum^n_{i=1} c_i x_i} + \sum^n_{i=1} t_i c_i x_i
\)</p>
<p>subject to: </p>
<p>\(
\sum^n_{i=1} {c_i x_i} \leq 1
\)</p>
<p>\(
0 \le x \le 1
\)</p>
<p>where \(r\) and \(c\) are continuous given vectors.</p>
<p>Is it possible to convert it into a linear program?</p>
<p>Thank you.</p>ftamThu, 28 Sep 2017 08:27:20 -0400http://www.or-exchange.com/questions/15029/can-this-problem-be-written-as-a-linear-programlinear-programmingSolving linear program with 1 quadratic constraint complexityhttp://www.or-exchange.com/questions/14996/solving-linear-program-with-1-quadratic-constraint-complexity<p>Consider the following linear program,</p>
<p>\( \min y \\
xc_1 \leq c_2 + yz,\\
x = x_1 + \dots + x_n,\\
z \leq x_1 + x_2, \\
z \leq x_2 + x_3, \\
\vdots\\
z \leq x_{n-1} + x_n, \\
x,x_1, \dots, x_n,y,z \geq 0
\)</p>
<p>where \(c_1, c_2\) are constants. This is an example of quadratically constrained linear program where I have 1 quadratic constraint. I wish to find out if this problem is NP-Hard or not. The quadratic constraint can be expressed in the form \( \vec{y}M\vec{y}^T \) where \( M \) for my problem is not positive semidefinite (and thus, non-convex).</p>
<p>Listing the questions:</p>
<ol>
<li>Can this problem be transformed into a linear program by taking logs?</li>
<li>Is there any literature reference or reduction showing that linear programs with non-convex quadratic constraints is an NP-Hard problem? </li>
</ol>karmanautSun, 17 Sep 2017 12:02:33 -0400http://www.or-exchange.com/questions/14996/solving-linear-program-with-1-quadratic-constraint-complexitylinear-programmingoptimizationquadratic-programmingCommodity Shipment Optimization (LP) with Seasonality and Warehouses?http://www.or-exchange.com/questions/14991/commodity-shipment-optimization-lp-with-seasonality-and-warehouses<p>A classic example problem for linear programming is the commodity shipment problem, with multiple plants and markets and shipment costs between them. This problem is used as an example in many tutorials with many different algebraic modeling languages (AML), e.g. <a href="https://www.gams.com/products/simple-example/">https://www.gams.com/products/simple-example/</a> <a href="https://en.wikibooks.org/wiki/GLPK/GMPL_(MathProg)#Official_GLPK_examples">https://en.wikibooks.org/wiki/GLPK/GMPL_(MathProg)#Official_GLPK_examples</a></p>
<p>I am interested in finding an example of an extension of this formulation to include seasonality in production and consumption, with warehousing in between seasons. A two or four-season example in any AML would be helpful. I would have expected this to be a fairly standard type of problem in logistics. To date I have not been able to find anything online.</p>RMalesFri, 15 Sep 2017 14:23:53 -0400http://www.or-exchange.com/questions/14991/commodity-shipment-optimization-lp-with-seasonality-and-warehouseslinear-programmingoptimizationColumn Generation for TSPhttp://www.or-exchange.com/questions/14982/column-generation-for-tsp<p>I am using Python's PULP and CBC solver.</p>
<p>Does col gen for TSP make sense? If so, would the sub problem be a knapsack problem? (the knapsack is the sub problem for the cutting stock problem) which is the only example of col gen I could find anywhere. </p>
<p>The aim is to start with some subset of edges, solve the TSP and deal with subtours, and then solve a sub problem to determine good candidate edges to enter the primal.</p>
<p>PS. I understand that branch and price does this in a way during each step. My concern there is that branch and price would run slower, and I would like to have more control over which columns enter the problem and have the option to save these columns in my database for future solves to be added from the get-go.</p>gtg489pWed, 13 Sep 2017 11:39:51 -0400http://www.or-exchange.com/questions/14982/column-generation-for-tspcolumnlinear-programmingcolumn-generationmixed-integer-programmingHow to find an extreme ray of an unbounded LP?http://www.or-exchange.com/questions/14942/how-to-find-an-extreme-ray-of-an-unbounded-lp<p>I am trying to implement a Benders decomposition approach using the C++ Concert API. I do not want to rely on the getDual, getDuals, getRay or dualFarkas methods because I found that they are too dependent on the black box solver. I don't get the convergence ratio that I would like to see in my method. I am trying to improve that fact by calculating/ computing/ finding the actual extreme ray of the dual.</p>
<p>So I was wondering if any one of you have come accross this problem again and have come up with any methods to find an extreme ray. </p>
<p>The most obvious is solving a LP, but does anyone have any idea how the LP should look like in a generic case? </p>dimrizoWed, 30 Aug 2017 14:24:23 -0400http://www.or-exchange.com/questions/14942/how-to-find-an-extreme-ray-of-an-unbounded-lpbenders-decompositionextreme-raylinear-programmingconditional constraint linearizationhttp://www.or-exchange.com/questions/14883/conditional-constraint-linearization<p>how to put the following constraints in a linear form.</p>
<pre><code>if(T(i)<Tmax(i)) then x=0 else x=1
</code></pre>
<p>where T and Tmax are continuous in [0.0008-10] and x is a binary variable</p>
<p>thank u</p>nardinebastaTue, 01 Aug 2017 06:17:47 -0400http://www.or-exchange.com/questions/14883/conditional-constraint-linearizationconditional-constraintslinear-programmingconstraint-programmingHow to linearise max min constraints for multiple terms?http://www.or-exchange.com/questions/14868/how-to-linearise-max-min-constraints-for-multiple-terms<p>Say, min{a_1...a_m} < max{b_1...b_m}</p>Sulivan CheungFri, 21 Jul 2017 07:34:52 -0400http://www.or-exchange.com/questions/14868/how-to-linearise-max-min-constraints-for-multiple-termslinear-programmingTransportation Problem - with conditionshttp://www.or-exchange.com/questions/14865/transportation-problem-with-conditions<p>Hi. I'm trying to find a suitable analytics method to solve the following hypothetical problem. </p>
<p>I have 1000 salesmen that I want to send to 100 different destination addresses throughout a country. At the moment, they are sent fairly randomly - with some people needlessly travelling very large distances. </p>
<p>This I could solve fairly easily with a linear optimisation method - with distance between salesmen and destination addresses being the cost which I want to minimise, and the constraints being the number of salesman, and e.g. number of visits required (the Transportation Problem, I believe).</p>
<p>Here's the problem though. What if I wanted to add constraints/conditions which say for example: I want five highly paid salesman with experience in Virtual Reality to go this address, along with three low paid ones with experience in board games. To another address, I might want a dozen board game sellers, but half a dozen medium paid retro computer sellers. And to do all of this, which still minimising that journey length.</p>
<p>Is this possible with an Operations Research-type approach? Is it sensible to take this approach or are there cognitive computing/neural network methods which could get there more easily? Could it scale to 10,000 individuals?</p>
<p>Many thanks in advance!</p>Ginger1Thu, 20 Jul 2017 11:26:08 -0400http://www.or-exchange.com/questions/14865/transportation-problem-with-conditionslinear-programmingtravellingsalesmanArbitrage LPhttp://www.or-exchange.com/questions/14664/arbitrage-lp<p>Hello,</p>
<p>I am trying to finish a model of arbitrage calculation for a project. I have written the mathematical modelling and trying to make it work through CPLEX ILOG. You can find both Mathematical Model and inital code I wrote in the attachments.</p>
<p>Basically I have to make a working model that start with any currency and leaves the system returning to the same currency and creating an arbitrage value if there is any.</p>
<p>At first I though I can solve it as many times as there is currency and take the maximum arbitrage value but that is not efficient at all. To solve this issue I have introduced a dummy currency in the beginning. This dummy currency has 1-1 exchange rate with all the other currencies. It starts via going to any currency and returns to the dummy currency only by the currency it has entered. (To prevent issues such as from dummy currency to GBP, then GBP to JPY and JPY to Dummy creating a non-existen arbitrage value I introduced a boolean that states y[0][i] == y[i][0] for all i ensuring that dummy can enter and leave through a single currency).</p>
<p>You can find simple arbitrage calculations starting from a predetermined currecny but I couldn't find too much information about modelling for all possible currencies. (The single model just maximizes inflow-outflow to initial node for any of those who are interested)</p>
<p>Whenever I run the code cplex returns me a trivial solutions. Is the problem at my code or at my mathematical model? </p>
<p>Thank you for all your help!</p>
<p><a href="https://www.dropbox.com/sh/cwm8amp3x3glbgd/AAAF1lN1soYJZS64NaWPemqZa/OR?dl=0">https://www.dropbox.com/sh/cwm8amp3x3glbgd/AAAF1lN1soYJZS64NaWPemqZa/OR?dl=0</a> </p>OR-EnthusiastSat, 17 Dec 2016 19:02:51 -0500http://www.or-exchange.com/questions/14664/arbitrage-lplinear-programmingmathematical-modelingilogcplexHelp formulating/finding the general class of this problemhttp://www.or-exchange.com/questions/14399/help-formulatingfinding-the-general-class-of-this-problem<p>Imagine a bus serving a line with N stations (one direction). Each station, <code>i, i=1,…N,</code> has s_ij passengers that want to board the bus to go to j, for all j not equal to i. . So there are sum(sij) passengers waiting at station i to board the bus. Now, suppose that station m, is a very important station and we want to make sure there will be enough room on the bus to board waiting passengers. Assume the bus can choose how many people to board at each station, regardless of their destination. We now want to determine how many people at each of the stations (prior to station m) can board the train to ensure everyone at station m can board the bus.</p>
<p>What type of optimization problem is this? Typical network optimization problems involve maximizing flow or capacity, but not this sort of problem. How would one go about modeling this? Are there any examples of problems similar to this? </p>PepWed, 16 Nov 2016 20:07:01 -0500http://www.or-exchange.com/questions/14399/help-formulatingfinding-the-general-class-of-this-problemlinear-programmingnetworksinteger-programmingRun lingo through a simplex model design scripthttp://www.or-exchange.com/questions/14395/run-lingo-through-a-simplex-model-design-script<p>I'm having trouble configuring my script file for lingo to solve a basic simplex model on my windows PC:</p>
<pre><code>MODEL:
!Objectives defined and interpreted below:;
SETS:
LEATHER = X1 X2;
SLACK = S1 S2;
ENDSETS
DATA:
YIELD = 40;
HOUR = 60;
ENDDATA
MAX = 4X1 + 3X2;
! constraints below:;
@SUM(LEATHER(I): X(I)) + S1 = YIELD;
2X1 + X2 + S2 = HOUR
@FOR(LEATHER(I):
X(I) >= 0;
);
[Non-Negative Constraint] @FOR(SLACK(I):
S(I) >= 0;
);
END
</code></pre>feasibilityWed, 16 Nov 2016 12:56:54 -0500http://www.or-exchange.com/questions/14395/run-lingo-through-a-simplex-model-design-scriptlinear-programmingsimplexlingogoal-programmingLooking for a fractional solution on a LP model where some constraints are added on demandhttp://www.or-exchange.com/questions/14316/looking-for-a-fractional-solution-on-a-lp-model-where-some-constraints-are-added-on-demand<p>Hi,</p>
<p>I'm programming a linear programming model in C++ via CPLEX where the number of constraints is exponential. I'm looking for an optimal fractional solution and I would like to not add all the constraints from the beginning (because of the number of the number of constraints). So I have a separation oracle. I tried to use lazy constraint callback but I read that the lazy constraint callback is called only when an integer feasible candidate is found. I tried to use the user cut callback, but the callback was not called.</p>
<p>I would like to know how can I implement this model where some constraints are added on demand.</p>
<p>Regards,</p>
<p>Hugo.</p>HugoBragaFri, 21 Oct 2016 14:44:37 -0400http://www.or-exchange.com/questions/14316/looking-for-a-fractional-solution-on-a-lp-model-where-some-constraints-are-added-on-demandlinear-programminglazyconstraintsfractionalHow to model this with linear variables and constraintshttp://www.or-exchange.com/questions/14313/how-to-model-this-with-linear-variables-and-constraints<p>Imagine I have a bucket containing water with volume <code>v</code>. (The water volume is <code>v</code>, not the size of the bucket)</p>
<p>I have an indexed set of cups <code>1,...,n</code> with capacities <code>c</code><sub><code>1</code></sub><code>,...,c</code><sub><code>n</code></sub> where <code>c</code><sub><code>1</code></sub><code>+...+c</code><sub><code>n</code></sub><code>>v</code></p>
<p>I have to put all water into the cups. I have to completely fill up cups with smaller indices before I can start filling cups with larger indices.</p>
<p>Denote <code>x</code><sub><code>i</code></sub> to be the volume of water contained in cup <code>i</code>, where <code>x</code><sub><code>1</code></sub><code>+...+x</code><sub><code>n</code></sub><code>=v</code></p>
<p>I would model this using some binary integer variables <code>u</code><sub><code>i</code></sub> which denotes the use of cup <code>i</code>, and <code>f</code><sub><code>i</code></sub> which denotes cup <code>i</code> being full:</p>
<ul>
<li><code>x</code><sub><code>1</code></sub><code>+...+x</code><sub><code>n</code></sub><code>=v</code></li>
<li><code>x</code><sub><code>i</code></sub><code><=u</code><sub>i</sub><code>c</code><sub><code>i</code></sub> for <code>i=1,...,n</code></li>
<li><code>x</code><sub><code>i</code></sub><code>>=f</code><sub>i</sub><code>c</code><sub><code>i</code></sub> for <code>i=1,...,n</code></li>
<li><code>u</code><sub><code>i+1</code></sub><code>>=f</code><sub><code>i</code></sub> for <code>i=1,...,n-1</code></li>
<li><code>f</code><sub><code>i+1</code></sub><code>>=f</code><sub><code>i</code></sub> for <code>i=1,...,n-1</code></li>
</ul>
<p>The first constrant says that the total amount of water apportioned to the glasses must equal the starting volume <code>v</code>.</p>
<p>The second constraint says that each glass can hold at most its capacity, and only if the glass is used denoted by <code>u</code><sub><code>i</code></sub>, otherwise none at all.</p>
<p>The third constraint says that each glass must hold at least its capacity, and only if the glass is full denoted by <code>f</code><sub><code>i</code></sub>. This constraint together with the previous ensures the glass is exactly full if <code>u</code><sub><code>i</code></sub><code>=f</code><sub><code>i</code></sub><code>=1</code>.</p>
<p>The fourth constraint says that a glass can only be used if the previously indexed glass is full.</p>
<p>The fifth constraint says that a glass can only be full if the previously indexed glass is also full.</p>
<p>Now, aside from any errors I may have made in this question, this method works, and it makes perfect sense to me. But when I use a solver such as XPRESS, CPLEX, or Gurobi, I can see that the solver eliminates the integer variables and ends up with a purely linear formulation.</p>
<p>The binary variables aren't true variables. They can only have one possible value in any feasible solution. So in a way, it makes sense that they can be eliminated, but I'm not sure how.</p>
<p>Can someone please show me how to model this without any binary or integer variables?</p>
<p>This problem is a small part of a larger problem, and <code>v</code> is actually also a variable involved elsewhere.</p>
<p>Thank you.</p>OzzahThu, 20 Oct 2016 20:36:20 -0400http://www.or-exchange.com/questions/14313/how-to-model-this-with-linear-variables-and-constraintslinear-programmingbinary-programmingTrouble in retrieving dual values in an LPhttp://www.or-exchange.com/questions/14244/trouble-in-retrieving-dual-values-in-an-lp<p>Hi everybody,
I'm a beginner in Cplex trying to solve a problem (linear programming) to get dual values related to the constraints so as to use those values for the next application. My preliminary search reveals that we can get the dual values by using cplex.getDuals() function. I also understand that a prerequisite to use getDuals() is to write the constraints using IloRangeArray(). I have applied these in my problem context as follows: </p>
<pre><code>IloModel model(env);
IloRangeArray constraints(env, Nb_constraints); // Nb_constraints are total number of constraints
// data input
// a sample constraint is given as
for( .. ){
for( .. ){
for( .. ){
constraints.add(sum_food_inv <= capacity[s][w] * Delta_wh_hire_contract[s][w]);
}
}
}
model.add(constraints);
.
.
cplex.solve();
double vals[Nb_constraints]; // this is the array which stores the dual values.
for(int c=0; c<Nb_constraints; c++)
cplex.getDual(constraints[c]);
</code></pre>
<p>However, with this code though the program is able to solve the LP, it is unable to produce the dual values. Can anybody help me out to understand where am I going wrong with the code? </p>
<p>I greatly appreciate any help in this regards. </p>AjinkyaMon, 03 Oct 2016 06:47:48 -0400http://www.or-exchange.com/questions/14244/trouble-in-retrieving-dual-values-in-an-lplinear-programmingilocplexcplexdualIs there a general theory of reduced costs?http://www.or-exchange.com/questions/14217/is-there-a-general-theory-of-reduced-costs<p>The concept of <em>reduced cost</em> appears virtually in any work about linear programming. I have a feeling, however, that the concept itself goes well beyond the boundaries of linear optimisation. For instance, there is an obvious similarity between the concept of reduced cost in linear programming and the cost of a <em>move</em> in local search (the simplex algorithm itself is a form or local search, after all). I was wondering where there exists a general theory of reduced costs, that transcends the boundaries of a specific optimisation technique. Maybe this is a trivial subject, but I haven't encountered any work that studies reduced costs under a unifying theory. Can anyone provide pointers to the literature, if available?</p>Tommaso UrliThu, 22 Sep 2016 20:23:58 -0400http://www.or-exchange.com/questions/14217/is-there-a-general-theory-of-reduced-costsreduced-costlinear-programminglocal-searchtheoryConstraint formulationhttp://www.or-exchange.com/questions/14207/constraint-formulation<p>Hello,</p>
<p>My problem consists to determine the exact period of patient treatment.
The duration of period is 30 minutes.</p>
<pre><code>Indices:
P patients
T periods
M doctor
Parameter:
dur[p] : the treatment duration of patient p
Decision Variables
Occup[m][t] {1: if a doctor is available at period t, 0:else}
Trait[p][t]:{1: If patient p is treated at period t, 0:else}
</code></pre>
<p>=> A patient is treated once on T periods.</p>
<p>I have this constraint:</p>
<p>At period t, if the sum of patient "p" treatment time with patients' treatment time to come before him does not exceed 30 minutes then
Trait[p][t]=1 else
Trait[p][t]=0</p>
<p>The formulation of constraint on CPLEX opl is</p>
<pre><code> forall(m in doctors, t in periods)
sum(p in 1..P)(dur[p]*Trait[p][t])<=30*Occup[m][t];
</code></pre>
<p>My problem when i add another constraint some patients will not treated at the exact period.</p>
<p>My question is: how can I force this constraint to determine the exact treatment period.</p>
<p>Best regards</p>lollaMon, 19 Sep 2016 12:17:40 -0400http://www.or-exchange.com/questions/14207/constraint-formulationlinear-programmingcplexconstraintConverting conditions to MILPhttp://www.or-exchange.com/questions/14146/converting-conditions-to-milp<p>Hello all
I want to convert following conditions to MILP model. Actually, the value of a variable (y) is determined as follows. can anyone help me? </p>
<p>y=alpha(1) if x < x(1);
y=alpha(2) if x(1)<= x <x(2); y="alpha(3)" if="" x(2)<="x" <x(3);="" .="" .="" .="" y="alpha(n)" if="" x(n-1)<="x" <x(n);="" y="alpha(n+1)" if="" x="">= x(n);</p>
<p>, where alpha(i) is a constant and are nonincreasing.
it is worthy to mention that these conditions are in objective function which should be minimized. </p>Amin-ShMon, 29 Aug 2016 04:32:15 -0400http://www.or-exchange.com/questions/14146/converting-conditions-to-milplinear-programmingmixed-integer-programming