4
$\begingroup$

I have a standard linear programming problems I want to solve:

$$ \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. \end{aligned} \right. $$

$F^T$ is a vector that doesn't involve $x$.

The problem with the above minimization is that, I don't know what $n$, the number of variable $x$ is — it is also a part of the minimization. There are a few constraints governing how the vector $x$ should behave. Additionally, there are constraints linking from $x_i$ to $x_{i+1}$. This means that given $x_i$, we know how to form the constraint for $x_{i+1}$. Also, even though we don't know about $n$, but in my problem I can easily construct the corresponding $f_i$ term for each $x_i$.

The constraints are complicated in the sense that it is not easy to express the constraints in the following form:

$$ Ax \leq a $$

and

$$ Bx = b $$

What I can do, at best, is to express $a$ and $b$ involving a first order of $x$ ( i.e., no $x^2$ and above). The matrix $A$ and $B$ are known values with no involvement of $x$.

I understand that linear programming can be used to tackle problems such as this. But the two problems I mention above ( don't know what $n$ is, and cannot separate out the matrix/vector easily) stop me from proceeding.

Is there any other techniques I can use to solve the problem?

  • 0
    May be you can have a look at the simplex method, Dual simplex method,...etc. They are the ones which i learnt when i studied this course, but now i have forgotten!2010-08-28
  • 0
    @Chandru1, as far as I know these methods require you to separate out the known matrix/vector values, which is not possible in my case.2010-08-28
  • 0
    Are the dimensions of $A$, $b$, or $f$ available?2010-08-28
  • 0
    @J. Mangaldan, that's the problem, the dimension of $f$ is tied to $x$, and hence it is also not available.2010-08-28
  • 0
    @J. Mangaldan, the dimension also not available. But $A$ and $b$ can be readily generated if we assume a particular value of $n$, namely the number of $x$ point.2010-08-28
  • 3
    Maybe just post the *actual* problem you have, and let the collective minds of this site wade through the thicket themselves?2010-08-28
  • 0
    @J. Mangaldan, give me sometime to prepare that ( I have great trouble typing mathematical notation!), or maybe I'll just start another question, since they are essentially different things2010-08-28
  • 0
    “What I can do, at best, is to express a and b involving a first order of x ( i.e., no x^2 and above).” This sounds like nothing but *nonlinear* optimization.2010-08-28
  • 0
    @Tsuyoshi Ito, it is still linear, because through clever ( but maybe difficult!) rearranging you can have all the $x$ on the left hand side equation.2010-08-29
  • 0
    My point is that if the “linear” constraint itself varies depending on the value of the variables, it is no longer linear.2010-08-29
  • 0
    @Tsuyoshi, note that $a$ and $b$ are the vectors, so if you do it carefully ( with some clever substitution), you can eliminate $x$ from $a$ and $b$. So your points don't apply2010-08-30
  • 1
    Ok, probably I do not understand your problem.2010-08-30
  • 0
    It has been a while. Could delayed column generation possibly solve your problem?2015-05-29
  • 0
    @WillemHagemann, would you like to explain how "delayed column generation" solves the problem?2015-05-30
  • 0
    I not really sure if delayed column generation is really capable to solve the problem. It was just an idea and I would need more information on the problem. How are the additional constraints on $x_{i+1}$ are generated? Is the number of rows in $A$ and $A_{eq}$ fixed?2015-05-30

1 Answers 1