27

The irreducible infeasible subsystem (IIS) for an infeasible linear program (LP) is a minimal subset of constraints that has no feasible solution, i.e., an inconsistent set of constraints for which any proper subset of the constraints is consistent. It is not true that an IIS is unique. For intuition, consider that there may be more than one source of ...


27

If $x$ is binary: Then the "if" condition really means either "$x = 0$" or "$x=1$". To enforce "if $x=0$ then $y=1$": use $$y \ge 1-x.$$ To enforce "if $x=1$ then $y=1$": use $$y \ge x.$$ If you want to require that $y=1$ if and only if the condition holds, then replace the $\ge$s above with $=$s. If $x$ is continuous: In this case, numerical inaccuracy ...


20

In an optimization model, a hard constraint is a constraint that must be satisfied by any feasible solution to the model. On the other hand, a soft constraint can be violated, but violating the constraint incurs a penalty in the objective function (often, the greater the amount by which the constraint is violated, the greater the penalty). So, a good way to ...


20

(I'm going to change $c$ to $x$ in my answer, since $c$ is usually used for cost coefficients, not decision variables.) We want a set of constraints that enforces $X = \max\{x_1,x_2\}$. Define a new binary decision variable $y$, which will equal 1 if $x_1 > x_2$, will equal 0 if $x_1 < x_2$, and could equal either if $x_1 = x_2$. Let $M$ be a constant ...


20

This can be handled as an MISOCP, Mixed-Integer Second Order Cone problem. The leading commercial MILP solvers can also handle MISOCP. Specifically, due to $x_{ij}$ being binary, $x_{ij}^2 = x_{ij}$. Therefore, the left-hand side is the two-norm of the vector over $i \in I$ having elements $\sqrt{a_{ij}} x_{ij}$. I don't know whether this is the best way ...


18

Arguments 3 and 4 are incorrect. The Right-Hand Side (RHS) is not convex. Even if it were, setting a nonlinear equality with either side non-affine is non-convex. As the final coup de grace, even if the RHS were convex, an inequality, {affine expression} $\le$ {convex RHS}, is going the wrong direction to be convex. I suggest you study sections 2.3 and ...


16

You have asked a broad question, so I will provide a broad answer. Integer programming typically refers to integer linear programming which is a mathematical modeling and solution paradigm. Decisions are modeled as a vector of real numbers, some of which are further constrained to take only integer values. The decision vector is constrained to satisfy a ...


16

Lazy constraints will only be checked when an MIP solution satisfying all other constraints, including integrality, is found. If you provide all your lazy constraints in advance to CPLEX, for example, then your main benefit is that these constraints are only checked against solutions that would otherwise be feasible. However, you may have an exponential ...


15

I going to assume that the ratio $L(x)/Q(x)$ is nonnegative. If it can be negative, I think there may be a workaround, but this will complicated enough without dealing with that. I'm also going to assume that $Q(x)$ and $L(x)/Q(x)$ have a priori upper and lower bounds, say $\underline{Q} \le Q(x) \le \overline{Q}$ and $L(x)/Q(x) \in \{1,\dots,N\}$. You can ...


14

Essentially you are trying to constrain $|p_1-p_2|$, where $p_1$ and $p_2$ are the pressures. Normally this must be done using binary variables (see this question, which @MarcusRitt linked to), but in this case, binary variables are not needed (since the lower bound on the absolute value is 0, as @MarkLStone pointed out). In short, you can simply use the ...


13

You are right that most real-world problems are constrained, and therefore, for the most part, "optimization" and "constrained optimization" are synonymous. However, some algorithms only apply to unconstrained problems: an easy example is bisection search. So when people say "constrained optimization," they are emphasizing that they're considering the ...


13

Counterexamples to your arguments: Argument 1: Only affine equality constraints are convex, $x = y^2$ is not convex. Argument 3: Take $f(x) = x^4$ and $g(x) = x$. Both are convex, but the ratio $h(x) = \frac{x^4}{x} $ is not. Argument 4: Let $f(x) = x$, and $y \in \mathbb{R}$. $f$ is convex, but $g(x, y) = yf(x) = xy$ is not.


12

These are know as "indicator constraints" or "on/off" constraints. The best formulation is the convex-hull one, it includes the optimal big-M value plus additional non-redundant constraints, here's a note characterizing this formulation. There's also a generalization for convex nonlinear "on/off" constraints here and recent extensions here.


12

Let $M$ be a new parameter (constant) that equals a large number. Greater-than-or-equal-to constraints: The constraint is $a_1x_1 + \cdots + a_nx_n \ge b$. Rewrite it as $$a_1x_1 + \cdots + a_nx_n \ge b - M(1-y).$$ Then, if $y = 1$, the constraint is active, and if $y=0$, it has no effect since the right-hand side is very negative. (If all of the $a_i$ ...


12

Rather than linearising the logical constraint, I would try the logical constraints built in a solver. Gurobi and SCIP both have indicator constraints. My colleague works with these a lot and he’s finding the indicator constraints in Gurobi perform worse than big-M. He’s in contact with the Gurobi developers so I might be able to get more info if there’s ...


12

You need to model disjunctive constraints. I will assume that variable $x$ is constrained to lie in $L_1 \le x \le U_1$ or $L_2 \le x \le U_2$. For instance, if you have the constraint $2 \le |x| \le 5$, then choose $L_1 = -5$, $U_1 = -2$, $L_2 = 2$, $U_2 = 5$. My solution handles a more general case than what you require, but includes your situation as ...


12

This is a very broad question and there is a lot going on here. So I will provide a few initial thoughts; hopefully others will chime in as well; and then you might want to post more specific questions, which will be easier for us to provide more concrete answers to. The approach you outlined is focused on the inventory level (IL). It assumes that there is ...


12

I suspect you read that actual floating point optimization solvers treat strict inequalities ($<$ and $>$) as non-strict inequalities ($\le$ and $\ge$). Solvers also give themselves a fudge factor, called feasibility tolerance, equal to the amount by which they may be violated in reality but treated as satisfying the constraint by the solver. If you ...


11

You can strengthen your "conflict" constraint to a "clique" constraint: $$\sum_j x_r^j \le 1$$ for all $r$. There are fewer of these, and they dominate the conflict constraints.


11

This is not true in practice. Moreover, this is something almost impossible to guess without experimenting. Indeed, adding constraints (proven to be mathematical valid, or just guessed by your flair and feeling of the business) to a mathematical optimization model that is solved by constraint programming techniques or integer programming techniques should be ...


10

If you want to use the KKT conditions for the solution, you need to test all possible combinations. This is why in most cases, we use the KKT's to validate that something is an optimal solution, since the KKT's are the first-order necessary conditions for optimality. For convex nonlinear optimization, you are better off using sequential quadratic ...


10

Welcome to OR.SE! If you're looking to enforce $$\max\limits_{pcj}X_{pwcj} \leq L_{wk}, \ \forall w,k$$ then simply using the constraint $$X_{pwcj} \leq L_{wk}, \ \forall p,w,c,j,k$$ will do the trick. This will ensure every value (including the maximum) will be at most $L_{wk}$. (If there's another dynamic you're looking to enforce, e.g., within a set of ...


10

Assuming that the $c_i$ and $q$ are all positive you may add one binary variable $y_i$ for every $i=1,\cdots,n$ then you may do \begin{align}c_i x_i &\geq q y_i \quad\forall i\\\sum_i y_i &\geq 1\end{align}


10

My approach would be: $$\begin{align} \min\>&- f(\color{darkred}x)+\sum_j \color{darkblue}p^-_j \color{darkred}s^-_j +\sum_j \color{darkblue}p^+_j \color{darkred}s^+_j\\ &\sum_i \color{darkblue}a_{i,j}\color{darkred}x_{i,j} = 10 -\color{darkred}s^-_j + \color{darkred}s^+_j&&\forall j\\ &\color{darkred}s^-_j,\color{...


9

Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route. However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article ...


9

If the model in PuLP is: from pulp import LpProblem, LpVariable, LpMaximize, lpSum m = LpProblem(name='example', sense = LpMaximize) x = LpVariable.dicts(name='x',indexs=[1,2,3]) m += lpSum(x) <= 3, 'c1' m += lpSum(i*x[i] for i in [1,2,3]), 'obj' We can access the coefficient of $x_1$ in 'C1' with: m.constraints['c1'][x[1]] # This the coefficient => ...


9

As the borders between statistics and machine learning are diffuse, I take freedom to include statistics. Some links: Non-negative least squares, posts on cross validated. But often restrictions can be implemented just by reformulation. Order-restricted statistical inference should be better known and more used. There is a new R package being developed ...


9

Equivalently, $c=\max(a,b)$. See this post.


9

You can do this with no new variables. Let $S=\{k:c_k \ge q\}$ and add the constraint $\sum_{k\in S}x_k \ge 1$.


9

The given constraint is a weak linearization of $(x_2 \lor x_3)\implies x_4$, which can be rewritten in conjunctive normal form as $(\neg x_2 \lor x_4) \land (\neg x_3 \lor x_4)$, yielding the tighter linearization $x_2 \le x_4 \land x_3 \le x_4$. The wording of the problem seems to instead mean $(x_2 \land x_3)\implies x_4$, which can be rewritten in ...


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