Hello! I need to put in relations couples of variables. This seems to make my model not-linear. My model manages two groups of variables (all of them boolean, 0 or 1). Part of objective depends on couples of variables coming from the two different groups are both equal to 1. So I check this multiply couples of variables each other and for a constant. The result is 0 (zero) or the constant. But this part of model makes it not-linear. Generally speaking how can I keep model linear in this case? thanks

asked 17 Feb, 09:23

cla68's gravatar image

accept rate: 0%

Imagine you have the boolean variables x[i] and y[j], then you can have another set of boolean variables z[i][j] where z[i][j] takes value 1 iff both x[i] and y[j] have value 1: \( 2 z_{ij} \geq x_i + y_j \), \( \sum_j x_{ij} \leq x_i \), \( \sum_i x_{ij} \leq y_j \).


answered 19 Feb, 12:49

Alberto%20Santini's gravatar image

Alberto Santini
accept rate: 0%

Thanks Alberto. I suppose you are Italian as I am. Your suggestion is ok, but it does not solve the main problem. That's because I did not explain it properly. Basically my problem is similar to classic example of transport optimization, but from/to sources/destinations are not defined because are variables of the problem. The problem has two targets (but together in the same objective as sum): one is optimization of choice sources/destination (based on an economic target, minimize the total cost of products supplied by different suppliers); at the same time part of the objective (minimize total cost) depends on transportation cost, which depends on couples of sources/destination. So, first part of problem is linear, but second part needs to compare the source/destination in order to calculate transportation cost, and that makes the problem not-linear. Maybe I can complete re-formulate problem (at the moment I choose source/destination with binary variables) but I do not find the right way. I cannot exclude there isn't a linear formulation...Thanks in advance for any further suggestion

(19 Feb, 15:06) cla68
Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 17 Feb, 09:23

Seen: 109 times

Last updated: 02 Mar, 15:06

Related questions

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