Questions Tagged With optimizationhttp://www.or-exchange.com/tags/optimization/?type=rssquestions tagged <span class="tag">optimization</span>enThu, 22 Feb 2018 03:18:44 -0500Linearize 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-programmingMin function in objective problemhttp://www.or-exchange.com/questions/15417/min-function-in-objective-problem<p>How can I convert this Min function (bold highlihted) in objective problem into simple mathematical equation:</p>
<p>Min a[i]*(x[i]-y[i]) + b[i] <strong>min(x[i],M-c[i])</strong></p>
<p>s.t. c[i]-x[i]+y[i]≤M</p>
<p>Here x[i] and y[i] are decision variables.</p>fadizTue, 20 Feb 2018 05:58:37 -0500http://www.or-exchange.com/questions/15417/min-function-in-objective-problemoptimizationMethod 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-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-generationlowerboundLooking for an equivalent formulation of an optimization problem in such a way that the CVX solver understands and solves it.http://www.or-exchange.com/questions/15195/looking-for-an-equivalent-formulation-of-an-optimization-problem-in-such-a-way-that-the-cvx-solver-understands-and-solves-it<p>I need to solve the following problem:</p>
<p>\[\left\{\begin{array}{lll} {\displaystyle \inf_{(\beta,\lambda)\in\mathbb{R}^{2},s\in\mathbb{R}^{N}} } & {\displaystyle \lambda \varepsilon +\frac{1}{N}\sum_{i=1}^{N}s_{i}} &\\
\mbox{subject to} &\beta^{2}+4a_{i}\lambda\beta+4a_{i}^{2}\lambda-4\lambda s_{i}+4s_{i}\leq 0 & \forall i\leq N \\
&\lambda >1& \\ & \beta\geq 0.& \end{array}\right.\tag{\(\bigstar\)}\]</p>
<p>where \(\varepsilon, a_{i}\in \mathbb{R}\) are fixed for all \(i=1,2,\ldots,N\).</p>
<p>My intention is to use <strong><em>CVX</em></strong> (see this <a href="http://cvxr.com/cvx/">link</a>), but I have problems, as it is stated ( \(\bigstar\) ) the solver does not interpret it.</p>
<p><strong>Remark:</strong> I do not know if the following is useful, but note that the constrain
\[\beta^{2}+4a_{i}\lambda\beta+4a_{i}^{2}\lambda-4\lambda s_{i}+4s_{i}\leq 0 \quad \forall i\leq N\]
can be changed by
\[\frac{\beta^{2}}{4(\lambda-1)}+\frac{\lambda}{\lambda-1}a_{i}(\beta+a_{i})-s_{i}\leq 0 \quad \forall i\leq N\]
I showed that the function \(f:\mathbb{R}^{3}\rightarrow \mathbb{R}\) given by \(f(\beta,\lambda,s):=\frac{\beta^{2}}{4(\lambda-1)}+\frac{\lambda}{\lambda-1}a(\beta+a)-s\) is convex in \(\mathbb{R}\times\mathbb{R}_{\geq 1}\times\mathbb{R}\) for any \(a\in \mathbb{R}\).</p>
<p><strong>My attempt:</strong> <strong><em>CVX</em></strong> can solve geometric programs (<a href="https://en.wikipedia.org/wiki/Geometric_programming">GP</a>), the problem is that ( \(\bigstar\) ) is not a geometric program because \( a_{i} \) can be negative, my idea was to express ( \(\bigstar\) ) as a geometric program but what arrived was the following equivalent formulation:</p>
<p>\(\left\{ \begin{array}{lll}
{\displaystyle \inf_{\beta,\lambda,s_{i},r_{i}} } & r_{0} & \\
\mbox{subject to} & \varepsilon\lambda r_{0}^{-1}+\frac{1}{N}\sum_{i=1}^{N}s_{i}r_{i}\leq 1 &\\
&\left.\begin{array}{l}\beta^{2}r_{i}^{-1}+4a_{i}\lambda \beta r_{i}^{-1}+4a_{i}^{2}\lambda r_{i}^{-1}+4s_{i}r_{i}^{-1}+r_{i}^{-1}\leq 1 \\ 4\lambda s_{i}r_{i}^{-1}+r_{i}^{-1}\geq 1 \end{array}\right\} &\forall i\in I_{1} \\
&\left.\begin{array}{l}\beta^{2}r_{i}^{-1}+4a_{i}^{2}\lambda r_{i}^{-1}+4s_{i}r_{i}^{-1}+r_{i}^{-1}\leq 1 \\ 4\lambda s_{i}r_{i}^{-1}+4(-a_{i})\lambda\beta r_{i}^{-1}+r_{i}^{-1}\geq 1 \end{array}\right\} &\forall i\in I_{2} \\
& \lambda >1 & \\
& \beta\geq 0.
\end{array}\right.\tag{\(\blacktriangle\)}\)</p>
<p>where \( I_{1}:=\left\{i \:|\: 0<i\leq N \mbox{ such that } a_{i}\geq 0 \right\} \) and \( I_{2}:=\left\{i \:|\: 0<i\leq N \mbox{ such that } a_{i}< 0 \right\} \).</p>
<p>The problem of ( \(\blacktriangle\) ) is that it is not yet a geometric program, the difficulty is in the constrains \(\geq 1\). The only advantage that has ( \(\blacktriangle\) ) is that all constrains are in terms of posynomials, really do not know if this is an advantage because <strong><em>CVX</em></strong> has not yet interpreted it, it shows an error in the restrictions \(\geq 1\).</p>
<p>Since my attempt has not had the desired results I hope that someone will read this problem, my can help with a way to solve it or a way of expressing it in such a way that CVX can solve it.</p>Diego FonsecaMon, 11 Dec 2017 20:11:50 -0500http://www.or-exchange.com/questions/15195/looking-for-an-equivalent-formulation-of-an-optimization-problem-in-such-a-way-that-the-cvx-solver-understands-and-solves-itoptimization-softwareoptimizationconvex-optimizationnonlinear-optimizationSolving TSP with Knapsack like constraintshttp://www.or-exchange.com/questions/15130/solving-tsp-with-knapsack-like-constraints<p>Dear all,</p>
<p>I am a newbie to Operations Research in general and currently working on implementation of a scenario that involves solving Travelling Salesman Problem(TSP) with knapsack constraints. This class of problem is also sometimes referred to as "Sightseeing Problem" (<a href="http://www-m9.ma.tum.de/material/sightseeing/">http://www-m9.ma.tum.de/material/sightseeing/</a> - you can change the language to EN below there) </p>
<p>The scenario has several locations and travelling to these locations incurs travelling costs. At each of these location there is a prize be picked up. The sales person has time constraints(has a fixed time available) and cost constraints(like in maximum capacity constraints). </p>
<p>The objective is to maximize the number of locations visited while the constraints of cost and time are not violated. Visiting each location is NOT mandatory. </p>
<p>I am wondering if there are any OpenSource codes/libraries which are able to solve such scenarios. I would really appreciate if you could suggest me any code/library that you might think are suitable for such applications. The codes which I am aware so far are only able to solve TSP and Knapsack independently. Could anybody help me with this please?</p>
<p>Many thanks,</p>
<p>Best Regards,</p>
<p>-Rama</p>ramaMon, 30 Oct 2017 15:47:46 -0400http://www.or-exchange.com/questions/15130/solving-tsp-with-knapsack-like-constraintsoptimizationcombinatorial-optimizationknapsacktspopensourceVideo Courses in Optimizationhttp://www.or-exchange.com/questions/15106/video-courses-in-optimization<p>Dear all</p>
<p>I like to know what video courses in optimization and operations research are publicly available (which are taught in universities)? If you know some courses, please share their links.</p>Amin-ShWed, 18 Oct 2017 18:07:47 -0400http://www.or-exchange.com/questions/15106/video-courses-in-optimizationoptimizationPricing 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-costSolving 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-programmingoptimizationLinearization of constraint with several non-linear termshttp://www.or-exchange.com/questions/14954/linearization-of-constraint-with-several-non-linear-terms<p>Hello all,</p>
<p>I need to implement this constraint in an MILP formulation:</p>
<p>$$(x_{1} \cdot C_{1} + x_{2}) \cdot x_{3} \geq (x_4-x_2)^2 \cdot C_2$$</p>
<p>where \(x_{1}\) is an integer decision variable, \(x_2\), \(x_3\) and \(x_4\) are real decision variables, and \(C_1\) and \(C_2\) are constants.</p>
<p>Is there a way to linearize this expression? The integer variable \(x_1\) could be relaxed to a real variable if that would make things easier.</p>
<p>Thank you very much!</p>Luis BadesaMon, 04 Sep 2017 12:46:52 -0400http://www.or-exchange.com/questions/14954/linearization-of-constraint-with-several-non-linear-termslinearizationoptimizationlinearization-techniqueHow to solve this optimization problem?http://www.or-exchange.com/questions/14947/how-to-solve-this-optimization-problem<p>Hi, I need to formulate and solve this optimization problem.</p>
<p>\[\min \sum_{t\in\mathcal{T}}p_t\]</p>
<p>s.t. c1: \[\sum_{t\in \mathcal{T}}w_t\log_2\left(1+\frac{h}{w_tn_0}p_t\right)= TR\]</p>
<p>c2: \[\alpha\sum_{t\in \mathcal{T}}w_t\log_2\left(1+\frac{h}{w_tn_0}p_t\right)\le D\]</p>
<p>c3: \[p_t\ge 0\]</p>
<p>Here,</p>
<p>The left side of c1 is the total resources assigned and the right side is the desired amount of resources.</p>
<p>\(\alpha\) is the price per unit of resources and \(D\) is the maximum amount that can be afforded.</p>
<p>My requirement is: if \(D\) is large enough, then c1 is satisfied. If the maximum affordable amount \(D\) is not large enough to buy the desired amount of resources, then the user receives according to the amount it can afford.</p>
<p>I am not sure whether my formulation is CORRECT or not.</p>
<p>Note that the \(=\) sign can be replaced with \( \le\) if the optimality is not affected.
Here,
\(p_t\) is the optimization variable.</p>
<p>Here, \(\alpha\), \(h\), \(T\), \(R\), \(D\), \( \eta_0\), and \( w_t\) are real and positive. \(\mathcal{T}\) is index set with \(T\) elements, i.e., \(\mathcal{T}=\{1,2,\cdots, T\}\).</p>
<p>Some one please help me to solve this.</p>dipFri, 01 Sep 2017 06:14:21 -0400http://www.or-exchange.com/questions/14947/how-to-solve-this-optimization-problemoptimizationconvex-optimizationSolving L1 Regularized Least Squares Over Complex Domainhttp://www.or-exchange.com/questions/14770/solving-l1-regularized-least-squares-over-complex-domain<p>I would like to solve the following <a href="https://en.wikipedia.org/wiki/Regularized_least_squares">Regularized Least Squares</a> Problem (Very Similar to <a href="https://en.wikipedia.org/wiki/Lasso_(statistics)">LASSO</a>):</p>
<p>$$ \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}^{2} + \lambda {\left\| x \right\|}_{1} $$</p>
<p>Where \( A \in {\mathbb{R}}^{m \times n} \) and \( b \in {\mathbb{R}}^{m} \).<br>
For simplicity one could define \( f \left( x \right) = \frac{1}{2} {\left\| A x - b \right\|}^{2} \) and \( g \left( x \right) = \lambda {\left\| x \right\|}_{1} \).</p>
<p>For \( x \in {\mathbb{R}}^{n} \) the solution can be achieved using <a href="https://en.wikipedia.org/wiki/Subgradient_method">Sub Gradient Method</a> or <a href="https://en.wikipedia.org/wiki/Proximal_gradient_method">Proximal Gradient Method</a>. </p>
<p>My question is, how can it be solved for \( x \in {\mathbb{C}}^{n} \) (Assuming \( A \in {\mathbb{C}}^{m \times n} \) and \( b \in {\mathbb{C}}^{m} \))?<br>
Namely if the problem is over the complex domain.</p>
<p>For instance, what is the Sub Gradient?<br>
What is the Prox (Shrinkage of Complex Number)?</p>
<p>Thank You. </p>
<h3>My Attempt for Solution 001</h3>
<p>The Gradient of \( f \left( x \right) \) is given by:</p>
<p>$$ {\nabla}_{x} f \left( x \right) = {A}^{H} \left( A x - b \right) $$</p>
<p>The Sub Gradient of \( g \left( x \right) \) is given by:</p>
<p>$$ {\partial}_{x} g \left( x \right) = \lambda \operatorname{sgn} \left( x \right) = \lambda \begin{cases}
\frac{x}{ \left| x \right| } & \text{ if } x \neq 0 \
0 & \text{ if } x = 0
\end{cases} $$ </p>
<p>Namely it is the Complex <a href="https://en.wikipedia.org/wiki/Sign_function">Sign Function</a>.</p>
<p>Then, the Sub Gradient Method is given by:</p>
<p>$$ {x}^{k + 1} = {x}^{k} - {\alpha}_{k} \left( {A}^{H} \left( A {x}^{k} - b \right) + \lambda \operatorname{sgn} \left( {x}^{k} \right) \right) $$</p>
<p>Where \( {\alpha}_{k} \) is the step size.</p>
<p>Yet it won't converge to CVX Solution for this problem.</p>RoyiMon, 02 Jan 2017 05:59:23 -0500http://www.or-exchange.com/questions/14770/solving-l1-regularized-least-squares-over-complex-domainlinear-algebraoptimizationleast-squaresconvex-optimizationWhich courses are needed for a PhD in Optimizationhttp://www.or-exchange.com/questions/14281/which-courses-are-needed-for-a-phd-in-optimization<p>Hi, </p>
<p>I have completed my bachelor with major in statistics. I have taken a course on optimization too and found it very interesting. After my masters, I am planning to do PhD with a focus on optimization algorithm in survey statistics (sampling allocation).
Could you please suggest me some courses in masters which would be helpful for me?
Thanks.</p>FarexThu, 13 Oct 2016 10:43:04 -0400http://www.or-exchange.com/questions/14281/which-courses-are-needed-for-a-phd-in-optimizationstatisticsoptimizationphdinteger linear if then elsehttp://www.or-exchange.com/questions/14135/integer-linear-if-then-else<p>Hello,
I wish to linearize the following constrain:</p>
<pre><code>if(a>0) then b = 1 else b = 0
</code></pre>
<p>a (integer) is in {1..15} and b is binary</p>
<p>thank u</p>BastaNMon, 22 Aug 2016 04:25:39 -0400http://www.or-exchange.com/questions/14135/integer-linear-if-then-elselinear-programmingoptimizationminimum optimal values for variables while objective is maximizedhttp://www.or-exchange.com/questions/14079/minimum-optimal-values-for-variables-while-objective-is-maximized<p>Hello,
My solver gives the variables to be optimized the minimum values to reach the objective while my objective function is a maximum (briefly the problem checks for each vehicles the location containing the maximum acquaintances and chose it then compares the chosen location with the real one in the database, where the strength of the social tie varies with time t. the variables controlling this variation are the ones to be optimised )</p>
<p>the relation variable r is calculated as followed where fr,fa,co are the ones to be optimized. friends,family and coworker are read in and the are values in [0,1]</p>
<pre><code>r(v,e,t)=sum [u|v<>u ,fr(t)*friends(v,u) + fa(t)*family(v,u) + co(t)*coworker(v,u))] ;
</code></pre>
<p>i am using the following set of constrains to manage the maximum where m is the maximum and z3 is a binary where r in[0,100]:</p>
<pre><code>m(v,t) <= r(v,e,t)+100*(1-z3(v,e,t))
m(v,t) >= r(v,e,t)
sum(e ,z3(v,e,t))>=1
</code></pre>
<p>i am using the following constrains to manage if(r=m)c1=1 else c1 =0, where z1,z2 are binaries r in[0,100] and m is the maximum.</p>
<pre><code>m(v,t)-r(v,e,t)<=-0.0001*z1(v,e,t)+100*z2(v,e,t)
m(v,t)-r(v,e,t)>=0.0001*z2(v,e,t)
c1(v,e,t)+z1(v,e,t)+z2(v,e,t)=1
</code></pre>
<p>to manage that if(m=0)c2=0 (with this i mean if r = m c should be 1 however if m =r=0, c should be zero)</p>
<pre><code>m(v,t)<=100*c2(v,e,t)
0.0001*c2(v,e,t)<=m(v,t)
</code></pre>
<p>to manage the conjunction of c1 and c 2</p>
<pre><code>c(v,e,t)<=c1(v,e,t)
c(v,e,t)<=c2(v,e,t)
c(v,e,t)>=c2(v,e,t)+c1(v,e,t)-1
</code></pre>
<p>to manage that i have only one chosen location c per vehicle v i added (knowing that more than one r(v,e,t)can have a value equals to the maximum, removing this constraint did not improve anything):</p>
<pre><code>sum( e , c(v,e,t) ) <=1
</code></pre>
<p>my objective function is to maximize the following (the chosen edges e matching the ones in the database):</p>
<pre><code>sum[(v,e,t) | e=Destination(v,t),c(v,e,t)]
</code></pre>
<p>the variable to optimize are in the calculation of r(v,e,t)values.</p>
<p>many thanks</p>nardinebastaMon, 01 Aug 2016 08:48:38 -0400http://www.or-exchange.com/questions/14079/minimum-optimal-values-for-variables-while-objective-is-maximizedlinear-programmingoptimizationmathematical-optimizationLinear Optimization with piecewise functionhttp://www.or-exchange.com/questions/13997/linear-optimization-with-piecewise-function<p>Hi, i'm a bit in struggle with the optimization below and I'd be grateful for any help or hint. The problem deals with the "relaxation" of the non-negativity constraint, i.e. my decision variables x can be negative. The cost function c_i(x) shall stay positive. Assume that x is bounded in between a lower and upper bound.</p>
<p>Let</p>
<ul>
<li>x - vector of decision variables</li>
<li>c_i(x) - cost function for each x</li>
</ul>
<p>So the problem needs to be minimized:
min z(x) = sum(c(x)) <br></p>
<p>s.t.<br> L <= x <= U</p>
<p>where c(x) = <br>
n * |x| if x < 0 <br>
m * x if x >= 0</p>
<p>n, m are constant.</p>
<p>Do you know any to convert this function (e.g. by using binary variables?) such that I am able to solve this problem by a linear solver?</p>
<p>Thank you in advance.</p>ThomasWed, 13 Jul 2016 05:00:12 -0400http://www.or-exchange.com/questions/13997/linear-optimization-with-piecewise-functionoptimizationprogramminglinearmixed-integer-programmingShortest Path With Limitations on Node Visitationhttp://www.or-exchange.com/questions/13961/shortest-path-with-limitations-on-node-visitation<p>Hello,</p>
<p>I have a variant on the classic 'shortest path' problem and I don't know how to approach it. My graph topology is as such:</p>
<p>There is one source and one sink.</p>
<p>Other nodes are designated by a letter and subscript integer (e.g., A1,B1,C1,A2,B2,C2,....A30,B30,C30). There is one node per possible letter/integer combination.</p>
<p>There is one zero-cost directed edge from the source to each of A1, B1, C1. There is one zero-cost directed edge from each of the nodes with the largest integer to the sink (e.g., when the integers go up to 30, there is one zero-cost directed edge from A30 to the 'Final Destination Node', and an identical edge from B30 and from C30).</p>
<p>From each node there is a directed, weighted edge to one other node of each of the other letters with a larger integer.</p>
<p>For example, there may be a directed weighted edge from A1 to B3 and from A1 to C10; however you won't see edges from A1 to both B3 and B5 because the destinations are both 'B' edges.<br>
</p>
<p>There are no edges that move from one node with a letter, to another node with a letter (e.g., no B3 to B10) and no edges that move from a node with a higher integer to one with a lower integer (e.g., no B30 to C10).</p>
<p>I know that I can use Djikstra's algorithm to find a singular shortest path from origin to destination, but my goal is somewhat different. I want to:</p>
<p>1) Find a single shortest path from source to sink that visits each of the 'letters' once and only once. Any group of integers will work as long as I visit all the letters. Eg. visiting the node set A1, B22, and C27 between the source and sink is acceptable; visiting A10, A15, B22 is not.
2) Find two paths that, combined, visit each of the letters once and only once. If the 'letter set' was ABCDEF, one route could visit ABD and the other CEF; but we couldn't have one route visit ABCD and the other visit DEF, because D would overlap. The goal is to identify two paths that find the minimal longer route - I don't care about the total time as much as about this minimax.
3) Same question as #2 but with 3 paths, 4 paths, etc.</p>
<p>I assume I could make a very complicated integer program but didn't know if there were shortest-path algorithms already available to solve this. Bonus points if it's ready-made in an R package.</p>
<p>Thanks in advance for any help you can provide.</p>
<p>Ralph</p>kmwestTue, 21 Jun 2016 16:05:15 -0400http://www.or-exchange.com/questions/13961/shortest-path-with-limitations-on-node-visitationoptimizationshortestResearch in Algorithmic Optimization: Need some suggestionshttp://www.or-exchange.com/questions/13955/research-in-algorithmic-optimization-need-some-suggestions<p>Hello Everyone,</p>
<p>I just need some suggestion for starting my PhD thesis in algorithmic optimization from August, 2016. I have completed my Bachelors in Statistics and Masters in Operations Research.</p>
<p>My PhD work would be concentrated on the multi criteria decision making in data analysis or in survey statistics. Actually, my mathematical background is not that much strong. Can you please suggest me some courses which would be required for carrying out PhD work in algorithmic optimization?</p>
<p>It would be more appreciable if you could suggest me some books or research papers.</p>
<p>Thanks for your valuable time.</p>SaemSun, 19 Jun 2016 15:14:48 -0400http://www.or-exchange.com/questions/13955/research-in-algorithmic-optimization-need-some-suggestionsoptimizationmathematical-optimizationlinearization 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>nardinebastaSun, 08 May 2016 05:46:12 -0400http://www.or-exchange.com/questions/13718/linearization-of-the-sum-functionlinearizationlinear-programmingaimmsoptimizationUse Dynamic Programming to maximise a nonlinear objective functionhttp://www.or-exchange.com/questions/13618/use-dynamic-programming-to-maximise-a-nonlinear-objective-function<p>Using dynamic programming, </p>
<blockquote>
<p>Maximise $$z = x_1(1-x_2)x_3$$</p>
<p>subject to</p>
<p>$$x_1 - x_2 + x_3 \le 1$$</p>
<p>$$x_1, x_2, x_3 \ge 0$$</p>
</blockquote>
<p>Here's the outline of my solution 1. How is it?</p>
<p>Let \(y_2=1-x_2\).</p>
<p>Also let's change the other x's to y's.</p>
<p>Then we have</p>
<blockquote>
<p>Maximise $$z = y_1y_2y_3$$</p>
<p>subject to</p>
<p>$$y_1 + y_2 + y_3 \le 2$$</p>
<p>$$y_1, \color{red}{y_2,} y_3 \ge 0$$</p>
<p>$$y_2 \le 1$$</p>
</blockquote>
<p>We can deduce that \(y_2 \ge 0\), but do we need to? In this case I guess not, but in general?</p>
<p>If we solve this problem by dynamic programming, then we get the same answer as in Wolfram.</p>
<hr>
<p>Here's the outline of my solution 2. How is it?</p>
<p>Stage 3: Max \(x_3\)</p>
<p>$$f_3^{op}(s_3) = \max_{0 \le x_3 \le s_3} {x_3}$$</p>
<p>Stage 2: Min \(x_2\)</p>
<p>$$f_2^{op}(s_2) = \min_{0 \le x_2 \le s_2} {(1-x_2) f_3^{op}(s_2+x_2)}$$</p>
<p>Stage 1: Max \(x_1\)</p>
<p>$$f_1^{op}(s_1) = \max_{0 \le x_1 \le s_1} {(x_1) f_2^{op}(s_1 - x_1)}$$</p>
<p>where $$s_1 = 1$$</p>
<p>After we solve $$x_1^{op} = 2/3$$</p>
<p>we get</p>
<p>$$x_2^{op} = s_2 = s_1 - x_1 = 1 - 2/3 = 1/3$$</p>
<p>$$x_3^{op} = s_2 + x_2 = 1/3 + 1/3 = 2/3$$</p>
<hr>
<ol>
<li>
<p>I think we have to minimise \(x_2\) and maximise everything else because the \(x_2\) part we want to maximise is \(1-x_2\), which would be done by minimising \(x_2\). Is that right?</p>
</li>
<li>
<p>Why should we still have \(x_2 \color{red}{\le s_2}\)? My solution (whose answer agrees with Wolfram) seems to rely on \(x_2^{*} = s_2\). I was thinking that the negative coefficient of \(x_2\) in the constraint removes that. If not, what is the role of the negative coefficient of \(x_2\) (in the constraint, not objective function)? Just the \(s_2 \color{red}{+} x_2\)?</p>
</li>
</ol>BCLCFri, 22 Apr 2016 06:38:43 -0400http://www.or-exchange.com/questions/13618/use-dynamic-programming-to-maximise-a-nonlinear-objective-functiondynamic-programmingoptimizationnonlinear-optimizationinteger linear if then else constrainthttp://www.or-exchange.com/questions/13611/integer-linear-if-then-else-constraint<p>how to linearize:</p>
<pre><code>if (m > 0)
then c = 1
else c = 0
</code></pre>
<p>thank you</p>
<p>c is binary<br>
m is in [0,inf)</p>nardinebastaThu, 21 Apr 2016 12:56:11 -0400http://www.or-exchange.com/questions/13611/integer-linear-if-then-else-constraintlinear-programmingoptimizationWhat values make the solutions in the optimal? infeasible? degenerate? etchttp://www.or-exchange.com/questions/13588/what-values-make-the-solutions-in-the-optimal-infeasible-degenerate-etc<p><a href="http://i.stack.imgur.com/Bk4TZ.png"><img alt="enter image description here" src="http://i.stack.imgur.com/Bk4TZ.png"></a></p>
<hr>
<p>Note that \(c_i\)'s in the \(z_j-c_j\) row are not coefficients of the \(x_i\)'s. We can use instead \(r_1, r_2, r_3\) (r for row).</p>
<hr>
<p>I'm assuming </p>
<ol>
<li>
<p>there's a non-negativity constraint.</p>
</li>
<li>
<p>we need to state <strong>necessary</strong> conditions from the word 'required', but please give sufficient if you can.</p>
</li>
</ol>
<hr>
<p>What I tried:</p>
<p>The only amount we can deduce without further conditions is \(r_3 = 0\) because \(x_3\) is a basic variable</p>
<p><strong>Letter b</strong></p>
<p>Based on <a href="http://math.stackexchange.com/questions/1676425/use-graphical-analysis-to-solve-a-parameterised-lp-problem">Case 1 here</a>, I think: \(b < 0, x_6\)</p>
<p>Is this really the only way we have an infeasible solution? I know it is a sufficient condition but am not sure if it is a necessary condition. Infeasible means doesn't satisfy the constraints. What if solution satisfies non-negativity constraint but doesn't satisfy other constraints?</p>
<p><strong>Letter a</strong></p>
<p>Case 1: \(r_1 = 0, a_3 > 0, r_2 \ge 0, b \ge 0\)*</p>
<p>Case 2: \(r_1 \ge 0, a_1 \in \mathbb R, r_2 = 0, b \ge 0\)</p>
<p>*Do we need \(a_3 > 0\) instead of \(a_3 \in \mathbb R\)? If so, why? Avoiding unboundedness because unboundedness implies no optimal solutions?</p>
<p><strong>Letter c</strong></p>
<p>\(b = 0, x_6\)</p>
<p><strong>Letter d</strong></p>
<p>\(x_1\) is not in basis. If \(r_1 < 0\) and \(a_3 \le 0\), the LP is unbounded. If \(b \ge 0\), the solution is feasible.</p>
<p><strong>Letter e</strong></p>
<p>\(r_2 < \min{0, r_1, r_3}\)</p>
<p>If \(a_1 > 0\), we need \(b < \min{ 15/2, 3/a_1 }\)</p>
<p>If \(a_1 \le 0\), we need \(b < 15/2\)</p>
<p>If \(b \ge 0\), the solution is feasible.</p>
<hr>
<p>Anywhere I went wrong?</p>
<hr>
<p>From Chapter 2 <a href="https://onedrive.live.com/?authkey=%21ABIU1apSS8r3CbA&id=5EA51B764D593198%212679&cid=5EA51B764D593198">here</a>.</p>BCLCTue, 19 Apr 2016 14:06:56 -0400http://www.or-exchange.com/questions/13588/what-values-make-the-solutions-in-the-optimal-infeasible-degenerate-etcfeasibilitylinear-programmingoptimizationboundsdegeneracyApproximation MIP by LP with exponential many constraintshttp://www.or-exchange.com/questions/13408/approximation-mip-by-lp-with-exponential-many-constraints<p>Is it possible to write for a given MIP a LP with exponential many constraints, which are aquivalent?
If yes, why is it not possible with the Ellipsoid method to solve it in poly time?</p>opti100Fri, 26 Feb 2016 18:34:57 -0500http://www.or-exchange.com/questions/13408/approximation-mip-by-lp-with-exponential-many-constraintsoptimizationAlternative Methods for Solving LPshttp://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lps<p>Next to the most known methods:</p>
<p>Ellipsoid Method, which has theoretical the best property but has big numerical problems.
Barrier Method, which also runs in poly-time, but lacks warm-start for MIPS.
Primal/Dual Simplex Method, which is theoretical worse, but in practice good. </p>
<p>Are there ideas for different methods for solving LPs/literature for other methods?
What are their weak points?</p>opti100Fri, 19 Feb 2016 19:08:12 -0500http://www.or-exchange.com/questions/13395/alternative-methods-for-solving-lpsoptimizationScheduling Problemhttp://www.or-exchange.com/questions/13346/scheduling-problem<p>Hey everyone I really hope I can get your help. I'm trying to solva a scheduling problem having some time and resource constraints. I work with time instances that are very very long and the optimizer is taking too long. I'm trying to switch on events, that is calculate the objective function when a new task starts or finishes. Therefore i inserted the following constraints:</p>
<pre><code>for (int ist =0; ist < finalIstant; ist++)
{
IloIntExprArray futureEvents(env); //eventi profilo
IloIntExpr cond;
for (int m = 0; m< jobs.getSize(); m++)
{
condEq= ist==jobs[m];
}
for (int f = 0; f< jobs.getSize(); f++)
{
IloIntExpr condGreater=jobs[f] > ist;
futureEvent.add(condGreater);
}
nextEvent=IloMin(futureEvents);
IloIntExpr event=nextEvent-ist;
IloInt tempOot = itThis->optimal;
IloIntExpr diff = tempOpt - IloSum(risIst);
IloIntExpr diffQuad = diff * diff;
expression.add(condEq*diffQuad*event);
}
</code></pre>aled98Thu, 11 Feb 2016 12:26:59 -0500http://www.or-exchange.com/questions/13346/scheduling-problemobjectiveschedulingcpoptimizationMultiobjective optimization with matlabhttp://www.or-exchange.com/questions/13200/multiobjective-optimization-with-matlab<p>I have pretty simple linear optimization problem with two objective functions</p>
<p>\[\begin{align} \text{maximize}\, (f_1 &= 4x_1+5 x_2\,,\,f_2 = 1x_1 ) \\ \text{subject to}& \\ 1x_1 + 1x_2 &\leq 200 \\ 1.25x_1 + 0.75x_2 &\leq 200 \\ 1x_2 &\leq 150 \\ x_1,x_2 &\geq 0 \end{align}\]</p>
<p>I'm trying to find optimal points to this problem with goal method (matlab) and with normalized objective function, where \(f^*(x) = (950,160)\) are the optimal solutions (Utopia point?) to my objective functions.</p>
<p>\[f(x)=\sum_{i=1}^2 (f_i^{*}(x)-f_i (x))/f_i^{*}(x)\]</p>
<p>I don't know how to translate this problem into matlab. Any help?</p>ORnoobSat, 09 Jan 2016 09:19:29 -0500http://www.or-exchange.com/questions/13200/multiobjective-optimization-with-matlaboptimizationmatlabmultiobjectiveMaximin Optimization Solverhttp://www.or-exchange.com/questions/13181/maximin-optimization-solver<p>Hi, all. I have a max-min program with linear objective and linear constraints for which Matlab global optimization solver is inaccurate and too slow. Can someone please recommend other decent solvers?</p>NNINGMon, 04 Jan 2016 18:17:01 -0500http://www.or-exchange.com/questions/13181/maximin-optimization-solverminimaxoptimizationmachine-learningHow to dualizehttp://www.or-exchange.com/questions/13005/how-to-dualize<p>We have a minimization problem, which includes the following two constraints, where M constant, and and x,y,z variables:
M(1- z) >= x-y
-M(1-z) <= x-y</p>
<p>I want to dualize these two constraints using lagrangean multipliers u >=0 and v>=0.
So I add in the objective function the following:
u * [x-y-M(1-z)] + v [ y-x-M(1-z)].
Or should I do u * [ M(1-z) -(x-y) ] + v [M(1-z) -(y-x)] ?</p>
<p>Thank you</p>spyimpTue, 10 Nov 2015 06:23:10 -0500http://www.or-exchange.com/questions/13005/how-to-dualizeoptimizationstochastic-optimizationdualityconvex-optimizationlagrangian-relaxationCPLEX: Strange behaviour with big M constraintshttp://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraints<p>Dear,
Would you please help me answer some questions regard to using big M constraints in cplex solver?
I have an optimization problem containing big M constraints, such as, a - b - M*c >= -M. The purpose of the constraint is c = 1 -> a>=b; I set M as MAX_INT.
I observed that with default integrality tolerance value (1e-5), cplex solver produces solution but violates the constraint above, for example, c=0.99... and a < b (instead of a >= b).
Then I reduce the integrality tolerance (tol) value from 1e-5 to 1e-15, I observed that with tol= 1e-7 cplex produces solution that satisfies all constraints, but with tol=1e-10 cplex produces solution that does not satisfies the constraint above. I do not understand the behaviour. Can you please help me explain that ?
Additionally, with tol= 1e-7 and tol = 1e-14 cplex produces solutions that satisfy all constraints, but the optimal values that cplex produces in these two cases are different. I though there is only one optimal solution, but here cplex produces different optimal points with different integrality tolerance values. Would you please help me explain that ?</p>
<p>Thank you so much.</p>NeroSun, 01 Nov 2015 18:07:16 -0500http://www.or-exchange.com/questions/12988/cplex-strange-behaviour-with-big-m-constraintsbigoptimizationmip