Questions tagged [feasible-points]

For questions specifically about existence (feasibility), counting feasible points (in a discrete setting), or partitioning the feasible region (e.g. in the context of branch-and-bound methods). Feasible points are those which satisfy all the constraints of a problem, and so can be defined without regard to any optimization criterion.

Filter by
Sorted by
Tagged with
3
votes
2answers
135 views

Find all Combinations of a Matrix

I have a $16\times11$ matrix and want to find all eligible* combinations of this matrix including always entities from all 11 columns. A simple example from a $2\times3$ matrix would be the following:...
10
votes
0answers
71 views

Is there a library of infeasible MINLP problems?

We have a number of test libraries to test solver performance like MINLPLIB, QPLIB, etc., but the problems in all libraries I know are overwhelmingly on the feasible side. Is there a library to test ...
7
votes
1answer
87 views

When using docplex.cp is it possible to get all feasible solutions?

I would like to solve an ILP and get all feasible solutions (even the worst one). How could I do that using docplex.cp? I've seen a similar question in: Using CPLEX "solution pool" to count ...
6
votes
1answer
110 views

How can I solve this problem?

I have $N_{\rm C}=8,$ and $N_{\rm U}=25$ Scenario 1: $$\frac{l_{c,u}}{\sum\limits_{c=1}^{N_{\rm C}}l_{c,u}}\ge 0.1,\quad\forall u,u=1,2,\cdots,N_{\rm U}$$ and $$\sum_{u=1}^{N_{\rm U}}l_{c,u}\le 1,...
8
votes
4answers
1k views

Why is there not a feasible solution for a MIP?

Is there a way to see why a solver (OR-Tools, CPLEX, Gurobi) cannot find a feasible solution when solving a MIP? By that I mean, is there a possibility to show at which constraint and exact indices ...
19
votes
3answers
2k views

Find feasible point in polynomial time in linear programming

Background A while ago my team was implementing an interior point LP solver and we came across the following conundrum: Is there a polynomial-time algorithm to find a feasible starting point in ...
10
votes
1answer
75 views

Computational complexity to compute an IIS

How hard is it to compute an irreducible infeasible subset (IIS) for a linear program? What about an integer program (e.g., removing the integrality constraint on a single variable may be enough to ...
14
votes
3answers
297 views

Using CPLEX “solution pool” to count feasible points

Some problems call for a count of the number of integer "lattice" points contained in a feasible region (rather than for locating the minimum or maximum objective function value in that region). See ...