# Tag Info

19

It is not true that the Two-Phase methods requires Simplex iterations, it is just the common way to do it. Let's assume we have a linear program with $n$ variables and $m$ constraints. Step 1) Convert this LP into standard form by splitting all unbounded variables into two $\geq 0$ variables, making sure $b$ is non-negative (by multiplying the rows that ...

17

LP is solvable in polynomial time. The polynomial depends not only on problem size, but also the size of numbers of the input matrix. The standard proof is using the ellipsoid method. Of course, the proof uses exact arithmetic, as any complexity proof would. That method isn't practical though. It is unknown if LP is strongly polynomial. In practice you can ...

14

Point 2 of "What we know" is incorrect: the ellipsoid method does not require a feasible starting point. As I stated in a comment earlier, in Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $\mathbb{R}^n$ belongs to the class of $P$ of problems". In Section 6 of the paper, Khachiyan shows that if you ...

14

@prubin has this neat (possibly slightly dated) series of blog posts, Finding All Solutions (or Not), Finding "All" MIP Optima: The CPLEX Solution Pool Solution Pool: "All" Is Not All, which deals with the hassle of collection all MIP solutions in CPLEX's solution pool. While this doesn't exactly answer your question, it still might provide helpful insights ...

14

The only way (to my knowledge) to get all feasible points for the binary components of a MIP is as follows: Solve the problem. Let $y$ denote the optimal solution Add the following integer cut to your model: $$\sum_{j\in J}y_j - \sum_{t\in T}y_t \leq |J|-1$$ where $J$ is the set of indices where $y_j = 1$, i.e. $J = \{j\mid y_j = ... 13 Yes - such a question can be answered by looking at the irreducible inconsistent subsystem (IIS). From the Gurobi documentation: An IIS is a subset of the constraints and variable bounds with the following properties: the subsystem represented by the IIS is infeasible, and if any of the constraints or bounds of the IIS is removed, the subsystem ... 9 There exist various reasons why a solver could not find the optimal solution. You must always check why a solver terminated. Typical reasons are: optimal solution was found termination criteria was reached, e.g. time limit or a limit on the optimality gap solver proved that problem is infeasible Popular solvers such as cplex/gurobi can report their status ... 8 Finding a minimum-cardinality MIS for a linear program is an NP-hard problem in general, see Edoardo Amaldi, Marc E. Pfetsch, and Leslie E. Trotter Jr. On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Mathematical Programming, 95(3):533–554, 2003. For this reason, commercial solvers such as CPLEX use heuristics to identify small IIS which ... 8 Maybe the unnecessarily large value for$A$is causing numerical trouble. Try instead$A = \max_{i,j} p_{i,j} = 9$. Probably your$=0$in the declaration of$x$should be$\ge 0$. In fact, you generally need to declare$x$to be binary when you include side constraints. 6 Your belief that there will be two different vertices in the set of optimal solutions as long as the feasible polyhedron contains more than a single point is incorrect. In practice, most LPs have unique solutions. As far as an upper bound on the number of optimal vertices, let's assume that you have$m$constraints including sign restrictions on the ... 5 Define quadratic functions$g_1(X)$and$g_2(X)such that \begin{align}\mathcal{E}_1 &= \{ X \mid g_1(X) \le 0\}\\\mathcal{E}_2 &= \{ X \mid g_2(X) \le 0\}\end{align} It follows from the definition that you can find a point in\mathcal{E}_1 \setminus \mathcal{E}_2by solving \begin{align} \min &\quad -g_2(X)\\\text{s.t.} &\quad g_1(X) \... 5 By Farkas lemma, infeasibility of Ax\leq b is equivalent to feasibility of A^Ty = 0, y^Tb < 0, y\geq 0, or more practically useful A^Ty=0, y^Tb \leq -1, y\geq 0. Unfortunately, this will lead to a bilinear model when you parameterize b(z). It is fairly similar to an application I worked on a decade ago Oops! I cannot do it again: Testing for ... 5 Consider maximizing \sum_{i=1}^n x_i subject to x binary and \sum_{i=1}^n i x_i \leq 2 Solve relaxation and it gives x_1 = 1, x_2 = 1/2 with remaining variables 0. Branch on x_2 = 0 and the new solution is x_1 = 1, x_3 = 1/3 with the rest 0. Continue in the same fashion and you will have to go through fixing all variables. Had you minimized \... 5 As an alternative to finding irreducible infeasible subsets (smaller subproblems that are still infeasible) would be to introduce slack variables into your constraints. Then you would replace your original objective with the minimization of these (non-negative) slack variables, penalizing their use. This way, you can also get some insight into which ... 5 Another possibility not mentioned in the other answers is that an optimal solution exists, but the solver is not able to find it, or perhaps confirm its optimality, due to numerical difficulties, which might in turn be due to poor scaling or ill-conditioning of the original problem. Double precision floating point computation can be a cruel mistress. 4 It sounds like what you want is to reduce each vector in your matrix to the relevant entries, and take the Cartesian Product of the column vectors. That is definitely not a problem where linear programming can help, but where you should resort either to traditional combinatorial algorithms, or use a database system that typically has support for generating ... 4 I am answering my own question because it may help other people. I could not find a function in docplex able to get all feasible solutions for a ILP problem. For my best knowledge, docplex only has this kind of function for MIP problems. If you are dealing with MIP, you can check additional information here: https://www.ibm.com/support/knowledgecenter/... 4 I doubt you can do so in polynomial time without any additional condition. Let g be an arbitrary polynomial function, and let f be defined by f(X) = g(X) - C^{T}X over B(0, R), and an appropriate extension so that it's twice differentiable with bounded Hessian over \mathbb{R}^{n}. Then, f(X) + C^{T}X = 0 reduces to g(X) = 0, i.e., your setting ... 3 I think this can be approached using a constraint generation technique (variant of Benders decomposition), although I have no idea if it would efficient. By reordering the rows of A, we can assume thatb(z)=\left[\begin{array}{c} \hat{b}\\ c+e-z \end{array}\right]$$where \hat{b}\in\mathbb{R}^{d-m}, c\in \mathbb{R}^m, e=(1,\dots,1)^\prime \in \mathbb{... 3 I'm not sure there is a way to tweak your heuristic that will guarantee finding a feasible solution (assuming one exists). What you might try is a restart approach combined with a modification of your priority assignment method. Let's say that the modified heuristic assigns each task a "base" priority and then adjusts it when computing priorities ... 3 I don't think I've ever seen a name (let alone any research) for the case of having a collection of known feasible points but no explicit mathematical criteria for feasibility. Before gluing together a bunch of balls, I would first ask whether the nature of the problem tells you anything about the shape of the feasible region. I'm assuming that your ... 3 I assume that the N_C is the number of customers (or something similar) and the N_U is the number of utilities (or again something similar) that can be used to satisfy the customers' demand. As I understood you want to maximize the number of customers for whom more than 2 utilities used in the model to satisfy the demand. You have these components in ... 2 In the end, I reduced the matrix by using HashMaps and ignoring the 0 entities. The code needs around 60' to run for a maximum of 2 different row combinations. I am sure that I can still optimize it, by reducing the iterations when I need at maximum X different row combinations. The following code, is what I have at this moment. import org.apache.poi.ss.... 2 There are LP algorithms which do not require feasible start, and which do not use a Phase I / Phase II method. These algorithms are based on the "Homogeneous Self-Dual Embedding" (HSDE) approach of Ye, Todd, and Mizuno (Mathematics of Operations Research, Vol. 19, No. 1 (Feb., 1994), pp. 53-67). For suitable parameter choices, a path-following HSDE algorithm ... 1 This is a feasibility problem, find X such that$$X^TA_1 X + 2B_1^TX + C_1 \leq 0, X^T A_2 X + 2 B_2^T X + C_2 \gt 0$.In general it will be non-convex (although it is convex if$A_1$is positive semidefinite and$A_2$is negative semidefinite; however, given mention of "ellipsoid", it seems reasonable to presume that$A_1$and$A_2\$ are both positive ...

1

As @Richard said, one of the possible ways to find multiple solutions is using the specific cut. There is a nice topic has been described by Erwin Kalvelagen to find all optimal LP solutions using specific cuts which implementation into GAMS software.

Only top voted, non community-wiki answers of a minimum length are eligible