0
$\begingroup$

Let's say we have linear programming problem

with x1 and x2 variables.

Maximize x1 + x2

where (for example)

0.3x1 + 0.7x2 <= 2

0.2x1 + 0.3x2 <= 3

How can be added one more condition, so linear programming solve should take into account, that

x1 should come a multiple of 20 (or any other number) ?

something towards:

(1/20)*x1 + 0 <= something towards 20

So, for this example x1 variable,

right answer should be 20 or 40 or 60, ...

$\endgroup$
5
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$ Commented Jan 15, 2024 at 15:09
  • 1
    $\begingroup$ I mean, how to limit possible solved variable value, so it should be a multiple of any specific number: for this example, X1 valid values are only 20, or 40, or 60, otherwise, solve is not finished $\endgroup$ Commented Jan 15, 2024 at 15:13
  • $\begingroup$ @KamilIslamov Here is a possible constraint for x_1: $$\frac{x_1}{20} \in \mathbb N^+$$ So $x_1$ can take any value of $\{20,40,60,...\}$ $\endgroup$ Commented Jan 15, 2024 at 16:43
  • $\begingroup$ @KamilIslamov Pay attention on the constraints. Both constraints do not allow that $x_1$ is greater or equal to $20$. With your mentioned condition the program is not feasible. $\endgroup$ Commented Jan 15, 2024 at 16:51
  • $\begingroup$ @callculus42. thanks for suggestion, would you please share, how can this condition be written down to A, b, c matrix of simplex method? for this example: A = [[0.3 0.7],[0.2 0.3]] b =[2, 3] c= [1, 1] If to speak about ∈N+, what should it look like for A, b, c? $\endgroup$ Commented Jan 15, 2024 at 18:41

1 Answer 1

Reset to default
1
$\begingroup$

It sounds like you want to enforce the constraint that there exists an integer $k$ such that $x_1 = k \cdot 20$. Once you enforce this type of constraint, you no longer have a linear programming problem. In particular, the set of decision variables is no longer convex, because you're only allowing $x_1$ "on a grid" so to speak.

Once you add in constraints like this, your problem becomes one of "integer linear programming".

$\endgroup$
9
  • $\begingroup$ thanks for idea, for better interpreting, would you please share, how this condition could look like? is it additional condition, or constant in target, or constant for right side? $\endgroup$ Commented Jan 15, 2024 at 16:03
  • $\begingroup$ This condition cannot be written as a system of linear equalities / inequalities. Instead, enforcing integrality is a new type of constraint. See this wikipedia article for more details link $\endgroup$ Commented Jan 15, 2024 at 18:46
  • 1
    $\begingroup$ @KamilIslamov You would introduce $k$ as an integer variable and $x_1=20k$ as a new linear constraint. $\endgroup$ Commented Jan 15, 2024 at 19:06
  • $\begingroup$ @RobPratt , thanks for suggestion, would you please share, how this integer variable could be implemented with A, b c paradigm of simplex method of LP? where A = is coefficient matrix, "b" is right sides array, and "c" is target condition coefficients array? (A = [[0.3 0.7],[0.2 0.3]] b =[2, 3] c= [1, 1]) $\endgroup$ Commented Jan 16, 2024 at 3:34
  • $\begingroup$ @KamilIslamov the main point here is that this is no longer an LP. You won't be able to write the feasible region using a system of linear inequalities. So, it generally doesn't make sense to use the simplex method as such, though there are many algorithms for integer linear programming, see the wikipedia link I sent above $\endgroup$ Commented Jan 16, 2024 at 22:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.