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

asked 30 Jan, 08:46

cla68's gravatar image

cla68
111
accept rate: 0%

When describing the original 264 constraints, did you mean "constraint >= 1" rather than "constraint = 1"?

(30 Jan, 13:53) Paul Rubin ♦♦

"... 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?

(30 Jan, 13:54) Paul Rubin ♦♦

You could maybe post the mathematical programming model (a mathematical description) you are trying to solve. That way we might give you better advice.

(31 Jan, 01:55) Sune

I will try to post a math description of model. I do hope to be able to do it in a compact text

(31 Jan, 02:27) cla68

the description of model is quite long and exceeds max characters allowed by post. How can I manage this issue? thanks

(31 Jan, 05:04) cla68

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?

(31 Jan, 05:34) Sune
showing 5 of 6 show 1 more comments

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 maximum value of your objective function is smaller than the value you use as a minimum value.

link

answered 30 Jan, 13:36

Sune's gravatar image

Sune
913412
accept rate: 19%

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)

link

answered 30 Jan, 16:34

cla68's gravatar image

cla68
111
accept rate: 0%

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...

link

answered 30 Jan, 17:24

cla68's gravatar image

cla68
111
accept rate: 0%

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].

link

answered 31 Jan, 17:32

cla68's gravatar image

cla68
111
accept rate: 0%

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]1+vc[i][2]2+vc[i][3]3+ vc[i][4]4+vc[i][5]5+vc[i][6]6+vc[i][7]7+vc[i][8]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)Q[j]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)Q[j]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)Q[j]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.

link

answered 03 Feb, 10:10

cla68's gravatar image

cla68
111
accept rate: 0%

Maybe is easier written in this way:

(i=1)^212▒∑(j=1)^52▒(1-〖((Sc〗_i=〖Sp〗_j )+0)×Q_j×c_ij )

where:

〖Sc〗i=〖vc〗(i[1])×1+〖vc〗(i[2])×2+〖vc〗(i[3])×3+〖vc〗(i[4])×4+〖vc〗(i[5])×5+〖vc〗(i[6])×6+〖vc〗(i[7])×7+〖vc〗_(i[8])×8

〖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

link

answered 03 Feb, 10:42

cla68's gravatar image

cla68
111
accept rate: 0%

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

link

answered 05 Feb, 02:06

cla68's gravatar image

cla68
111
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×228
×36

Asked: 30 Jan, 08:46

Seen: 271 times

Last updated: 05 Feb, 02:06

OR-Exchange! Your site for questions, answers, and announcements about operations research.