# Tag Info

7

$\max(y,z)\le b$ is equivalent to \begin{align} y&\le b\\ z&\le b \end{align} The $\min$ constraint is similar.

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 ...

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 ...

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 ...

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

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-...

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-...

3

Define a directed graph $G(V,A)$, where $V=\{0,1,2,\dots,n,n+1\}$, where $0$ and $n+1$ are the starting and ending depot of the vehicles (these depots are typically the same physical depots, but duplicating the depot makes modelling easier). Let $V'=\{1,2,\dots,n\}$ be the set of customers. Then arc set $A$ is defined as $A\subseteq \{0\}\times V'\ \cup V'\... 3 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 ... 3 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 variabley_j$that takes value$1$if and only if point$j$is the center of one of ... 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 ... 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. 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. 2 @JorisKinable uses the MTZ-like constraints to ensure the capacities on the vehicles are respected. Unfortunately, this formulation is known to be (very) weak, and you will probably not be able to solve any large instances. I would suggest to use a network flow based formulation, akin to the formulation you already have to keep track of the time consumption. ... 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 ... 2 Math Formulation + Pyomo model We need to define 3 sets i: 1 to 8 staffs j: 1 to 3 shifts t: 1 to 18 days$X_{i,j,t} \in {0/1} $Binary There must be 3 people on each shift$\forall t,j $then$\sum_i X_{i,j,t} =3$Every individual (i) must work 1 shift per day\$\forall t,i $then$\sum_j X_{i,j,t} \geq 1 $Every individual must not work more than 2 ... 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\...

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 ...

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.

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