# Tag Info

10

Let $w_o$ denote the weight of object $o$, and let $c_b$ denote the capacity of bin $b$. You can interpret this as a job shop scheduling problem. The correspondence is that each object is a job, with duration $w_o$, each bin is a machine that is available for only $c_b$ time units, and $z$ is the makespan. It is also a special case of the bottleneck ...

10

You can add an extra binary that equals $1$ if and only if the first constraint is satisfied: \begin{align} x_1+x_2+x_3 &\ge \delta\\ x_1+x_2+x_3 &\le 3\delta\\ x_4+x_5+x_6 &\ge 1 - \delta\\ x_4+x_5+x_6 &\le 3(1 - \delta)\\ \delta &\in \{0,1\} \end{align} If $\delta=1$, the first two constraints become: $$1 \le x_1+x_2+x_3 \le 3$$ And ...

10

Your constraint is equivalent to $$x_i \le f(x_j) \quad \text{for j<i},$$ so it is linear if $f$ is linear.

9

Aggressive cut generation will slow the processing of the root node (and other nodes, if cuts are generated beyond the root), so it's more likely to slow finding a feasible solution than to speed it up. Setting MIP_Strategy_Subalgorithm to 1 tells CPLEX to use primal simplex on node subproblems. To emphasize finding feasible solutions, you want to set ...

9

This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful). My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing: https://projects.coin-or.org/Dip The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition ...

9

Here's another single-solve solution. Replace each original variable $x_n$ with a sum of two variables, $x_n=y_n + z_n$, where $y_n$ is integer-valued and $z_n\in [0,1]$. Now define $\lbrace z_1,\dots, z_n\rbrace$ to be a type 1 special ordered set (SOS1). Assuming the solver supports SOS1 constraints, you'll end up with a solution in which at least $n-1$ of ...

9

Equivalently, you want to remove the smallest number of constraints so that the resulting problem is feasible. You can do this implicitly, without enumerating all Irreducible Infeasible Sets, by solving an auxiliary ILP problem. Introduce a binary variable $z_i$ for each constraint (including variable bounds as a special case) $$\sum_j a_{i,j} x_j \le b_i$$...

8

When I started learning CP (coming from IP), one of the first things I discovered is that model elements are less standardized in CP than in IP. An IP model typically contains a polynomial objective function and equality/inequality constraints involving polynomial functions (where you are hoping the polynomials are linear or at worst quadratic). Beyond that (...

8

There are many resources available to learn constraint modelling. When learning about constraint modelling I can recommend the following books: Principles of Constraint Programming by Krzysztof Apt is probably the most used constraint programming book that will teach you all the aspects of constraint programming. The book that would most fit your ...

8

Solving: why is this solution optimal? As Richard explained, the objective in OR is not "fuzzy" like in ML: we assume an objective that can be evaluated by the computer. Once the problem is specified, there is not much to explain: you can prove optimality or infeasibility directly. Many solution methods attempt to prove optimality, and it is ...

8

@Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form: $$\lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \omega_i) \ge 1 \\ \sum_{i=1}^n \omega_i \le n-1 \\$$

8

How about $$\omega_1 + \cdots + \omega_n \le n-1$$ This way, at most all variables but one of them can take value $1$ simultaneously. In the context of knapsack problems, if each variable models the selection of a given item and that the sum of the weights of the items exceed the knapsack capacity, these inequalities are called cover inequalities.

8

An alternative approach that requires only one solve and no modification of the model is to modify branch and bound to prune by integrality when at most one integer variable takes a fractional value (rather than the usual requirement that all integer variables are integer-valued). You would also need to disable any presolve/cut routines that assume ...

7

Mention of intlinprog, without further specification, generally means the intlinprog of the MATLAB Optimization Toolbox. However, Gurobi also has a function called intlinprog, which mimics the interface of the MATLAB Optimization Toolbox intlinprog, but which calls the Gurobi solver. Similarly with Mosek. CPLEX has cplexintlinprog, which mimics the ...

7

In my view, mathematical optimization is inherently explainable for various reasons: The model is "white-box", i.e. it is developed by a person defining all the variables and constraints. This means that if a certain constraint is active or inactive, there is a logical conclusion that can be drawn from this. The result is, as you say, provably ...

7

These are called contiguity constraints. See this paper for models and references.

7

If I understand correctly, the following enforces your desired behavior: \begin{align} y_1 &= d_1 \\ y_2 &= d_2 \\ y_3 &= d_3 \\ y_4 &\ge d_1 + d_2 - 1\\ y_5 &\ge d_1 + d_2 + d_3 - 2\\ \end{align} If you also want to enforce $y_4 \implies (d_1 \land d_2)$ and $y_5 \implies (d_1 \land d_2 \land d_3)$, then include these additional ...

7

In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper: Dimitrios Michail, Joris Kinable, Barak ...

7

Excluding the constant portions of the objective function is perfectly fine. The optimal solutions will be unchanged and it should have no impact on how long the solver needs to solve the model.

7

Introduce binary variables $z_1$, $z_2$, and $z_3$, and impose linear constraints \begin{align} z_1+z_2 +z_3&= 1 \tag1\\ 1z_1+bz_2+(b+1)z_3 \le y &\le (b-1)z_1+bz_2+Uz_3 \tag2\\ z_2&\le x\tag3 \end{align} Constraints $(1)$ and $(2)$ enforce the three disjoint cases $y<b$, $y=b$, and $y>b$. Constraint $(3)$ enforces $x=0\implies z_2=0$, and $... 6 You can solve this as a quadratic assignment problem. With the same$x$variables as in @Kuifje's answer, you want to maximize $$\sum_{(u,v)\in A}\sum_{j\in C(u)}\sum_{k\in C(v)}|\omega_j- \omega_k| x_{u,j}x_{v,k} \tag1$$ subject to $$\sum_{j \in C(v)} x_{u,j} = 1 \quad \text{for v \in V} \tag2$$ One approach is to call a mixed integer quadratic ... 6 If you are dealing with Voronoi diagrams then perhaps your graph is planar, and in this case there is probably a good heuristic for the problem, but more details should be given I think before going down that road. In the mean time you can try working with a MIP as suggested by @SimonT. For example: Let$x_{vc}$be a binary variable that takes values$1$if ... 6 As Sune said in a comment, they really are both "big-M" constraints, differing (perhaps) in how "big"$M$is. If you choose$M$sufficiently large, then yes, your second constraint will not meaningfully limit the values of the$xvariables ... which likely is by design. Other constraints in the model will probably restrict the values of ... 6 With a low to moderate number of distinct weights, this is a variant of a transportation problem. An appropriate model would be \begin{alignat*}{1} \min\ \ & w_{\max}\\ \text{s.t.}\ \ \ & \sum_{j=1}^{J}x_{ij}=n_{i}\ \ \ i=1,\dots,I\\ & \sum_{i=1}^{I}a_{i}x_{ij}=w_{j}\ \ \ j=1,\dots,J\\ & w_{j}\le w_{\max}\ \ \ j=1,\dots,J\\ & 0\le ... 5 Based on the comments (thanks @RobPratt), C4 looks like\frac{\sum_{u=1}^U d_{u,1}L_{u}}{\sum_{u=1}^U d_{u,2}L_{u}} = \frac{\psi_1}{\psi_2}$$with similar constraints for other ratios. Just multiply both sides by the denominator, which males it a linear constraint.$$\sum_{u=1}^U d_{u,1}L_{u} = \frac{\psi_1}{\psi_2}\sum_{u=1}^U d_{u,2}L_{u}$Similarly ... 5 This is the transportation problem, a network flow problem (in a directed bipartite network) and hence solvable exactly as an LP. If you prefer a combinatorial algorithm, this might be a good exercise to learn the primal-dual method, and your heuristic approach can provide the initial solution. 5 Here's one way, assuming$L_i \le x_i \le U_i$. Introduce binary variables$y_i$and$z_i, with linear constraints \begin{align} \sum_i (y_i+z_i) &\ge 1 \tag1\\ y_i + z_i &\le 1 &\text{for alli$} \tag2\\ L_i(1-z_i) + (x_i^*+1)z_i \le x_i &\le (x_i^*-1)y_i + U_i(1-y_i) &\text{for all$i} \tag3\\ \end{align} Constraint(1)$forces$...

5

If you are willing to entertain an element of risk, and assuming that the feasible region is bounded, you might get away with a single new binary variable $z$. Assume that the feasible region $X$ is bounded, which implies that the number of feasible $x$ is finite. Generate a vector $r\in \mathbb{R}^n$ uniformly over the unit rectangle. Since the feasible ...

5

Pushing @Erwin's idea further, I got faster solve times by instead introducing variables ry and qx: for j in b: for k in c: o += ry[j][k] == r[k] *(xsum(y[k][jj] for jj in b if jj <= j)) for j in b: for k in c: o += qx[j][k] == xsum(( xsum (q[i][k]* x[i][jj] for i in a )for jj in b if jj <=j)) for j in b: for k in c: ...

5

You would have to introduce a helper variable (say $z_{ij}$) to count: \begin{align} \text{max }& \sum_{\forall i,j} x_{i,j} - z_{ij} &\\ \text{s.t. }& A_{i,j} y_{i,j} \leq B_{i,j} + Mz_{ij}&\forall i,j\\ &z_{ij}\in \{0,1\} &\forall i,j \end{align} Here $M$ is a sufficiently large number.

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