# Tag Info

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

This is a semicontinuous variable, and you can enforce it by introducing a binary variable $y$ and imposing linear constraints $$cy\le x \le My.$$ If $y=0$, then $x=0$. If $y=1$, then $x\in[c,M]$.

8

This answer complements that by @worldsmithhelper . Not only does an objective function not have to include all the decision variables, it need not include any of them. An "optimization" problem having a constant (zero) objective function, which is equivalent to not having an objective function, is called a feasibility problem. Your understanding ...

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

6

It looks like you want to model $x \; \Longrightarrow \; y$, or in conjunctive normal form : \begin{align*} \lnot x \vee y \\ 1-x + y \ge 1 \\ x \le y \end{align*} If $y$ takes value $1$ when a given parameter $p$ is larger than a given variable $z$, then you need to add $p > z \; \Longrightarrow y=1$, or its contraposition $y=0 \; \Longrightarrow \; p \... 5 Your last example, is certainly not that interesting. Let$f_1(x)$and$f_2(x)$abe the objective functions. From multi-objective optimization theory it is well known that if we use strictly positive weights for the objectives and solve the corresponding weighted sum scalarization, any optimal solution is efficient. In this case, we choose weight vector$\...

5

NO Not all decision variables need to be present in the objective. They can be often used to handle constraints or express other things. Consider this simple problem: $$\min_{x,y_1,y_2,y_3,y_4,y_5 \in \mathbb{N}} x \text{ subject to }$$ $$\forall i \in \{1,2,3,4,5\}: \ 0 \leq y_i \leq x$$ $$y_1+y_2+y_3+y_4+y_5 = 12$$ Which might answer the question how much ...

4

If you can't find (or can't afford) a solver that will handle a problem with that many nonzero matrix coefficients, and if your problem has a structure that fits one of the following methods, you might try either Dantzig-Wolfe or Benders decomposition.

4

Try adding valid constraints $$y_{i,j} \le \sum_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k} \quad\text{for (i,j) such that \hat{y}_i = 0 and j \in \tilde{V}\setminus\{i\}}$$ that enforce the logical implications $$(y_{i,j} \land \lnot\hat{y}_i \land [j \in \tilde{V} \setminus\{i\}]) \implies \bigvee_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,... 2 Assuming you are comparing Benders results to CPLEX solutions, why not use the CPLEX formula for the Benders results? Best integer would be your LB and best bound would be the current objective value of the master problem. 2 The quickest way to study this is to use Generalized Disjunctive Programming. If we use disjunctions to formulate the problem, we get:$$ min/max \quad z=f(x)\\ \begin{bmatrix} Y_1 \\ x_1 = a \\ x_2 \geq c\\x_3 \geq d \end{bmatrix} \veebar \begin{bmatrix} Y_2 \\ x_1 = b·x_3 \\ x_2 \geq c\\0\leq x_3 \leq d \end{bmatrix} \veebar \begin{bmatrix} Y_3 \\ x_1 = 0 ...

2

The question is a bit confusing, in that you say you have a MILP, mention a continuous variable but nothing about integer variables, and then ask about the dual solution (which exists for a continuous model but not for an integer model, at least not in the usual sense of "dual"). Assuming that we are talking about a linear program with the ...

2

MILP with a fixed objective function is hard as finding a feasible solution. Since this can still encode n-queens completion or SAT it is still in the same complexity class. Depending on your problem some MILP heuristic might find a solution. Constraint satisfaction programming might be fast but it could be that encoding it into sat or pseudo boolean form ...

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