Suppose there is a set of n linear constraints <mo fence="false" stretchy="false">{ <msubsup>

Addison Trujillo 2022-07-08 Answered
Suppose there is a set of n linear constraints { a i T x + b i 0 } i = 1 n with a i R d , b i R , x R d . How can I find x that maximizes | { i [ n ] a i T x + b i 0 } |? Is this problem solvable or can be approximated within polynomial time?
Some reference materials would also be nice. Thanks!
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Karla Hull
Answered 2022-07-09 Author has 20 answers
The maximum cardinality feasible subsystem problem is NP-hard
You might also search for the equivalent minimum cardinality IIS set cover problem.
You can solve the problem via mixed integer linear programming as follows. Let binary decision variable indicate whether constraint i is satisfied. The problem is to maximize i z i subject to linear (big-M) constraints
a i T x + b i M i ( 1 z i ) for all  i .
Here, Mi is a (small) constant upper bound on the LHS when z i = 0.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-01-18
The ratio of the number of blue sticks to the number of green sticks in a box was 4:1. When David took out some blue and sticks and replaced them with an equal number of green sticks, the ratio of the number of blue sticks to the number of green sticks became 3:1. If there were 185 green sticks in the box now, (a) find the total number of blue and green sticks in the box, (b) find the number of green sticks in the box at first.
asked 2021-11-22
Graph the sets of points whose polar coordinates satisfy the given polar equation.
The given polar equation is written as follows:
θ=2π3,r2
asked 2022-07-23
How do you find the area of the largest isosceles triangle having a perimeter of 18 meters?
asked 2020-12-13
Use Greens
asked 2021-09-12
Which of the following is true?
dydt+y1t=3t+4 is best solved with undetermined coefficients.
dydt=tyyt2 is best solved with separation of variables.
dydt=ty is best solved with integrating factors.
dydt=2ysin(5t) is best solved with separation of variables.
dydt=tyyt2 is best solved with undetermined coefficients.
asked 2021-11-15
Determine whether the function is continuous at the given point. Show your solution.
k(x)=x2x3+1 at x=1"
asked 2021-11-19
Graph the sets of points whose polar coordinates satisfy the given polar equation.
The given polar equation is written as follows:
π4θπ4,1r1