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
10
votes
2answers
588 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
133 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
55 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
52 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
42 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
61 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
74 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
42 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
71 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
75 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 ...
8
votes
3answers
761 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
93 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
192 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
29 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
161 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
52 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
94 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
188 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: ...
8
votes
3answers
314 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
90 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
74 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
108 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
238 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
236 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
156 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
401 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
222 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
61 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
160 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
189 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
342 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
64 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
83 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
113 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
117 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
146 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
90 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
81 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
82 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
105 views
12
votes
1answer
75 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)$ ...
10
votes
2answers
125 views

How to exploit known solution in MILP

I have an MILP model to which I get an integer feasible solution as a result of a heuristic search. In this particular example, the initial solution turns out to be the optimal solution, which I prove ...
3
votes
0answers
56 views

Integer variable optimization - decreasing execution time

I have a variable declared as follows in AMPL: ...
5
votes
1answer
149 views

Find the cheapest shopping cart

Given a list of items to buy on an e-commerce, generate the cheapest possible cart (which obviously includes all the items). The items can be purchased from many sellers at different prices. Sellers ...
6
votes
2answers
1k views

IF X = 0 THEN Y = 1, IF X > 0 THEN Y => 0

I'm trying to model the following IF $tS = 0$ THEN $Y = 1$, IF $tS \gt 0$ THEN $Y \ge 0$ $tS$ is a positive real number and $Y$ is binary. I tried the following: $tS - \epsilon \ge -M Y$ but ...
14
votes
2answers
1k views

Why do we need to measure the difficulty of mixed-integer programming problems?

I'm doing a project about the estimation of the difficulty of mixed-integer programming problems. The MIP instances are from MIPLIB 2017. And there are three categories of MIPs provided by MIPLIB 2017,...
6
votes
2answers
163 views

Cplex 12.10: How can I solve an LP relaxation?

I have an IloCplex object which contains a MILP. Is there a way to obtain the objective value of its LP relaxation, without having to rewrite the entire model as ...
3
votes
1answer
67 views

Controlling the constraint execution sequence in docplex

I have tried to implement my question asked here with the help of Github code link. Below is the linearized version of the MTZ like constraint as per the answer given here. Constraints below assign ...
5
votes
1answer
104 views

Converting if else condition to MIP constraints - validation

I have an if else condition as follows: If $g \ge 0$ then $e=1$, else $e=b$. I formulated MIP constraints using big-M as follows where I am setting $\delta=1$ if $g \ge 0$: \begin{alignat}2g &\...
5
votes
2answers
255 views

How can this relationship be modelled?

I declare an array of binary variables as $y(i), i = 1, ..., N$ I would like to model the following: If $y(i-1) + y(i) = 1$ then $y(k) = 0$ for $k < i$ and $y(m) = 1$ for $m \geq i$ To make ...

1
2 3 4 5