I want to reformulate abs(x1+x2+x3) = 1 to a linear constraint.

How do you do that?

Thank you

Edit 1:

The general problem is: i have binary variables x_1,...,x_k and only one of them is 1. so the constraint would be x_1+...+x_k = 1 solving my MILP is very slow. so i read about speeding it up by making a stronger relaxation problem, because the value of the relaxation has for example: (0.2, 0,5, 0.7, 0.1)

So it is very far away from the MILP solution. so i took your approach and added:

x_1+x_2+x_3 = -1 + 2*z_1
x_1-x_2+x_3 = -1 + 2*z_2

...and removed the binary condition on the x's in hope to get it solved more quickly. However that doesn't work because you have to introduce as many binary variables as you removed.

Does anybody know a way of a stronger formulation of that constraint?

Edit 2:

Ok, I'm sorry the full question:

I have given n-set of m-vectors and want to minimize the maximum of the biggest element of the sum of vectors when you have to pick one vector of each set

My Formulation (minimal example):

min m_peak
  v_1*x_1+v_2*x_2+... <= m_peak_vec (m_peak_vec is m-dimensional vector with elements have value m_peak)
  x_1+x_2+... = 1 
  x_3+x_4+... = 1
  • v_1 is the first vector,
  • m_peak is continuous, and
  • x_i's are binary and decide wether to take that vector v_i or not.

I hope it is clear because i can't write matrices.

I used Gurobi.

Currently the matrix is about 20,000x70,000 and has 120 mio nonzeros (but will increase in future).

Edit 3:

I have more informations:

  • The elements of the given vectors are bounded by +-10e8,
  • the vectors have nonzero entries from k till k+d, so all nonzero entries appear in a row,
  • all vectors in the same set have the same entries but they are translated:
    so v1 has for example entries from 100 to 1000;
    and v2 which is in the same set from 700 to 1600
    and v3 from 1300 to 2200.
    So they all contain the same entries but at different positions.
    so the first vector of each set vary but the following vectors in the set always have the same entries and translated 600 indices forward compared to the previous one.

Edit 4: Finally :)

Suppose you got you n-railroads on each is driving one train.

For each train you have a given a vector in which the current power demand is written while he is driving (depending on the road and is given every 1/10s).

For each train is also given:the minutes he is driving and the earliest and the latest departure time.

You look at an interval [0,T]. Each Train can leave the train station in his departure interval at full minutes.

If two trains driving at the same time the power demand add up. You look at the summation of all current power demand of all trains.

Choose the departure time of all trains so that the max peak is minimized.

My modeling resizes the power demand vector to the full intervall and fills it with 0 when it is not driving.

For every possible departure time it duplicates the vector and moves the nonzeros to the departure time. Constraints makes make sure that only of those "shadow trains" is driving.

Then you use approach from Edit2. However for large instances it is not very fast. Maybe there is a good heuristic. But i didn't find a name for this kind of problem.

Thank you

asked 07 May '14, 16:07

zBirdy's gravatar image

accept rate: 20%

edited 09 May '14, 14:11


From your Edit 3 it seems like you're very close to actually phrasing the problem you're trying to solve. If you can tell us the problem statement, we may be better equipped to maybe even tell you a standard approach, or even a full formulation so you don't have to "reinvent the wheel" so-to-speak.

(08 May '14, 13:31) Paul

the way you state it means that either x1+x2+x3 = 1 or x1+x2+x3 = -1. This cannot be stated as a linear constraint, you need a binary variable z for this, like x1+x2+x3 = -1 + 2z.

(ok, this is a linear constraint, admitted)

edited after you posted a clarification of the question:

:-) nice, it is of great importance to ask the right questions... typically, a sum of binary variables equal to one is a well-behaving structure. What solver do you use, of what size is your model? Is there anything else you would add to your question before we start more guessing?


answered 07 May '14, 16:17

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
accept rate: 16%

edited 07 May '14, 18:41

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: 07 May '14, 16:07

Seen: 2,650 times

Last updated: 09 May '14, 14:11

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