Skip to main content

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
1 answer
103 views

Modelling Question

Let $W^C_t$, $W_t$ be binary variables and $p$ an integer variable with $1 \leq p \leq 3$ The variables are related through the following equation: $$W^C_t = \sum_{\theta=1}^{p} W_{t-\theta}$$ I can ...
Clement's user avatar
  • 2,252
-1 votes
2 answers
92 views

How to apply smooth approximation to non-linear complementarity constraints?

$P =$ $ x, if U \geq U^{max} $ $ y, if U^{up} < U < U^{max} $ $ z, if U^{down} < U < U^{up} $ $ \alpha, if U^{min} < U < U^{down} $ $ \beta, if U \leq U^{min} $ Where $P$, and $U$ ...
Ghulam Mohy-ud-din's user avatar
6 votes
2 answers
247 views

Robust optimization for IP formulation

I am researching the robust version of a problem. I have managed to produce an Integer programming formulation which solves the problem with perfect knowledge. From my research on the topic one can ...
Pia MiA's user avatar
  • 392
5 votes
2 answers
148 views

Number of simple cycles on the graph

I would like to know if there is an efficient way to formulate simple cycles on the Graph/Digraph. Let's say, there is a grid-form graph for which each vertex is only connected to a limited number of ...
A.Omidi's user avatar
  • 8,892
1 vote
1 answer
119 views

How to model this problem with multiple objectives?

This question is related to How to deal this L0 norm of a vector of L2 or L1 norms in objective? I have an optimization variable denoted as ${\bf A\in\mathbb{C}^{100\times 5}}=\begin{bmatrix}{\bf a}_1&...
KGM's user avatar
  • 2,285
6 votes
2 answers
257 views

How to partition a giant tour into feasible routes?

In vehicle routing problems, the route first cluster second approach starts by computing a "giant" TSP tour (which typically does not satisfy all constraints of the problem), and then ...
Kuifje's user avatar
  • 13.4k
2 votes
0 answers
85 views

Branching the product of binary and continuous variable in Gurobi

I have a binary variable (X) multiplying a continuous variable (Y). I know I can linearize by adding an auxiliary variable (I have that model working), but I now want to do my own branching in the ...
orpanter's user avatar
  • 517
3 votes
2 answers
131 views

How to linearize or fix this disciplined convex programming error?

How can I linearize this constraint $$d_{u,c}\sigma \le \|{\bf f}_{u,c}\|^2\le Td_{u,c}$$ $\sigma$ is a very small number based on scale of $f$ $T>0$, ${\bf f}_{u,c}$ is optimization variable, a ...
KGM's user avatar
  • 2,285
6 votes
2 answers
499 views

Is this constraint with an indicator function nonlinear?

We have two variables $x\geq0$ and $y\in\mathbb{Z}^{0+}$. We have this constraint in our model $$x = \sum_{i = 0}c_i \mathbb{1}_{\{y=i\}}$$ where $c_i$ is a parameter and $\mathbb{1}_{A} = 1$ if $A$ ...
user avatar
1 vote
1 answer
78 views

MILP: Substituting products with additive logarithms

I would like to linearize a product, for example $a*b$. if I solve my solution in log space, I can formulate it as $a+b$ and when my final output is returned, remember to convert back to original ...
jbuddy_13's user avatar
  • 551
1 vote
1 answer
143 views

How to model this constraint? [duplicate]

I have a system with $C$ machine and $U$ users. The decision variables are $d_{u,c}$ and ${\bf f}_{u,c}$ with $c=1,2,\cdots,C$ and $u=1,2,\cdots,U$, where $$d_{u,c}\in\{0,1\}$$ $${\bf f}_{u,c}\in\...
KGM's user avatar
  • 2,285
3 votes
1 answer
148 views

How to remove a callback that was previously registered in Julia?

I'm coding in Julia, how can I do the same as "Remove(Cplex.Callback)" function does in C++ ?
Brown's user avatar
  • 173
2 votes
3 answers
315 views

How can I extract the .lp or .mps version of this (Rubik's cube example)

https://cw.fel.cvut.cz/b192/_media/courses/ko/ilp_rubik.pdf In pages 5-6 this example solves a cube with Gurobi. I don't have Gurobi but I'd like to get .lp or .mps version for my own testing?
user9050's user avatar
  • 119
2 votes
1 answer
79 views

Articulating categorical soft constraints in MILP

I'm curious how is the best way to articulate a soft, categorical constraint for MILP solvers. In example, say that there are two sizes of t-shirts, small and large. Likewise, people have ideal t-...
jbuddy_13's user avatar
  • 551
6 votes
2 answers
240 views

Cover cuts for knapsack constraint with integer variables

It is known for knapsack type constraint $\sum_{i \in N} a_i x_i \leq b , x \in \{0,1\}$, we can generate the so called cover cuts that have the sum of coefficient in a set C greater than b. The cover ...
CHE's user avatar
  • 113
4 votes
2 answers
251 views

XPRESS variables as indices for mixed integer linear programming

Can XPRESS variables not be used as indices to retrieve other XPRESS variables. In Python, for example, say that I have a list of XPRESS variables, each which can take on values (0->24). I'd like ...
jbuddy_13's user avatar
  • 551
2 votes
2 answers
206 views

How to model not-met demand to next period?

I am trying to include to my model a demand shift. That is, I am having a fixed demand for each period (t), but because of capacity constraints I am not able to serve the whole demand for each period. ...
Laura's user avatar
  • 79
5 votes
1 answer
1k views

How many variables and constraints can modern mixed integer programming solvers handle?

I originally asked a question here and they suggested that I crosspost it to the OR stack exchange, so that is what I am doing (hopefully correctly?). Here is the question I asked there: "I know ...
graphtheory123's user avatar
5 votes
1 answer
236 views

Summation of Binary Variables Pushing a Binary Variable

I'm modeling a problem where I have a set of binary decision variables $x_{ij}$ that has a value of 1 if the person $i$ is allocated to day $j$ or 0 otherwise. I have another set of binary decision ...
dhfg's user avatar
  • 53
2 votes
1 answer
115 views

How to mathematically model this multi-objective optimization problem?

I have a system of $M$ machines and $U$ users. Each machine has a capacity in terms of number of resources. Let, machine $m$ has $\zeta_m$ resources. Each user has a service demand $d_u$ and there is ...
KGM's user avatar
  • 2,285
3 votes
1 answer
129 views

Expressing $\{0,1\}$ assignment across a matrix in MILP?

I have a MILP (Xpress) constraint, which is doing what I want it to, but I'm struggling to translate it into a LaTeX friendly mathematical expression. The below code enforces that in the matrix $V$, ...
jbuddy_13's user avatar
  • 551
1 vote
0 answers
58 views

How to avoid complementarity constraints in continuous nonlinear program?

In my two-stage continuous NLP problem, I have a constraint in second stage: $X_{g,k}$ = $X_{g,0} + a_{g} d_{g} $, if $X_{g,k} \in [X_g^u,X_g^l]$ $X_{g,k} = X_g^u$, if $X_{g,k} \geq X_g^u$ $X_{g,k} ...
Ghulam Mohy-ud-din's user avatar
5 votes
2 answers
275 views

Adding linear penalties for multiple assignments

I have a multiple assignment problem, with an added cost for "repeat assignments". For example, consider the cost matrix: ...
Him's user avatar
  • 153
1 vote
2 answers
177 views

How to express this constraint efficiently?

Let, $\mathcal{C}=\{1,2,\cdots,C\}$, $\mathcal{U}=\{1,2,\cdots,U\}$ $\mathcal{S}_u$ is a subset of $\mathcal{C}$ with $u\in \mathcal{U}$ $d_{u,c}$ is a binary variable with $u=1,2,\cdots,U$ and $c=1,2,...
KGM's user avatar
  • 2,285
2 votes
2 answers
279 views

An if-then-else logic to construct constraint

I was hoping to get some help in modelling the following logic, I know that it would use some kind of Big M formulation but I am not sure how. Thank you in advance! $\Omega$ is a set whose values are ...
WaMIMO's user avatar
  • 33
2 votes
2 answers
362 views

pseudocode to convert english to constraint

This is not a technical question, but more curious if anyone has seen any software that converts english rules into linear constraints for MILP solvers? The rules would be industry specific and not ...
mathcomp guy's user avatar
-2 votes
2 answers
69 views

How to model the following "if, then" constraint

There are two matrices: Matrix $S^{v\times v} \in \{0,1\}$ this is a know parameter. Matrix $X^{v\times p} \in \mathbb{N}$. Elements of $X$ are the variables. I want to model: $$\textrm{if }s_{v v'} =...
Daniel Baquero's user avatar
7 votes
2 answers
545 views

Implementing Heuristic Callback in CPLEX C++ API for MILP

I am trying to implement a heuristic callback to a MILP with BOTH integer variables and continuous variables. After finding a feasible solution, I tried to use setSolution() to send the solution to ...
Jasonzjc's user avatar
1 vote
2 answers
221 views

How do I convert existing MILP problem into heuristics? or Shall I add heuristics to my existing MILP problem?

I have formulated a MILP problem & solved it using Gurobi. Below is the link to the description of MILP problem (a brief document) clearly stating its variables, constraints, and objective ...
Margi Shah's user avatar
5 votes
3 answers
294 views

MIP constraint with sum of decision variables having certain value : $\sum_{i=1}^nx_i = 2 \implies \delta = 1$

I want to formulate a MIP constraint such that : $$\sum_{i=1}^nx_i = 2 \implies \delta = 1$$ $x_i, \delta \in \{0, 1\}$. My problem is that delta should be one when this sum is exactly 2 and not ...
tonythestark's user avatar
6 votes
1 answer
726 views

Doubles Round Robin Sorting Algorithm

Background: I have a group of 6 guys that get together and play pickleball every week. We play 2v2 and 2 players sit each game. We play 2 sets of 6 games each week (12 total games) - in each set, ...
WoodGuyPurdue's user avatar
5 votes
1 answer
423 views

Dantzig-Wolfe decomposition for mixed-integer problem

Recently, I have been working on Dantzig-Wolfe(DW) decomposition technique. I found enough online resources that show worked-out examples of how to solve linear problems using the DW method. But I did ...
Fouad Hasan's user avatar
2 votes
1 answer
409 views

MIQP — CVXPY unable to treat summation of variables as a variable

I have a quadratic integer programming assignment problem. The goal is to assign riders seats on a bus such that distance between any two riders is maximized; however, the importance of each objective ...
jbuddy_13's user avatar
  • 551
2 votes
1 answer
99 views

Expressing inner product of binary variables in MIP

I have a $m$ by $n$ matrix $X$ of binary variables in my MIP which represents a list of $m$ items each belonging to one of $n$ categories. $m$ is usually around $1,000$ while $n$ is much lower at ...
Anish Shanbhag's user avatar
3 votes
1 answer
65 views

Is not the substitution method supposed to reduce the computation cost?

Is the substitution method expected to reduce the computation cost? We know it will reduce the number of variables and constraints. I mean by substitution method is to eliminate the equality ...
Hussein Sharadga's user avatar
1 vote
0 answers
89 views

Polynomial time separation and optimization for an LP with exponential columns and rows?

We know the fundamental theorem on the equivalence of separation and optimization: an optimization problem can be solved in a polynomial time if and only if there is a polynomial time separation ...
kachi's user avatar
  • 11
1 vote
1 answer
211 views

Applying weights to assignment problems for linear MIP solvers

In previous posts, A & B, I posed the Movie Theater Problem. In short, the movie theater problem encompasses assigning viewers to seats such that the distance between viewers is maximized, however,...
jbuddy_13's user avatar
  • 551
2 votes
1 answer
196 views

Google OR Tools: Iterative Assignment Problem

This question is a Google OR-Tools specific implementation of recommendation from a previous question. In short, the movie theater problem encompasses assigning viewers to seats such that the distance ...
jbuddy_13's user avatar
  • 551
2 votes
2 answers
169 views

Mixed Integer Programming: Iterative assignment problem

I have a real world problem, which is analogous to the below toy problem, which I call 'The Movie Theater Problem' (TMTP.) In TMTP, movie viewers are assigned seats which principally balances two ...
jbuddy_13's user avatar
  • 551
4 votes
3 answers
445 views

How to transform a logical constraint with integer variables?

Consider the binary variables $x_1, x_2 \in \{0,1\}$ and the integer variable $y \in \mathbb{Z}$ with $0 \leq y \leq 3$. I'd like to formulate the following logical constraint: $$ x_1 = 1 \wedge y \...
Ronaldinho's user avatar
2 votes
2 answers
442 views

Simplex method for multiple objectives

I am a user of Google OR Tools, which can interface with many LP & MIP solvers, plus it's own SAT based constraint programming solver. My question, in the context of OR-Tools, is: how should I ...
jbuddy_13's user avatar
  • 551
1 vote
1 answer
336 views

Create constraint when variable is within a given range MILP

What is the best way to specify whether a given variable is within a given range in Pyomo? Here I have a binary decision variable assign[t, e] which I want to ...
Pia MiA's user avatar
  • 392
2 votes
1 answer
65 views

How to get the fractional solution of a node in a MIP model using JuMP package?

I'm coding in Julia and use the JuMP package. My IP solver stops by a fixed node limitation. I noticed that I can only get the feasible primal and dual solution if has any, however I would like to get ...
Brown's user avatar
  • 173
2 votes
2 answers
310 views

Improve Network Flow computation with additional Pyomo constraints based on previous computation

I am performing several max-flow computations on extremely similar networks and I seek to improve their execution time based on information from previous computations (As there is a lot of repetitive ...
Pia MiA's user avatar
  • 392
1 vote
1 answer
105 views

Are there any performance overheads if we specify Pyomo Constraints in different way?

I am interested to know whether there are any performance overheads for specifying Pyomo Constraints in different ways. For example, which of the two ways is better? I am trying to speed up one of my ...
Pia MiA's user avatar
  • 392
3 votes
1 answer
73 views

Can we turn a Binary IP model into a problem solvable using Local search?

I am new to the fields of operations research. I have a Binary IP model for solving a scheduling problem and I am seeking to find information whether I can somehow transform it to a problem that can ...
Pia MiA's user avatar
  • 392
0 votes
1 answer
165 views

Rolling Horizon approach for solving a job scheduling problem

I am trying solve a scheduling problem adopting a rolling horizon approach. I have developed an Integer programming model and seek to speed up execution. I am seeking advice on beginner level ...
Pia MiA's user avatar
  • 392
2 votes
1 answer
97 views

Modeling advice: scheduling problem with judged events and "blocks" of judging assignments

I am considering a scheduling problem in which the events are officiated, likely as a MILP problem. I'm getting hung up on how best to model a particular requirement of how the judged events are ...
pholser's user avatar
  • 123
3 votes
1 answer
297 views

Linearize objective function in MILP

I have an objective function that I want to linearize but want to confirm that I'm doing it correctly. There are some constraints that are linear in $x$ but they're unimportant for the problem. The ...
dmbeledo's user avatar
3 votes
1 answer
377 views

Jump, Julia : How to add constraints with different indexes a.c.a $x_i \leq z_j, \; \forall i, j$

I am having a constraint in the form : $$ x_i \leq z_j, \quad \forall i, j \in \{1, 2, .., n\}$$ I know that if the right part of the equation was a constant so something like $x_i \leq c[i]$ I could ...
tonythestark's user avatar

1
4 5
6
7 8
20