f******d
发帖数: 3 | 1 给定一个max线性规划，要求引入一个额外的(满足一些简单性质的)constraint，使得
在加入这个新的constraint之后，这个线性规划的最优解最小。请问有不有类似的研究
或者结果，谢了先... |
d*****1
发帖数: 1837 | 2 max c'x
st Ax <= b
get optima f*, with solution x*
you want to add some constraints Dx <= d such that
f*, x* will be optima and solution of the following problem
min c'x
st Ax <= b
Dx <= d
a simple constraint
c'x >= f*
can do the job |
f******d
发帖数: 3 | 3 Thanks for your reply.
Sorry, I didn't make myself clear. Formally, the problem is like this.
z = max c'x
st. Ax <= b
I want to find a vector d such that the following problem
z = max c'x
st. Ax <= b
dx <= 0
get the minimum over all possible d. I.e. select a d such that z decreases
as much as possible. Moreover, each element d_i of d is restricted to be 0
or some given constant k_i. |
d*****1
发帖数: 1837 | 4 same idea
solve min z = c'x, st Ax <= b
add constraint c'x <= z* |
f******d
发帖数: 3 | 5 Thanks for you idea. It provides more insight to the problem although it
doesn't fully solve the problem.
The point is that c' may not satisfy the condition of "each element of c' is
restricted to be 0 or some given constant k_i". In other words, c' is not a
valid constraint coefficient. |
d*****1
发帖数: 1837 | 6 You can solve it as a bilevel problem
\min z
st k = d * y
y \in (0, 1)
z = \max_k c'x
st. Ax <= b
kx <= 0
Not sure how much effort it will be |
