Questions tagged [mixed-integer-programming]

For questions about mathematical optimization problems involving both continuous and binary or general integer variables.

Filter by
Sorted by
Tagged with
3
votes
1answer
133 views

Resource constraint with MIP model

My question is how to model a resource constraint with MIP model (how should I modify it?) A factory is making blocks. If there is space left at that time, the block can be assembled. (If the factory ...
3
votes
0answers
79 views

Linearization of the shifted copy of a function

Suppose in a model I have the expression $y_{1}(x) = 10 + 5 x^2$ where $x \in [0,20]$ is a continuous variable. In order to be able to use an MILP solver, I piecewise linearise $z_{1} = x^2$, by ...
5
votes
1answer
140 views

How are indicator constraints implemented? [duplicate]

I wonder how systems like CPLEX, GUROBI, etc implement indicator constraints. Do they just implement Big M equivalents? If yes, what is then the justification for using them? Edit The question does ...
6
votes
1answer
202 views

Convert summation of min functions into linear constraints for optimization

I have the following optimization problem: $$ \mbox{maximize } j^{*} \mbox{ subject to:} \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \geq \lambda, \lambda \in \mathbb{R} \mbox{ and } {\bf A}_j,{...
1
vote
0answers
51 views

Linearize max function in a constraint [duplicate]

I have a constraint as follows: $ \sum_i {r_i} \geq \max \{g_j, B_j\} $ where, $r_i$, $g_j$ are variables and $B_j$ is a parameter. How do I linearize the constraint (I suppose using big-M method)?...
4
votes
2answers
386 views

How to convert this if-then constraint to MIP constraint?

How to convert this if-then constraint to MIP constraint? $\text{if } a \geq 0 \text{ then } b=K_1 \text{ else(a <0 ) } \ b =K_2$
5
votes
0answers
353 views

What is the difference between root relaxation and LP relaxation

(I apologize. I saw this question but, I do not know these may be the same or not.) I am trying to solve a MIP problem and have an issue about that. The problem's LP relaxation has the objective ...
2
votes
1answer
132 views

How to determine whether the solution is integer feasible in a CPLEX heuristic callback?

I am working with a MILP formulation of a routing problem using Concert CPLEX 12.10. And I am implementing a greedy heuristic that uses the variables fractional values to attempt to construct an ...
3
votes
0answers
48 views

Linearisation using SOS2

I am trying to linearise the following expresssion. $C(k) = B(k) e^{-d(k)}, B(k) \ge 0 , d(k) \ge 0 $ I am trying to do this by using SOS2 sets. I set $X(k) = e^{-d(k)}$ and I get $C(k) = B(k) X(...
11
votes
2answers
676 views

Can presolve reductions change the value of the linear programming relaxation?

For integer programs solvers (like Gurobi, Cplex, ...) report the value of the linear programming relaxation for integer programs, i.e. ...
6
votes
2answers
170 views

What is the definition for an integer-friendly constraint?

I have seen some papers claiming that their proposed model is integer-friendly. I would like to get more information about what type of constraints we can call integer-friendly. Probably, it can be ...
3
votes
1answer
256 views

Why does the getTime() function from cplex concert returns wrong value?

I am running a MILP formulation (implemented in C++) with the Cplex Concert Technology 12.10, and I am trying to get the total elapsed time. So till the moment, I have tried three approaches: Be ...
1
vote
0answers
71 views

Ways to improve lower bounds while solving MIPs

What are the ways to improve lower bounds while solving a minimization problem (MILP)?
3
votes
0answers
52 views

What are the efficient ways to model this scheduling problem and ways to improve running time

There are $N - \{1 \ldots N\}$ jobs, each with processing time $p_j$, to be scheduled on $M - \{1 \ldots M\}$ machines over span of $D - \{1 \ldots D\}$ days and while working $T - \{1 \ldots E \ldots ...
1
vote
2answers
328 views

Pulp: slack variable to identify & measure extent infeasible in supply problem

I am currently modelling a supply problem that attempts to optimise a rail schedule which moves products from a production plant, to a warehouse to satisfy sales. The model is working fine (thanks in ...
3
votes
1answer
105 views

What kind of scheduling problem is this?

I am trying to develop algorithm to solve following basic version of the problem. 1) I would like to know what this problem is called in literature so that I can look it up 2) What are efficient ...
5
votes
0answers
64 views

Complexity of determining whether a LP or MIP is infeasible

What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
3
votes
1answer
197 views

How to fomulate the following conditional constraint in MILP?

How can I formulate the following conditional constraint to a linear constraint using indicator variables? Please note that all variables are continuous and $c \ge 0$ $\text{1: if} \ c=0 \ \& \ ...
5
votes
1answer
955 views

Non-constant expressions cannot be multiplied

I am trying to solve a valued n-queens problem, in which queens in black squares worth double of those in white squares. I solved it in AMPL just fine, but I would like to try that in Python using a ...
9
votes
3answers
1k views

Open source MILP solver for quick “good enough” solution

I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained ...
3
votes
1answer
132 views

Modeling the sum of binary variables

Suppose $x_{1},x_{2}, \cdots ,x_{n}$ are binaries. I would like to model the following: IF $x_{1} + x_{2}+ \cdots +x_{n} \ge 2$ THEN $x_{1} + x_{2} = 2$ IF $x_{1} + x_{2}+ \cdots +x_{n} \ge 3$ ...
1
vote
3answers
221 views

Using big M values for a constraint

I want to enforce $x_{i,j}=x_{k,j}\implies z_i \neq z_k$ where $k = i-1$ so I used \begin{align}z_k + 1 - (x_{i,j} - x_{k,j})) \leq z_i \leq z_k - 1 - (x_{i,j} - x_{k,j})\quad\text{for each $j$}\end{...
1
vote
1answer
36 views

Enforcing discontinuous range for a variable

I want to enforce the following ranges for a set of variables, where the ranges for each variable are discontinuous. For example, I have two sets of ranges for each variable, \begin{align}\sf LB_1 &...
2
votes
1answer
168 views

Does this problem fall into any common problem definition…Knapsack maybe?

I am struggling to find a representative problem formulation for this optimization challenge. I have implemented a MILP in Matlab, but the run time is taking more then a day. My goal is to see if it ...
1
vote
1answer
63 views

Derived variables of when a decision variable appears?

I am dealing with a multi-travelling passenger problem. $x_{i,j}$ is a binary variable that allocate a passenger $i$ to a vehicle $j$, every vehicle can carry only $n_{pv}$ passenger where $i \in \{1,...
4
votes
1answer
174 views

How to write quantity discount constraint?

In a simple transportation problem like below image, how to model a constraint for shipment discount e.g. if quantity transported from any origin to any destination is more than 100 unit then the ...
5
votes
3answers
206 views

Problem with binary decision variable constraints in VRP

I would like to create non-linear violation costs in my VRP. I already created my whole VRP with time windows in which I have these decision variable: ...
10
votes
3answers
843 views

Settings for a faster solution of a MILP (GUROBI, python)

Using GUROBI with python. When solving a MILP, I notice that the incumbent is very early (25sec) at the optimal point but the best bound is so slow to fall (maximization problem) that it takes ages (...
4
votes
1answer
94 views

Is working with equations in an MILP more efficient than working with inequaltities?

I have the following model \begin{align}\max&\quad B_{1} + B_{2}\\\text{s.t.}&\quad 0 \leq B_{1} \leq c_{1}\cdot Y_{1} \\&\quad 0 \leq B_{2} \leq c_{2}\cdot Y_{2} \\&\quad \end{align} ...
2
votes
1answer
207 views

Nested set in OPL/CPLEX

I'm trying to solve a scheduling problem using OPL/CPLEX. In the model, there are nine tasks in which each task has its specific precedence. the precedence relationship is as follows: ...
7
votes
2answers
118 views

How can preferences be modelled in MILPs?

Suppose a MILP model includes the following constraint: $ \begin{gather*} B_{1} + B_{2} + B_{3} \le 100 \end{gather*} $, where $B_{1},B_{2},B_{3}$ are nonnegative reals. Suppose that $\begin{...
12
votes
2answers
341 views

“Out of the box” Mixed Integer Programming Heuristics

I currently have a complex Mixed Integer Program (a sort of vehicle routing problem variant, with multiple vehicle types and without assigned pickup -> delivery routes, among other complications) ...
4
votes
2answers
302 views

What are the most useful evaluation metrics when comparing the performance of different model formulations

Suppose you are writing a paper about a certain new problem class. You have certain problem instances of different size (real-world as well as random) given. You developed different integer ...
7
votes
2answers
202 views

Is the iteration-limited Simplex dual solution of a MIP node useful?

Idea Sometimes I encounter problems where Simplex spends many iterations for final convergence to the optimal objective value. Let's suppose, this happens when solving branch and bound-tree nodes as ...
5
votes
3answers
450 views

How can I represent null or dashes in a cost matrix or incidence matrix in CPLEX?

In the image below, the cost matrix of customers and supplier has several dashes which indicates the impossibility of certain suppliers with certain customers. How can I represent these dashes in ...
7
votes
2answers
262 views

Do Benders cuts exclude current solutions?

I am wondering if optimality cuts in Benders algorithm exclude the possibility to have the same solutions and as a result, have the same optimality cut? I don't know why it is not possible to have the ...
5
votes
1answer
70 views

Help with a MILP formulation for service scheduling

I'm trying to formulate a MILP for scheduling service jobs for multiple devices. Let's assume that each device $i$ has a life $\ell_i$ and that I have $n$ total service visits to allocate at times $\{...
4
votes
3answers
181 views

Formulate relationship between four binary variables

I have four binary variables $x_{h}$, $x_{h'}$, $y_h$ and $y_{h'}$. I need to have the following relationships satisfied between the variables: 1- If $y_h = 1$ and $y_{h'} = 1$, then exactly one of $...
3
votes
2answers
308 views

Mocking up conditional statements in LP

I would like to know how if condition statements in linear programming can be reformulated using indicator constraints, and hence solved as a mixed integer linear program. Specifically: 1. Is it ...
5
votes
1answer
428 views

Where can I find resources to learn mathematical modelling for real life operation research problems like combinatorial optimization?

I find it hard to form math models for real life operations research problems, how can I learn this? Any books, tutorials available?
4
votes
0answers
69 views

Adding redundant inequality to a model

The following relationship is part of my optimization model ($W_k$ denotes a binary variable) $$W_{1} \le \cdots \le W_{k-1} \le W_{k} \le W_{k+1} \le \cdots \le W_{k^{\max}}$$ My question is, do ...
2
votes
1answer
135 views

How to formulate logical or constraint in cplex?

How to write the following constraint in cplex? the cost for full truck load is $700 and the cost of fractional truck load is \$800 *fraction up to $700
0
votes
1answer
172 views

How to form math model to solve this problem using cplex

Hiring company has the following requirement within a year; week 1 to 5: 20 week 6 to 20: 40 week 21 to 40: 35 week 41 to 60: 55 week 61 to 80:75 week 81 to 100: 60 Training time for an ...
6
votes
1answer
262 views

Advanced Heuristics for MIP vehicle routing problem in PuLP

I am currently trying to speed up an MIP. An approach I was considering was to implement a cut callback heuristic with PuLP (one which rounds relaxed integer variables greater than .9 to 1). ...
8
votes
2answers
169 views

Modeling Linear Program to decide if an inequality is facet

Suppose you have a set of points $v_1,\ldots,v_n$, which are the vertices of the polytope $P=\operatorname{conv}\{v_1,\ldots,v_n\}$ and a linear inequality $a^\top v \leq b$. What would be a linear ...
5
votes
2answers
247 views

Linearizing objective function with variables inside an indicator function

I am working on a problem in which I am trying to maximize the average of a variable only for the data that meet a certain condition with a constraint on the number of data that meet this condition. I ...
5
votes
1answer
88 views

How to linearize difference of absolutes?

How to linearize difference of absolutes? $$|a|\ge k|b|$$ where $a,b$ are variables and $k$ is a constant.
3
votes
1answer
85 views

How to design the objective function of an MILP problem

In an MILP problem, I wonder if it is better to use an objective function that involves as many of the variables of the problem as possible as opposed to an objective function with only a few ...
3
votes
1answer
125 views
12
votes
1answer
99 views

Benders subproblem feasible region dependent upon solution master problem

Suppose I want to solve a naturally MINLP problem of the following form: $$ \min_{x,y} \{c'x + y \mid Ax \leq b, Dx + Ey \leq f, G(x)y\leq g, x \in \mathbb{Z}, y \in \mathbb{R}^+\} $$ Here $G(x)$ ...

1
3 4
5
6 7
9