Tag Info

Let's assume that (a) the full polyhedron is not empty (a solution to the inequalities exists) and (b) you have identified the extreme points of the unit simplex that remain extreme points after the new constraint has been added. Any other extreme points will necessarily satisfy the new constraint as an equality ($\mathbf{b}^T\mathbf{x}=c$). Since they are ...
I had the following model lying around: \begin{aligned} \min&\sum_{i,k}\color{darkred}d_{i,k}\\ & \color{darkred}d_{i,k} \ge \sum_c \left(\color{darkblue}p_{i,c}-\color{darkred}\mu_{k,c}\right)^2-\color{darkblue}M(1-\color{darkred}x_{i,k}) \\ & \sum_k\color{darkred}x_{i,k} = 1 && \forall i\\ & \color{darkred}n_k = \... 3 It depends on what you want to achieve exactly. You could, for example, want to minimize the average distance between a point and the "center" of the cluster. This requires that you first define this center. Assuming it is one of the points, then intoduce a binary variable y_j that takes value 1 if and only if point j is the center of one of ... 2 I recommend you to try very powerful utility LRS, http://cgm.cs.mcgill.ca/~avis/C/lrs.html. It is an open source application (a set of applications) to handle polyhedrals. B.t.w. one of LRS applications, called redund "removes redundant inequalities from an H-representation" (from description) - seems that what you need. There are parallel (MPI-... 6 \max(y,z)\le b is equivalent to \begin{align} y&\le b\\ z&\le b \end{align} The \min constraint is similar. 2 you could try constraint programming / scheduling within CPLEX and use noOverlap to model the time matrix. In OPL that gives using CP; execute { cp.param.timelimit=10; } {string} nodes={"O","A","B","C","D","E","T"}; tuple edge { key string o; key string d; int time; } {edge} ... 2 I think your third constraint should be + 1, not - 1, on the right hand side. As stated, it says you enter destination nodes one time fewer than you exit them. You want to enter one time more. Fixing that will make the optimal solution feasible, but it will not make the model correct. There still remains the possibility of a solution that is not a contiguous ... 3 If the set S of nodes to be visited is not too large, you can solve |S| shortest path problems with additional constraints imposing a visit to some nodes. With your example, |S|=|\{A,C \}|=2 so it is not too bad. 1/ Find the shortest path from O to A, while imposing a visit to node C. 2/ Then find the shortest path from O to C, while ... 4 To be clear, you have a set S of nodes of a graph G=(V,A), with S\subseteq V, which must be visited. There is a special node O, which must be the starting point of a tour. A tour visiting the nodes in S starting from O (but not returning to O) at minimum length must be found? If that is the case, I think the easiest way is to compute an all-... 1 Is the following model correct? Consider \delta_i as binary variables, whereas x_i and y_1 are continuous. $$x_1 = a \delta_1 + y_1$$ For the first if statement: \begin{matrix} c - M(1 - \delta_2) \leq x_2 \leq c + M\delta_2\\ d - M(1 - \delta_3) \leq x_3 \leq d + M\delta_3\\ \delta_2 + \delta_3 \geq2\... 5 Introduce four binary variables indicating which region you are in and the function value.\begin{align} \delta_1 &\rightarrow x_2\geq c, ~x_3\geq d, ~x_1 = a\\ \delta_2 &\rightarrow x_2\geq c, ~0\leq x_3 \leq d, ~x_1 = bx_3\\ \delta_3 &\rightarrow x_2\leq c, ~x_1 = 0\\ \delta_4 &\rightarrow x_3\leq 0, ~x_1 = 0 \end{align} $$You are in ... 3 https://en.m.wikipedia.org/wiki/Diophantine_equation any milp solver can handle it, but maybe something like mathematica/mable has special algortihms or one can use the algorithm described by the wiki entry 4a) https://en.m.wikipedia.org/wiki/Lattice_problem 4b) is i think polytime, either the problem is unbounded, infeasible or all solutions are optimal. 5 Shameless plug: I recently gave a webinar on diagnosing infeasibility. Here's what your example looks like in SAS: proc optmodel; var A >= 0; var B >= 0; max z = 20*A + 30*B; con c1: A <= 60; con c2: B <= 50; con c3: A+2*B >= 220; solve with lp / iis=true; expand / iis; quit; The resulting IIS contains all three ... 1 {0,1}-ILP can be rewritten as Pseudo-Boolean programming or MAX-Sat. It might be worth to explore alternative solving technologies for your problem. 5 I actually have quite a few points. As usual, things are not as clear cut. I use advanced bases for LPs very often and they are surprisingly effective and tolerant of quite a few changes in the model. For large problems, often a good strategy is to use the barrier method for the first problem (solved from scratch) and the simplex for subsequent related ... 1 Warm starting is used predominantly when solving problems that are only slightly different, and typically when only some coefficients have changed. The idea is that many of the feasible polyhedrons' vertices are shared between the two problems, therefore starting at a vertex that was good at a previous problem will save us pivot operations. If the problems ... 3 For sake of completeness: An alternative to using an additional binary variable and a big M would be to use an SOS constraint. An SOS constraint specifies a set of variables, at most one of which may be non-zero. 5 Your constraint matrix is changing with each new problem, so it might not be easy to warm-start ... and it might not be worthwhile, even if you could. One nice thing (among several) about transportation problems is that the origin is feasible, meaning the simplex method has an obvious starting basis. Warm-starting would require you to massage the previous ... 4 There are certainly different ways of achieving what you want. Here is how I would proceed: Start by predefining the set of all possible schedules which satisfy your constraints 2,3,4,6. Although there are many, I believe that with your constraints, it may be not too difficult to derive them somewhat automatically. Here is a subset of them in the table ... 4 Suppose we know an upper bound M for y such that |y| \leq M, we can linearize this constraint as follows. First, we introduce a new variable h \in \mathbb{R} with h = b y. Then we need to model that h equals y if b = 1 and equals 0 if b = 0. For this purpose we add the following linear constraints:$$ \begin{align} h &\leq b M \tag{1} ...