Newest questions tagged binary-variable - Operations Research Stack Exchange most recent 30 from or.stackexchange.com 2019-11-22T06:14:37Z https://or.stackexchange.com/feeds/tag?tagnames=binary-variable&sort=newest https://creativecommons.org/licenses/by-sa/4.0/rdf https://or.stackexchange.com/q/2968 7 Help with formulating an implication Djames https://or.stackexchange.com/users/609 2019-11-01T11:58:12Z 2019-11-01T17:01:51Z <p>I have a binary variable <span class="math-container">$y$</span> and a set of binary variables <span class="math-container">$x_i$</span>, where <span class="math-container">$i\in I$</span>. My problem requires that <span class="math-container">$$\sum\limits_{i\in I}x_i = b.$$</span> What I want to formulate is the following implication: if <span class="math-container">$\sum\limits_{i\in \tilde{I}} x_i \leq b-1$</span> then <span class="math-container">$y=1$</span> where <span class="math-container">$\tilde{I}\subseteq I$</span>, but I can't seem to figure out how. I have been able to find a formulation that says if <span class="math-container">$\sum\limits_{i\in \tilde{I}}x_i=m$</span> then <span class="math-container">$y=0$</span> by the inequality <span class="math-container">$\sum\limits_{i\in \tilde{I}}x_i + y \leq m$</span> but that is not exactly what I want. Any help is greatly appreciated!</p> https://or.stackexchange.com/q/2903 8 How to linearize the multiplication of an integer and a binary integer variable? dipak narayanan https://or.stackexchange.com/users/836 2019-10-24T10:44:57Z 2019-10-24T23:36:15Z <p>I have the following constraints</p> <p><span class="math-container">\begin{align}\sum_{i=1}^{N}{x_it_i}&amp;= M\\\sum_{i=1}^{N}{t_i}&amp;\le S\end{align}</span> where <span class="math-container">$x_i\ge 0$</span> is an integer variable, <span class="math-container">$t_i\in\{0,1\}$</span> is a binary variable and <span class="math-container">$M,S$</span> are known numbers.</p> <p>How can I linearize this?</p> https://or.stackexchange.com/q/2782 5 How to establish constraint between variables with multiple indexes using CPLEX in Python campioni https://or.stackexchange.com/users/2453 2019-10-11T14:30:34Z 2019-10-13T23:51:27Z <p>I am new in CPLEX and I am using docplex in Python to solve an ILP. </p> <p>I would like to translate the following constraint in docplex: </p> <p><span class="math-container">$$\sum_{c}(X_p{_w}_{cj}+X_{p+1}{_{w'}}_{cj+1})\leqslant T_w{_{w'}}_{,jj+1} + 1$$</span></p> <p>Knowing that the binary variables are: </p> <ul> <li><p><span class="math-container">$X_p{_w}_{cj}=1$</span> if an operation <span class="math-container">$p$</span> is done by a machine <span class="math-container">$w$</span> with a configuration <span class="math-container">$c$</span> at process plan position <span class="math-container">$j$</span>, and zero otherwise</p></li> <li><p><span class="math-container">$T_w{_{w'}}_{,jj+1}=1$</span> if there is a change of machine <span class="math-container">$w$</span> between position <span class="math-container">$j$</span> and <span class="math-container">$j+1$</span>, and zero otherwise. </p></li> </ul> <p>I've tried to code a dictionary: </p> <pre class="lang-py prettyprint-override"><code>cnrt_10 = {(w, w1, j-1, j): opt_model.add_constraint(ct=opt_model.sum(X_var[p-1, w, c, j-1] + X_var[p, w1, c, j] for c in set_C) &lt;= 1 + T_var[w, w1, j-1, j], ctname="cnrt10_{0}_{1}_{2}_{3}".format(w, w1, j-1, j)) for p in set_OP for w in set_W for w1 in set_W for j in set_J} </code></pre> <p>And also a list: </p> <pre class="lang-py prettyprint-override"><code>opt_model.add_constraints(opt_model.sum(X_var[p-1, w, c, j-1] + X_var[p, w1, c, j] for c in set_C) &lt;= 1 + T_var[w, w1, j-1, j] for p in set_OP for w in set_W for w1 in set_W for j in set_J) </code></pre> <p>But both are returning an error. </p> <p>I am sorry for my elementary question, but I am a beginner in Python and CPLEX, so I would really appreciate if someone can help me with these problems.</p> <p>Thanks in advance!</p> https://or.stackexchange.com/q/2770 14 Does this $0-1$ integer program have any speciality? worldterminator https://or.stackexchange.com/users/2491 2019-10-09T08:27:36Z 2019-10-10T07:35:13Z <p>Given matrix <span class="math-container">$A \in \{0,1\}^{m \times n}$</span> and vector <span class="math-container">$b \in (\mathbb{Z^+})^m$</span>, where <span class="math-container">$\mathbb{Z^+}$</span> is the set of positive integers,</p> <p><span class="math-container">$$\begin{array}{ll} \text{maximize} &amp; c^\top x\\ \text{subject to} &amp; Ax \leq b\\ &amp; x \geq 0\\ &amp; x \in \{0,1\}^n\end{array}$$</span></p> <p>Notice the biggest difference from normal <span class="math-container">$0-1$</span> integer programming is that <span class="math-container">$A \in \{0,1\}^{m \times n}$</span> and <span class="math-container">$b \in (\mathbb{Z^+})^m$</span>. Is there anything special about such integer programs? Is there an algorithm to solve them in polynomial time?</p> <p>This question also exists at <a href="https://math.stackexchange.com/questions/3383975/does-this-0-1-integer-program-have-any-speciallity">math.stackexchange</a> </p> https://or.stackexchange.com/q/2758 8 Constraint to state the relation between 2 binary variables campioni https://or.stackexchange.com/users/2453 2019-10-08T08:08:31Z 2019-10-08T17:06:51Z <p>I'm trying to deal with a process planning and machine layout allocation simultaneously. </p> <p>I have the following variables: </p> <ul> <li><p><span class="math-container">$X_p{_w}_{cj}=1$</span> if an operation <span class="math-container">$p$</span> is done by a machine <span class="math-container">$w$</span> with a configuration <span class="math-container">$c$</span> at process plan position <span class="math-container">$j$</span>, and zero otherwise</p></li> <li><p><span class="math-container">$T_w{_{w'}}_{,jj+1}=1$</span> if there is a change of machine <span class="math-container">$w$</span> between position <span class="math-container">$j$</span> and <span class="math-container">$j+1$</span>, and zero otherwise. </p></li> <li><p><span class="math-container">$C_w{_{cc'}}_{,jj+1}=1$</span> if for a given machine <span class="math-container">$w$</span> there is a change of configuration between position <span class="math-container">$j$</span> and <span class="math-container">$j+1$</span>, and zero otherwise. </p></li> </ul> <p>Since the variable <span class="math-container">$X_p{_w}_{cj}$</span> gives me the position of each machine and configuration on the process plan, I think I must establish a relation between this variable and <span class="math-container">$T_w{_{w'}}_{,jj+1}$</span> and <span class="math-container">$C_w{_{cc'}}_{,jj+1}$</span>, respectively.</p> <p>In order to do that, I created the following constraint: </p> <p><span class="math-container">$$\sum_{c}(X_p{_w}_{cj}+X_{p+1}{_{w'}}_{cj+1})\leqslant T_w{_{w'}}_{,jj+1} + 1$$</span></p> <p>With this constraint I would like to state that for 2 followed positions on the process plan, the sum of variables <span class="math-container">$X_p{_w}_{cj}$</span> must be equal or less than the variable <span class="math-container">$T_w{_{w'}}_{,jj+1}+1$</span>. In other words, this constraint states if there is a change of machine between <span class="math-container">$j$</span> and <span class="math-container">$j+1$</span>.</p> <p>Similarly, the following constraint states if there is a change of configuration for the same machine between <span class="math-container">$j$</span> and <span class="math-container">$j+1$</span>.</p> <p><span class="math-container">$$X_p{_w}_{cj}+X_{p+1}{_w}_{{c'}j+1}\leqslant C_w{_{cc'}}_{,jj+1} + 1$$</span></p> <p>I would like to know if it is correct or if there is a better way to express these relations. Could someone help me?</p> https://or.stackexchange.com/q/2734 8 Should I factor in time as a parameter or a variable in a scheduling problem with MILP? Dom https://or.stackexchange.com/users/2460 2019-10-04T01:46:40Z 2019-10-08T22:13:58Z <p>I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written. Here is the premise of my problem.</p> <ul> <li><p>There are <strong>320 papers</strong> to be written. (All writers can write these papers and <strong>can all work at the same time</strong>). Each paper takes a different amount of time to complete.</p></li> <li><p>We have <strong>2 types</strong> of workers available to complete this set of papers. </p></li> <li><p>We have <strong>150 writers</strong>, whose responsibility it is to actually write the paper.</p></li> <li><p>We have <strong>25 movers</strong>, whose responsibility it is to take the completed papers and go and grab a new paper for the writers to work on. For the sake of simplicity, I am assuming that the time to take a completed paper and deliver a new one is constant for each move.</p></li> </ul> <p>The goal of this problem will be to minimize the total length of time it takes to write all of these papers with my staff. We are restricted by the following:</p> <ul> <li>How many writers we have to write papers at the same time</li> <li>How many movers are available to move papers at the same time</li> <li>Each mover takes 25 minutes to move a paper for the writer</li> <li>Movers cannot move papers for writers that are within 2 writers of each other at the same time (If writer 3 has completed his paper and a mover begins moving a paper for them, then writers 1,2,4, and 5 will have to wait until the mover for writer 3 has finished their move). This constraint is meant to represent a physical limitation we have at our facility.</li> </ul> <p><strong>My Approach:</strong></p> <p>It has been some time since I've properly done LP so I am rusty(I'm also still a student so my skills were never good to begin with). I have defined the following variables but am not sure if these are good or not. <strong>I don't know whether to consider time <span class="math-container">$t$</span> as a parameter for these variables or as its own variable and this is what I'm mainly struggling with.</strong></p> <p><span class="math-container">$D_p$</span>: The length of time for paper <span class="math-container">$p$</span> to be completed.</p> <p><span class="math-container">$S_{p,w}$</span>: The point in time when writer <span class="math-container">$w$</span> begins writing paper <span class="math-container">$p$</span>.</p> <p><span class="math-container">$X_{p,w}$</span>: Binary variable representing whether or not a paper <span class="math-container">$p$</span> is being written by writer <span class="math-container">$w$</span>.</p> <p><s> <span class="math-container">$M_{m,w}$</span>: Whether or not mover <span class="math-container">$m$</span> moves a paper for writer <span class="math-container">$w$</span> </s></p> <p>Constraints that I have come up with are as follows:</p> <ul> <li><p><span class="math-container">$\sum_{w \in W} X_{p,w} = 1$</span></p></li> <li><p><span class="math-container">$S_{p,w} \ge 0$</span></p></li> </ul> <p>I am struggling with how to wrap my head around how to factor in a timeline as either a variable or some set or whatever. </p> <p><strong>Edit:</strong> I've spent some more time and discovered that this is a common difficulty with this type of problem(yay!). The two routes to be taken are to consider time as either a discrete or a continuous variable. Though the precision would be nice, the data I have at the facility is available per minute so I think treating time as a discrete variable with <em>one-minute</em> intervals is reasonable.</p> <p>I would like to be able to get an output that gives me an optimal schedule for the papers to be written and for the output to tell me which papers are being completed by which writers at what time. I will be as active as I can in the comments if there needs any clarification.</p> <p>Note: I have also posted this question on SO link: <a href="https://stackoverflow.com/questions/58223716/how-to-formulate-scheduling-matrix-problem-with-mixed-integer-linear-programming">https://stackoverflow.com/questions/58223716/how-to-formulate-scheduling-matrix-problem-with-mixed-integer-linear-programming</a></p> <p>I have also posted this on Math.SE link: <a href="https://math.stackexchange.com/questions/3384542/should-i-factor-in-time-as-a-parameter-or-a-variable-in-a-scheduling-problem-wit">https://math.stackexchange.com/questions/3384542/should-i-factor-in-time-as-a-parameter-or-a-variable-in-a-scheduling-problem-wit</a></p> https://or.stackexchange.com/q/2615 7 Excel Solver linear programming - Is it possible to use average of values as a constraint without #DIV/0! errors or sacrificing linearity? Jacob Myer https://or.stackexchange.com/users/2393 2019-09-21T16:50:03Z 2019-09-21T18:14:51Z <p>I'm trying to create an assignment optimization model where the areas are assigned to either the south or north school districts so that the total distance is minimized. Each school must have at least 1500 students, an average income of at least $85,000 and a minority % of at least 10%. </p> <p>The issue I am having is that when I use solver to find a solution by changing cells G4:G13 (H4:H13 is calculated to be the opposite), there seems to be at least one iteration where the denominator of the average income of a school is 0 (in other words, no districts assigned to one school) and of course this causes a dividing-by-0 error. I tried adding a constraint to ensure each school had at least one district in it which did nothing to solve my problem and I also tried suppressing the error with =IFERROR() which only made the model non-linear. </p> <p>I need to use the Simplex LP method in solver for this assignment. Is there a way I can add these "Average" constraints without issue? </p> <p><a href="https://i.stack.imgur.com/bSAzO.png" rel="noreferrer"><img src="https://i.stack.imgur.com/bSAzO.png" alt="enter image description here"></a></p> https://or.stackexchange.com/q/2535 9 Binary variable to count appearances independentvariable https://or.stackexchange.com/users/65 2019-09-12T01:40:00Z 2019-09-12T17:43:16Z <p>Let <span class="math-container">$x \in \mathbb{R}^n$</span> be an optimization variable. Now, at a constraint, I would like to count how many times a value, say <span class="math-container">$2$</span>, appears in <span class="math-container">$x$</span> decision. </p> <p>I think we can have a binary variable <span class="math-container">$y_i$</span> indicating whether <span class="math-container">$x_i =2$</span>. So, <span class="math-container">$x_i - 2 = 0$</span> should imply <span class="math-container">$y_i = 1$</span>. But, anything except <span class="math-container">$0$</span> should imply <span class="math-container">$y_i = 0$</span>. What is the easiest way for this?</p> <p>Note: since we can subtract <span class="math-container">$2$</span> from each element of <span class="math-container">$x$</span>, we are interested in the number of zeros in <span class="math-container">$x-2$</span>. So, 'the number of zeros in a decision vector' constraint will also make it.</p> <p>We may assume <span class="math-container">$x$</span> consists of elements <span class="math-container">$x_i&lt; M$</span> for some constant <span class="math-container">$M$</span></p> https://or.stackexchange.com/q/1369 6 Obtaining the intermediate solutions in AMPL Oguz Toragay https://or.stackexchange.com/users/39 2019-08-24T16:59:24Z 2019-08-24T20:40:35Z <p>I know that for some solvers, for example, the constraint programming solver in Google OR-Tools, it is possible to see all the intermediate solutions that the solver finds while it searches for an optimal solution. (An example is in <a href="https://developers.google.com/optimization/cp/cp_solver#all_solutions" rel="nofollow noreferrer">this link</a>.) I need these step-wise partial solutions to visualize the evolution of the optimization process in a physical example where I have a nonlinear 0-1 integer problem that I programmed in AMPL.</p> <p><em>My questions are:</em> </p> <ul> <li><p>When solving nonlinear 0-1 integer problems, is it logical to consider such intermediate solutions?</p></li> <li><p>Is it possible to obtain the intermediate solutions of solvers using AMPL? Which solvers have such a feature for AMPL?</p></li> </ul> https://or.stackexchange.com/q/1316 11 Representing an indicator function: binary variables and "indicator constraints" Libra https://or.stackexchange.com/users/459 2019-08-17T15:42:32Z 2019-08-17T16:34:08Z <p>I want to represent the indicator function: <span class="math-container">$$\mathbb{1}_{(y=j)}$$</span></p> <p>where <span class="math-container">$y$</span> is a non negative, integer variable.</p> <p>My attempt is as follows: define a binary variable: <span class="math-container">$$z_j =\begin{cases} 1 \qquad\text{if y=j} \\ 0 \qquad\text{otherwise} \end{cases}$$</span></p> <p>the model of the indicator function would be:</p> <p><span class="math-container">$$\sum_{j=0}^{n} z_j = 1$$</span> <span class="math-container">$$\sum_{j=0}^{n} j \cdot z_j = y$$</span></p> <p>where <span class="math-container">$n$</span> is an upper bound for <span class="math-container">$y$</span>.</p> <p>Actually, this can be conveniently modeled in OPL Cplex (for example) using <em><a href="https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/indicator_constr/04_Interactive.html" rel="noreferrer">indicator constraints</a></em> such as follows:</p> <pre><code>forall(j in 0..n){ (y == j) == (z[j] == 1); } </code></pre> <p><strong>QUESTIONS:</strong></p> <ol> <li>is my binary-variables-based formulation attempt correct? Do you know better (performance wise) formulations?</li> <li>in a hypothetical academic journal paper, is the second formulation (based on indicator constraints) acceptable? If yes, how would you formally express it in the paper in a way that is implementation-independent (that is, in a way that does not depend upon how a specific solver models such a constraint)? Or it is better to provide the more general, binary-variables-based formulation?</li> </ol> <p>Thanks a lot.</p> https://or.stackexchange.com/q/924 7 How can I linearize or convexify this binary quadratic optimization problem? dipak narayanan https://or.stackexchange.com/users/836 2019-07-09T00:00:22Z 2019-07-09T20:03:57Z <p>I have an optimization problem as below. I am having a hard time with the last constraint.</p> <p><span class="math-container">$\max \eta$</span></p> <p>subject to</p> <p><span class="math-container">${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$</span></p> <p>here</p> <p><span class="math-container">$\bf{A}$</span> is a Binary Matrix of size <span class="math-container">$N\times N$</span> (given, known)</p> <p><span class="math-container">$\bf{U}$</span> is an optimization variable matrix <span class="math-container">$\bf U$</span> of size <span class="math-container">$N\times M$</span> (Binary matrix)</p> https://or.stackexchange.com/q/828 16 What are some real-world applications of QUBO? user1271772 https://or.stackexchange.com/users/727 2019-06-29T19:02:59Z 2019-07-16T17:37:59Z <p>QUBO (Quadratic Unconstrained Binary Optimization) is the minimization of a quadratic function of binary variables.</p> <p>It has been used for <a href="https://www.cv-foundation.org/openaccess/content_cvpr_2014/html/Ishikawa_Higher-Order_Clique_Reduction_2014_CVPR_paper.html" rel="noreferrer">computer vision</a>, <a href="https://arxiv.org/abs/1103.1345" rel="noreferrer">Ramsay numbers</a>, <a href="https://arxiv.org/abs/1411.6758" rel="noreferrer">factoring numbers</a>, the <a href="https://arxiv.org/abs/1811.11538" rel="noreferrer">integer partitioning problem</a>, the <a href="https://arxiv.org/abs/1811.11538" rel="noreferrer">MaxCut</a> problem, and many other problems.</p> <p>But in the real-world, one would not factor numbers this way, no new Ramsey number has been found by solving a QUBO problem, and it's not the most efficient way to solve the integer partitioning problem.</p> <p>Are there any real-world problems, for which QUBO is the state-of-the-art way to solve the problem?</p> https://or.stackexchange.com/q/488 16 Can we replace a binary variable with a continuous variable using a quadratic equality constraint? prash https://or.stackexchange.com/users/439 2019-06-15T02:17:08Z 2019-08-25T16:54:37Z <p>Is it possible to replace a binary variable <span class="math-container">$x$</span> with a continuous variable that satisfies the quadratic equality constraint <span class="math-container">$x^2 - x=0$</span>?</p> <p>The function <span class="math-container">$f(x) = x^2 -x\$</span> is not a convex function. Can this constraint still be helpful in using binary variables in constrained optimization problems?</p> <p>It will be helpful if you give literature references to problems having binary variables solved using this method.</p>