Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
133
questions
3
votes
1answer
110 views
Problems finding a feasible solution in a MIP
I am using CPLEX with Julia using the package JuMP to solve a MIP problem.
In a small instance, I have tested my problem but, after 10 minutes, nothing happens. I have defined the following parameters ...
3
votes
2answers
276 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 ...
3
votes
2answers
132 views
How to get an extreme ray of an LP from Gurobi
I am working on a problem of form
\begin{equation}
\begin{array}{l @{\quad} l}
\mathrm{max}_{x, u} & p^{\top} u
\\
\text{st.} & A u + a x \leq 0
\\
& x \in \{0, 1\...
3
votes
1answer
143 views
Formulation of assignment problem as Linear Optimization
In the anti-tumor treatment with radiotherapy, it is possible to irradiate the tumoral mass from different positions with different intensities. For each of these possibilities, however, one has to ...
3
votes
2answers
65 views
How to improve relative mip GAP using CPLEX in a MIP
Supose that I have an integer feasible solution for a MIP and I provide this one for CPLEX. I have tested this situation in a problem and CPLEX have reported the following:
...
3
votes
1answer
164 views
Problem solving a linear program using Excel
The exercise is as follows:
ACI has decided to put an order for golf shoes twice every year and
expects to receive one shipment of $960$ pallets of shoes by the
beginning of January and another ...
3
votes
1answer
78 views
Integer decision variables as index
The following problem has only two integer variables; however, they appear in the index of the parameters. Appreciate it if anyone has any efficient idea to transform it into a canonical integer ...
3
votes
1answer
38 views
Finding bounds on a data sensitivity scenario ILP problem
This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem
As a recap, I was interested in finding the minimum number of cells that need to be suppressed ...
3
votes
1answer
94 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 ...
3
votes
0answers
58 views
Optimal Seat Allocation Problem
I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
3
votes
0answers
50 views
Flexible Job Shop with Preemption
I'm trying to solve a flexible job shop problem variant that has precedence constraints on jobs along with a few other issues. We have a MIP formulation and also a simulated annealing algorithm to ...
3
votes
0answers
65 views
Indicator function for integer variable with inequality constraint
I have $n$ integer variables $\vec{x}$ with the following integer programming problem.
$$
COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0)
$$
Here, $a_i, b_j \in \mathbb{R}_+$ ...
3
votes
0answers
98 views
How develop a branch and bound algorithm for integer programming with black box objective function?
The problem here described was taken from a university exercitation session.
A serial production line is made of $K$ workstations: one kind product is manufactured by this line and has to be processed ...
3
votes
0answers
93 views
Condition for an integer program and its linear relaxation to have the same value
Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
3
votes
0answers
38 views
How to find all covers and minimal covers?
Consider a constraint of type
$$c_1x_1+c_2x_2+\cdots+c_nx_n\leq C$$
with $x_i$ binary.
We call a cover a subset of the $n$ indices such that the sum of the corresponding coefficients is higher than ...
3
votes
0answers
61 views
Theoretical aspect of using extended formulation
If I can show a polyhedron Y is an extended formulation of polyhedron X and every extreme point in Y is integral, does that automatically imply the projection of Y onto the variable space of X gives ...
2
votes
4answers
79 views
Linearity of an optimization problem which comprises the product of variables with constant values from a non-linear function
In a mathematical integer optimization problem, if the objective function is represented as $\sum x_k \cdot M_k$, where $M_k$ is a non-linear function whose value is known and just plugged in to the ...
2
votes
2answers
95 views
Constraint to handle the machine-configuration's change between initial position and its first occurrence in the process
I am working with a kind of a reconfigurable process planning, meaning that the same machine can have different configurations and perform multiple operations. Each machine has an initial ...
2
votes
1answer
83 views
constraint programming and scheduling issues
I have a constraint problem that i need to resolve, but i did not how know to model the problem:
I have 11 employees, i will name them from a to k {a,b,c,d,e,f,g,h,i,j,k}.
I have a small company that ...
2
votes
1answer
299 views
Divisibility constraint in Integer programming
I have a simple question regarding the divisibility in integer programming
suppose the objective function is
$\text{max}\quad x_1 + x_2$
where the constraint is that the sum of $x_1$ and $x_2$ are ...
2
votes
1answer
48 views
Priority Constraint
Suppose I have the following set of binary variables:
$X_i$: $I$ ranges from {1,..,4} Highest priority among the three variables $X$ , $Y$ and $Z$
$Y_j$: $J$ ranges from {1,..,3}
$Z_k$: $K$ ranges ...
2
votes
1answer
77 views
Inequality Constraint Linearization of a product of an integer and a binary variable
I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable?
But the answers to that questions didn't help me find a solution for my ...
2
votes
1answer
71 views
Minimizing a quadratic binary nonconvex function by CPLEX
I am using CPLEX 12.8 to minimize a quadratic binary nonconvex function, according to quadratic function by CPLEX.
In particular, my function is the following:
$$ \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{...
2
votes
1answer
75 views
confusing results of two models with different complexity
i have two models that address the same problem.
the first one is :
the second one is:
for different instances for the same size (n=30) i found the following results ( the first column on the left ...
2
votes
1answer
50 views
Has the concept of TU other application than proving convex hull characterizations?
If a matrix is totally unimodular (TU), then we know that $\text{\{}x| Ax\leq b \text{\}}$ is integral for all integral $b$'s. This is often used for convex hull proofs, but does the concept of TU has ...
2
votes
0answers
34 views
Interger programming using gray encoding
Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...
2
votes
0answers
143 views
Operation hours optimization for circular schedule
Here is my problem. A store has X = 15 electical devices with the ability to work non-stop, fully charged, up to 8 hours. Their battery charge lasts 2 hours and the operating hours of the store differ ...
1
vote
2answers
154 views
Switching of decision variables to be larger than or equal to a decision variable according to an indicator variable value
I would like to seek some advice on modeling the following:
I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is greater than or equal to a ...
1
vote
2answers
86 views
How this problem can be defined as MultiObjective optimisation
I need to optimize the end-to-end latency of a multi-component application.
Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...
0
votes
2answers
197 views
How can I formulate this specific if-then constraint?
IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly)
AND
IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly)
$X$ and $Y$ are binary variables.
What I'm actually trying to do is to charge the ...
0
votes
1answer
74 views
Miller-Tucker-Zemlin subtour elimination constraints to obtain a minimum spanning tree
I need Miller-Tucker-Zemlin subtour elimination formulation for symmetric traveling salesman problem (STSP) to use to construct a minimum spanning tree. Ie,
I need Miller-Tucker-Zemlin formulation ...
0
votes
0answers
36 views
Linearizing max constraint Problem [duplicate]
I want to linearize a max constraint as below:
In which x_(i,t),are binary decision variables and T is a constant.
How can I linearize this constraint?
-1
votes
1answer
96 views
Any references to the ROADEF 2020 Challenge?
The problem description of the challenge is given here.
Does anyone has some references to similar problem. I would like to participate but I don't know where to start.
