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
6
votes
1answer
189 views

Guides for strong MILP Formulations

When developing MILPs, often there are different alternatives possible to express a constraint. The question then arises, which of the alternatives is better, meaning, which alternative is expected to ...
5
votes
1answer
488 views

MILP - stronger models

Let $y, x_1, x_2, x_3$ be binary variables. The following holds: $y=1 \implies x_1=1, x_2=1, x_3=1$ I can model this by requiring (1) \begin{align}x_1 &\ge y\\x_2 &\ge y\\x_3 &\ge y\end{...
5
votes
3answers
2k views

How to represent an integer variable via binary variables?

Suppose we have a model with $N$ integer variables, i.e. $x \in \mathbb{Z}^{N}$ with $L \leq x \leq U$. How can we represent the integer variables via binary variables? Or in other words: how can we ...
2
votes
0answers
85 views

Minimax problem with a large high dimensional feasible region

How to solve minimax mixed integer problem with a large high dimensional feasible region? \begin{aligned} \max_{\vec{x}}\min_{\vec{y}} \quad & \vec{r} \cdot \vec{x} + \vec{s} \cdot \vec{y}\\ \...
5
votes
1answer
116 views

Is that Ok to exclude fixed components from an objective function?

Suppose we have the following objective function with one decision variable $x_i$ where $p_i$ is a fixed parameter for each $i$ and also, $a$ is a constant for the problem \begin{align} \label{eq} \...
5
votes
1answer
265 views

Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only

I'm totally new to the world of optimization and I have an optimization problem that I think it can be formulated as Mixed Integer Quadratically Constrained Quadratic Program (QCQP) but I'm not sure ...
3
votes
0answers
61 views

Linearization of a quadratic model, what is the difference while using gurobi?

I have a quadratic model of parking $N$ cars in $S$ separate lanes as follows. Each car has an arrival time and a departure time. Departure follow the last in first out principle. The objective is to ...
4
votes
1answer
253 views

CPLEX log always the same after hours ("Gap" and "Best Integer" always blanks)

I'm using the Java API of CPLEX 12.6.1 (with license) to solve a MILP (Mixed-Integer Linear Programming) maximization problem. The point is that, after 21 hours, CPLEX has consumed 32 GB of RAM and ...
5
votes
1answer
152 views

Solver Recommendation : Discrete Variables and Quadratic Constraints

I would like some solver recommendations to solve a problem with boolean/integer variables, mostly linear constraints but also some quadratic constraints. I also have an objective to minimize which is ...
4
votes
0answers
194 views

Simplified risk game: writing a pratical Minimax objective for mixed integer programming

Problem To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount ...
3
votes
1answer
89 views

Benders Decomposition for deterministic MILP

When I think of Benders Decomposition, I typically think of two-stage stochastic programs. However, I was wondering if there is any application to decomposing a large scale deterministic MILP with ...
4
votes
1answer
35 views

behaviour of CPXsetincumbentcallbackfunc

I am using the incumbent callback CPXsetincumbentcallbackfunc to identify integral solutions that do not satisfy nonlinear constraints that are not explicitly part of the constraint set. When such a ...
0
votes
0answers
93 views

Problems with a MILP

I need some advice, any hints will be appreciated. I have a MILP and I am using Gurobi to solve it. I have a feasible integer solution. When I use mipstart, after ...
2
votes
1answer
75 views

CPLEX Indicator Constraints in Java API

I'm using the Java API of CPLEX (12.6.1 version) to solve a MILP problem. This is how I create 'normal' constraints: ...
2
votes
1answer
111 views

The precision of the decimal number of the Cplex

I have faced a little weird problem when I use Cplex to solve my test problem. Basically, some of my data are float numbers up to three decimal numbers (For instance, 0.627). But, when I print out the ...
6
votes
0answers
120 views

Water quality component optimization

I have an optimization problem that I'm attempting to tackle. As you can see in the image below, there's a graph network through which water flows. I've drawn out the problem in the image to explain ...
5
votes
1answer
269 views

What is a good way to penalise LP relaxation?

I have a binary integer program. It is of a large size and the solver is taking longer time. I am thinking of relaxing the binary integer variable and making it a continuous variable. How can I ...
2
votes
2answers
107 views

Docplex, CPLEX Warning 1036 :

I am trying to solve a large-scale MIP problem. I have the following errors, I know, it's about the data, but I can't change the data. Is there a method to deal with it? ...
1
vote
0answers
146 views

CPLEX ignores a feasible solution given as start one

Assume we have 100% feasible solution for the model with decision variable a[i]. Then we are changing the objective function on something similar to ...
4
votes
1answer
92 views

Approximately evenly-spaced subsequence

Suppose you have $n$ time series data where the times are in arithmetic series with difference $d$, and suppose further that some of the data are missing at random (say, $p=.30$). Now suppose you want ...
6
votes
2answers
240 views

Forbid transformation of max(x,y) into MILP

The function $\max(x,y)$ can be linearized by making use of additional binary variables. I suppose global optimisers are implemented to perform this transformation automatically. Is there a global ...
1
vote
2answers
133 views

Combinatorial Optimization Problem using IBM ILOG CPLEX

Consider the combinatorial optimization problem described as below. Let $D=(V,A)$ be a directed graph with $V$ the set of vertices and $A$ the set of arcs, i.e., $A=\{(i,j)\mid i,j\in V\}$. On each ...
-4
votes
1answer
111 views

Multiple If else constraints in Mixed integer programming

How to formulate the following as constraints in MILP? a[0][0] = y, if x[0]= 0, a[0][0] = 0, if x[0] != 0, . . . . a[i][j] = b[i][j-1] + y, if x[j]=i, a[i][j] = a[i][j-1], if x[j] != i, ... . . . b[0]...
5
votes
1answer
172 views

How to model this multi-commodity flow problem with a twist?

Problem description I am working on a variation of the multicommodity flow problem on a graph $G=(V,E)$. I have requests $r_{uv}$ for pairs of nodes $(u,v), u\in V, v\in V$, which means that $r_{uv}$ ...
-1
votes
1answer
93 views

For docplex, it's possible to set the number of iterations without improvement?

When running the cplex model, I noticed that the CPLEX repeats the same gap value several times. I ask if there is a parameter in docplex that limits the number of iterations without improvements or ...
2
votes
2answers
83 views

Graph partitioning/cutting problem

Let $G = (V,E)$ be an undirected graph, with $e \in E$ has positive weight $w_e$. Given a set of integers $I = \{i_1,\dots,i_n\}$ such that $\sum_{k=1}^n i_k = |V|$. I want to find a partition $P$ of $...
4
votes
2answers
194 views

Setting up Branching Priority for GUROBI in Pyomo

I am currently experimenting with GUROBI and would appreciate some kind advice on the following: In Pyomo: Setting variable branching priorities, there was a response to doing so for CPLEX, hence I ...
2
votes
0answers
79 views

Pyomo Trouble - Number of Constraints in Output is 0 When It Should Be > 5000

I have an MILP program written in Pyomo and I am using CBC as a solver. Below is a description of my problem: The model works fine when it is run on my local computer The output is the following in ...
2
votes
1answer
65 views

Finding the minimum of a group of timings

I would like to seek some modeling advice on the following: Say for instance I have 5 nodes representing workstations of the operation of 5 jobs, and that I have less than 5 vehicles. Say I have two ...
0
votes
1answer
80 views

How to solve this clustering problem with heuristic or meta-heuristic approach?

I have clustering problem with servers and users. This is different to the one posted in https://math.stackexchange.com/questions/4088441/what-will-be-an-efficient-joint-clustering-solution-to-this-...
1
vote
1answer
161 views

References to publications on representation of any boolean function as a system of linear inequalities

It is known that any boolean function may be represented, in some sense, as a system of linear inequalities. But my rather intensive literature search brought a little references. I will appreciate ...
5
votes
4answers
498 views

How to visit a subset of network nodes in a single trip?

I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I ...
3
votes
2answers
86 views

MILP modelling on minimal disturbance of right-hand-side to make a linear system infeasible

I try to model the following problem: given $z\in\{0,1\}^m$ and a linear system $Ax\le b(z), x\in\Bbb R^n, A\in\Bbb R^{d\times n}, b(z)\in\Bbb R^{d}$, where $b(z)$ means that some entries of $b$ are ...
3
votes
1answer
101 views

Electricity market clearing price using fixed-MIP formulation?

Dual information of electricity markets clearing problem is required to calculate the marginal clearing price. As most electricity market problems are based on MIP (and dual information of MIP is not ...
7
votes
1answer
148 views

How can I strengthen a family of constraints in the presence of a clique constraint?

Suppose $x_i$ are binary variables, $y_j$ are arbitrary variables, $a_j$ and $b$ are constants, and I have the following linear constraints: \begin{align} x_i + \sum_j a_j y_j &\le b &&\...
4
votes
1answer
64 views

Name for subclass of ILP without any inequality constraints (including constraints on x)

In "Myths and Counterexamples of Mathematical Programming" myth "IP Myth 21" says: The problem of finding $x\in \mathbb{Z}$ such that $Ax=b$, where $A\in\mathbb{Z}^{m\times n}$ ...
3
votes
1answer
104 views

How to deal with log0 in optimization problem

I am adding some constraints to my model described in my previous post, where a discontinuous piecewise-quadratic functions is the objective to be minimized in cvx. Here I have an additional terms, ...
3
votes
2answers
179 views

How to reformulate a discontinuous piecewise-quadratic functions

I am trying to develop a model, solving an optimization problem which has the following objective function: variable p(i); minimize sum(cost) subject to p>=0 ...
2
votes
1answer
46 views

How to interpret no-overlap constraints with rotation as a mixed integer programming

Suppose, we want to locate some given facilities $\left \{ (i,j) \ |\ (i,j) \in \text[{1,\cdots, N}]\right \}$ in a specific area. Each facility has a predefined dimension with a length $l_{i}$ and ...
3
votes
1answer
103 views

Obtaining linear relaxation objective value from MILP model coded in Pyomo

I would like to seek some advice on modeling the following: I am currently using Pyomo to generate my MILP model in Pyomo. It seems that it is not possible to cast the integer and binary variables to ...
6
votes
1answer
165 views

How to treat a system of bilinear constraints

A model contains constraints of the following form $R(k) \leq X(k) G(k)$ where $X(k)$ binary and $G(k)$, $R(k)$ non-negative variables. The index $k$ runs from $1$ to $50$. I linearise the equations ...
3
votes
1answer
84 views

Constraints that set values to binary variables depending on other binaries

I am trying to write a mathematical problem that involves some conditions based on binary variables. More specifically, I have a set of three binary variables $d_1$, $d_2$, $d_3$ and depending on ...
12
votes
6answers
934 views

Where can I find documentation on good practices for efficient formulations of a problem?

I am sort of new to mathematical optimization and have to build some fairly complicated models for my thesis. I was wondering where I could find literature to help me develop more efficient versions ...
5
votes
3answers
177 views

Modelling precedence relations

I have two tasks $i$ and $k$ with durations $d_i$ and $d_k$, where $d_i$ and $d_k$ are nonnegative variables. I would like to model that $i$ may precede $k$ or $k$ may precede $i$ and that they may ...
4
votes
1answer
196 views

Assignment problem with batching costs

I am studying an assignment problem with batching costs, and I would like to know if there is a standard name or algorithm for this problem. I know this problem can be formulated as mixed-integer ...
2
votes
1answer
72 views

How does the RCPSP's precedence constraint work?

In [1] the authors define the RCPSP (resource-constrained project scheduling problem) as follows: minimize $$ \sum_{t} t x_{n t} $$ subject to $$ \begin{array}{c} \sum_{t} x_{j t}=1, \quad j \in J, \\ ...
1
vote
1answer
144 views

Non-linear optimization local or global solution

In an NLP, I have a constraint that I would like to formulate in a convex manner preferably without introducing binary variables and/or big M formulations if possible. The actual problem is non-convex ...
3
votes
1answer
182 views

Linearizing a quadratic function with more variables or not in Gurobi?

Suppose I want to set the price $0 \le p_t \le p_{max} $ and based on the price, demand is determined $D_t(p_t)=a-bp_t$. Inventory level at each time is denoted by $I_t$ and it is determined by $I_t= ...
2
votes
3answers
165 views

Linearizing a Max Function in the constraint - not working

I have a minimization function which is in its simplest form looks like below. I am including the index of the variables. ...
6
votes
2answers
307 views

Mixed-integer optimization with bilinear constraint

So I have an optimization problem of the following form: \begin{aligned} \max_{x,y} \quad & \sum_i x_i \\ \text{s.t.} \quad & \sum_i x_iy_i \leq a \\ \quad & x_{\min} \leq x \leq x_{\max} ...

1 2
3
4 5
11