Answers to: additional 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>enMon, 05 Feb 2018 02:06:19 -0500Answer by cla68http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15378<p>The model is not linear because I multiply variables each other. I should introduce further boolean variables.
How can I linearize the statement IF(A=B, 0 , K)? thanks</p>cla68Mon, 05 Feb 2018 02:06:19 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15378Answer by cla68http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15369<p>Maybe is easier written in this way:</p>
<p>∑<em>(i=1)^212▒∑</em>(j=1)^52▒(1-〖((Sc〗_i=〖Sp〗_j )+0)×Q_j×c_ij ) </p>
<p>where:</p>
<p>〖Sc〗<em>i=〖vc〗</em>(i[1])×1+〖vc〗<em>(i[2])×2+〖vc〗</em>(i[3])×3+〖vc〗<em>(i[4])×4+〖vc〗</em>(i[5])×5+〖vc〗<em>(i[6])×6+〖vc〗</em>(i[7])×7+〖vc〗_(i[8])×8</p>
<p>〖Sp〗_j=〖vp〗_j[1] ×1+〖vp〗_j[2] ×2+〖vp〗_j[3] ×3+〖vp〗_j[4] ×4+〖vp〗_j[5] ×5+〖vp〗_j[6] ×6+〖vp〗_j[7] ×7+〖vp〗_j[8] ×8</p>cla68Sat, 03 Feb 2018 10:42:32 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15369Answer by cla68http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15366<p>Hello. I tried to work around the problem separating each contribute to target value (objective). It seems which I found the main issue, where part of model is not linear. Here is the mathematical representation of not linear part:
i=1 to 212, number of component;
j=1 to 52, number of products;
k=1 to 8, number of suppliers (for components and/or products);
Supplier of component [i] = Sc[i], which is calculated as: vc[i][1]<em>1+vc[i][2]</em>2+vc[i][3]<em>3+ vc[i][4]</em>4+vc[i][5]<em>5+vc[i][6]</em>6+vc[i][7]<em>7+vc[i][8]</em>8 , where vc[i][k] is a variable boolean . Sc[i] is an integer number (1,2,3,4,5,6,7, or 8).
Supplier of product [j] = Sp[i], calculated in the same way of Sc[i], but with sets of variable vp[j][k].
For each component [i] is calculated the total quantity which is required to be delivered from supplier Sc[i] to central warehouse. In case the supplier of product [j] where component [i] is required is the same of Sc[i] then the quantity transported is zero. This matter is modelized in this way:
(1-((Sc[i]=Sp[j])+0)<em>Q[j]</em>c[i][j] , where Q[j] is total quantity of product [j] and c[i][j] is the unit quantity of component [i] used in product [j].
Total quantity of component [i] which needs a transportation is SUM((1-((Sc[i]=Sp[j])+0)<em>Q[j]</em>c[i][j])[j=1 to 52].
The overall quantity of components which require a transportation is: SUM(SUM((1-((Sc[i]=Sp[j])+0)<em>Q[j]</em>c[i][j])[j=1 to 52]) [i=1 to 212].
This final formula is recognized as not linear.
How can I make it linear?
Thanks in advance for any help.</p>cla68Sat, 03 Feb 2018 10:10:55 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15366Answer by cla68http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15355<p>The model considers seven different costs managed in a logistic system. Cost for purchasing components (Cpc) required for a set of products, Transportation cost for moving components from suppliers to central warehouse (Ctc1), Picking cost for preparing components to be delivered to product’s assembling sites (Cpc), Stock cost for maintaining components at warehouse before assembling (Csc), Transportation cost for moving components from central warehouse to suppliers (Ctc2), Cost for assembling products (Cpp), Transportation cost of products from suppliers to central warehouse (Ctp).
The objective is minimize TCO = Cpc + Ctc1 + Cpc + Csc + Ctc2 + Cpp + Ctp
Cpc is the sum of total purchasing components’ costs. Component i=212. Suppliers involved k=8.
Cpc= sum( sum (Pc[i][k] x vc[i][k])[k=1 to 8] x Qc[i]) [i=1 to 212] , where Pc[i][k] is the unit price of component [i] supplied by supplier [k], vc[i][k] is boolean variable (0 or 1) which makes the choice of what supplier is selected. Qc[i]: yearly quantity required for component [i]. Constraints : vc[i][k] Boolean, sum(vc[i][k]) [k=1 to 8] = 1 (only one supplier is selected for each component [i])
Ctc1 = sum(sum(Cts[k] x vc[i][k]) [k=1 to 8] x Qcx[i]) [i=1 to 212] , where Cts[k] is the unit cost of transportation per package from/to supplier [k], Qcx[i] is the number of packages referred to component [i].
Cpp = sum( sum (Pp[j][k] x vc[i][k])[k=1 to 8] x Qp[j]) [j=1 to 522] , where Pp[j][k] is the unit price of product [j] assembled by supplier [k], vc[i][k] is boolean variable (0 or 1) which makes the choice of what supplier is selected. Qp[j]: yearly quantity required for product [j]. Constraints : vc[i][k] Boolean, sum(vc[i][k]) [k=1 to 8] = 1 (only one supplier is selected for each product [j])
Ctp = sum(sum(Cts[k] x vc[i][k]) [k=1 to 8] x Qpx[i]) [i=1 to 52] , where Cts[k] is the unit cost of transportation per package from/to supplier [k], Qpx[j] is the number of yearly packages (pallets) referred to product[j].
Qcx[i] is calculated as ratio sum(A/ Ncx[i]) [i=1 to 212] where A = sum((1-((Sc[i]= Sp[j])+0)) x Qcp[i][j] x Qp[j])[j=1 to 52] . Ncx[i] is the quantity of component [i] which are packed in one unit (one package). Qcx[i] should be approximated to integer up but I am not able to manage this issue without introducing non-smooth functions (ROUNDUP , INT or similar).
The syntax (1-((Sc[i]= Sp[j])+0)) avoids to use in Excel IF function, which is not linear. So, (1-((Sc[i]= Sp[j])+0)) = 1 if supplier of component [i] is not the same of supplier of product [j], otherwise the result is zero (0). Qcp[i][j] is the unit quantity of component [i] used inside product [j]. Qp[j] is the yearly quantity required for product [j].
Sc[i] is calculated as: vc[i][1]x1+vc[i][2]x2+vc[i][3]x3+ vc[i][4]x4+vc[i][5]x5+vc[i][6]x6+vc[i][7]x7+vc[i][8]x8. The result is a integer number between 1 to 8. In the same way Sp[j] is calculated as: vp[i][1]x1+vp[i][2]x2+vp[i][3]x3+vp[i][4]x4+vp[i][5]x5+vp[i][6]x6+vp[i][7]x7+vp[i][8]x8. The result is a integer number between 1 to 8.
Cpc is calculated as sum(sum((1-((Sc[i]= Sp[j])+0)) x (((F[i]=”VOL”)+0) + (1-((F[i]=”VOL”)+0))*Lp[j])) x CP) [j=1 to 52]) [i=1 to 212] , where F[i] is a costant (string) for each component [i] which indicates if its high volume (=”VOL”) or not (= blank) component. Lp[j] is the number of lots of product [j] required each year. CP is a constant which represents the unit cost/component for Picking activity. So, the formula says: if the component is “VOL” then we need to prepare picking each time we produce a lot of product [j], otherwise we can prepare/picking component only one time per year. If supplier of component [i] is the same of product [j] then the picking cost is zero (0).
Csc is the cost for managing stock of components. SUM((1-((A=0)+0)) x ((Moq[i]/ Ncx[i] /2) x Cplt x 12 + Moq[i] * Std[i] x Cfin /2 )) [i=1 to 212] . Where A = sum((1-((Sc[i]= Sp[j])+0)) x Qcp[i][j] x Qp[j])[j=1 to 52] (as above). Moq[i] is the minimun quantity which is possible purchase for component [i]. Cplt is constant (cost for managing one pallet at stock for one month. Std[i] is a constant, standard price for component [i]. Cfin is a constant and represents the yearly cost of money.
Ctc2 = sum(sum(Cts[k] x vc[i][k]) [k=1 to 8] x Qcx[i]) [i=1 to 212] , where Cts[k] is the unit cost of transportation per package from/to supplier [k], Qcx[i] is the number of packages referred to component [i]. Qcx[i] is calculated as above. The only difference compared to Ctc1 is the fact that the unit transporation cost is referred to supplier of product [j] instead of supplier of component [i].</p>cla68Wed, 31 Jan 2018 17:32:48 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15355Comment by Sune on cla68's questionhttp://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15343<p>Don't you have a description in the form \[\min\{ c^Tx\ :\ x\in\mathcal{X},\ x\in\{0,1\}\}\]? That is, some sort of compact description?</p>SuneWed, 31 Jan 2018 05:34:40 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15343Comment by cla68 on cla68's questionhttp://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15342<p>the description of model is quite long and exceeds max characters allowed by post. How can I manage this issue? thanks</p>cla68Wed, 31 Jan 2018 05:04:31 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15342Comment by cla68 on cla68's questionhttp://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15341<p>I will try to post a math description of model. I do hope to be able to do it in a compact text</p>cla68Wed, 31 Jan 2018 02:27:13 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15341Comment by Sune on cla68's questionhttp://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15340<p>You could maybe post the mathematical programming model (a mathematical description) you are trying to solve. That way we might give you better advice.</p>SuneWed, 31 Jan 2018 01:55:54 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15340Answer by cla68http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15332<p>I have tried to use Solver premium trial in order to get some extra info from my model. The verdict indicates that model is not linear (despite I was sure that's). It's considered a NSP/MIP model with 4064 bounds (2032 linear + 2032 smooth) 255 functions (254 linear, 254 smooth ...?) , 2032 variables (in the meantime I re-adjusted model in order to reduce variables). the Excel function SUMPRODUCT should not be a non-linear formula, but the fact that I use it in this way [SUMPRODUCT((RANGE1=XX)*(RANGE2))] probably makes it non-linear because RANGE1=XX is seen as an IF condition... I suppose. In this case I do not know how to manage this issue and replace this formula withi a linear formula....in case this is the problem of my model...</p>cla68Tue, 30 Jan 2018 17:24:52 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15332Answer by cla68http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15331<p>Thanks. So, I followed your suggestion: I used "optimal" solution (expected min cost as model target) as benchmark. I have copied the value in another cell and set as objective a third cell where I put the formula of difference between the original objective cell and the new one with the value. This cell is the new objective equal to zero (=0). The solver fails and cannot find a feasible solution. So, my assumption that model was ok because found a solution which seemed to be the best (min) one was wrong. I guess how to proceed. Despite of number of variables the model is not so complex. What's the best way to proceed in order to validate it and find the error inside?
(the 264 constraints are set as = 1)</p>cla68Tue, 30 Jan 2018 16:34:12 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15331Comment by Paul Rubin on cla68's questionhttp://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15329<p>"... and I can find more than one feasible solution". These solutions make the value of cell XX greater than or equal to the specified number?</p>Paul RubinTue, 30 Jan 2018 13:54:28 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15329Comment by Paul Rubin on cla68's questionhttp://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15328<p>When describing the original 264 constraints, did you mean "constraint >= 1" rather than "constraint = 1"?</p>Paul RubinTue, 30 Jan 2018 13:53:16 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution#15328Answer by Sunehttp://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15327<p>If you know an optimal solution to your problem, try setting the minimum value in the constraint equal to the optimal solution value. If your problem doesn't report a solution, you know there's a bug in your implementation. On the other hand, if your model finds a solution with this minimum value, you know that the <em>maximum</em> value of your objective function is smaller than the value you use as a minimum value.</p>SuneTue, 30 Jan 2018 13:36:31 -0500http://www.or-exchange.com/questions/15326/additional-constraint-does-not-deliver-a-feasible-solution/15327