Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
352
questions
2
votes
1answer
91 views
Benders decompositions: Number of iteration does not remain same
I am solving an LP(i.e 118-bus system economic dispatch for 130% loading) using benders decomposition. The problem takes 26 iterations to converge. This means that the process adds 25 cuts to the ...
1
vote
0answers
66 views
Optimisation Multiple Constraints
I am trying to solve a linear algebra problem: an optimisation problem and I am using CVXOPT. I've split the problem into 3 components
In its simplest form, The general formulation for CVXOPT is \...
4
votes
1answer
172 views
Are decomposition methods applicable on large linear programs?
Working on a very large Linear Program, we tried out some primitive implementations of decomposition techniques such as Lagrangian relaxation and column generation. However, none of these were able to ...
2
votes
1answer
81 views
Linearly independent rows in simplex
I'm having some trouble understanding about the independent rows in a basic solution. In the book Introduction to linear optimization by B&T, the authors give the definition of a basic solution as ...
9
votes
2answers
151 views
Are there small LPs out there?
A fair share of academic research and software development focuses on solving ever-larger problems, particularly when it comes to LPs.
I am however curious to know in what contexts and to what extent ...
6
votes
1answer
93 views
Upper and lower bounds of a variable equal
I'm working on a MILP (Mixed-Integer Linear Programming) problem with the Java API of Cplex.
In order to easily exclude some variables from my problem I thought about setting both their lower and ...
2
votes
1answer
65 views
Examples of LP problems in irrigate engineering
I need examples of linear programming problems applied to irrigation system.
My idea is to give students many examples of LP applications in the irrigation engineering.
1
vote
0answers
74 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}\\
\...
4
votes
0answers
191 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 ...
2
votes
1answer
87 views
KKT conditions analysis for binary constraints
I am wondering if boolean constraints in a linear program can be solved (after linear relaxation from $x\in\{0,1\}$ to both $x\ge0$ and $x\le1$) using KKT analysis.
Most of the algorithms that I have ...
3
votes
1answer
114 views
Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT
I am trying to convert a boolean LP to LP using LP relaxation by converting $x \in {0,1}$ to both $x \ge 0$ and $x \le 1$.
Then to use it in my problem analysis, I am trying to build the KKT ...
5
votes
1answer
276 views
Model “if and only if” indicator constraints in Linear programming
Apologies if this question has been asked, but I haven't been able to find it. I'm modelling something with Gurobi and want to do the following:
\begin{align}\text{cond} < \dfrac{1}{3} &\iff x =...
3
votes
1answer
114 views
Best way to add dummy to transportation problem? Zero cost will be always chosen first?
I know that an unbalanced transportation problem could be made a balanced transportation problem by adding a dummy node which equals the difference between demand and supply.
In literature, dummy ...
4
votes
1answer
228 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 ...
3
votes
1answer
73 views
Need help with an appointment scheduling problem
I am currently stuck on writing a linear programming model to describe the process of appointment scheduling for an Oncological Center. I wanted to share it with you guys and see if anyone here could ...
1
vote
1answer
48 views
Employee allocation based on ranking: Mathematical Model
Suppose I have three employees and I have to assign three employees based on their ranks. If an employee has rank 1 that means he is best. Say, I have the following table
...
-2
votes
1answer
71 views
MODM to create balanced groups of students to maximise diversity
I am very new to LP, Goal Seek, Decision Models etc and I have a multiple-objective decision making problem that may or may not require a mix of techniques although I am trying to solve it purely ...
4
votes
1answer
76 views
An efficient Integer programming model for the minimum spanning tree problem?
Let $T=(V, E')$ be a spanning tree of a graph $G=(V, E)$. Rather than verifying for any subset of vertices $S\subseteq V$ that $|E'(S)|=|S|-1$, is there an efficient way to satisfy the spanning tree ...
17
votes
7answers
3k views
Is there a Linear Programming Library that natively supports fractions instead of floating point arithmetic?
If one recalls how the Simplex method is taught by hand in most LP classes it takes place entirely in $\mathbb{Q}$. All operations yield exact fractions.
For this reason I'm looking for linear ...
5
votes
1answer
240 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 ...
6
votes
1answer
178 views
Obtaining the system of irredundant inequalities from a set of inequalities using CPLEX
Given a linear system of inequalities $Ax \geq b$, I would ideally like to compute the irredundant set for those set of inequalities. I know how to do so mathematically, but I was wondering if there ...
2
votes
0answers
52 views
How is the dual revised simplex method equivalent to running the RSM on the dual problem?
I've seen the claim (in the title) several places, but can't quite understand why it's true.
From what I understand so far, the revised simplex method solves an LP in standard computational form, $$\...
2
votes
2answers
91 views
Transformations that leave the linear program unchanged
A typical linear program is written as $$L_0:\min_{x \geq 0; A^\top x \leq b}c^\top x.$$ Here, $x \in \mathbb{R}^n$, $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$.
...
0
votes
1answer
85 views
Objective function with exponential coefficients
I have a linear programming problem, with $n$ variables and $a\leq x_{i} \leq b$ for each variable $x_{i}$, where the objective function is $\min \sum\limits_{i=1}^{n}{2^{i} x_{i}}$
Is it true that, ...
10
votes
1answer
612 views
Linear Optimization Library for C++ with GPU Support
Does anyone know any linear optimization libraries for C++ supporting GPUs for parallelization? If multiple, which do you recommend?
The GPU support is important to me since I am dealing with large ...
11
votes
1answer
132 views
What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?
I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
-4
votes
1answer
94 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]...
19
votes
4answers
788 views
How can I remember the rules for taking the dual of a linear program (LP)?
When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?...
4
votes
2answers
156 views
Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (`python`)
I am trying to write a program to schedule a team of 8 individuals into shifts.
I want to know how to model that every individual must get at least one night shift break, and must not work two ...
1
vote
0answers
46 views
Specializing Iterations of Dantzig-Wolfe Decomposition with an Oracle
This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the bounded ...
5
votes
2answers
159 views
Asymmetric time-constrained capacitated vehicle routing problem
I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)1 (pp.4).
The mentioned model caps the travel distance, while I cap the travel time. Let $U$ represent ...
4
votes
1answer
113 views
Extreme points of a simple polyhedron
Consider the polyhedron given by the set of inequalities
\begin{align}
\mathbf{b}^T\mathbf{x} ~&\leq~ c \\
\mathbf{e}^T\mathbf{x} - 1 ~&\leq~0 \\
\mathbf{x}~&\geq~0
\end{align}
where $\...
9
votes
2answers
237 views
Common structures in Gurobi - Python
I'm new to Gurobi in Python and I was wondering if someone knows how to code some common structures of linear constraints. I'm trying to understand how you'll code something like the following ...
4
votes
2answers
143 views
Any Solution for $k$-means with minimum and maximum cluster size constraint?
I am looking for an efficient approach to $k$-means clustering with minimum cluster size constraints. The clusters are non overlapping, so, one point can belong to only one cluster.
$N$ be the number ...
5
votes
4answers
429 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 ...
2
votes
1answer
89 views
On dual-formulation of a given primal for a set-covering problem
I need to solve an LP-relaxation of an airline crew pairing optimization problem (CPOP). The problem formulation is a modified SCP and is as follows:
Primal of the CPOP:
\begin{align}\min&\quad\...
2
votes
1answer
65 views
How to linearize inequalities having max or min?
I'm modeling an LP problem in which I have to maximize an objective function. Two of the constraints are the following, where $k_i$ are constants and $x_i$ decision variables (continuous). Could ...
0
votes
1answer
256 views
How to mathematically formulate the optimization problem?
I have a system with $S$ service points.
There are also $U$ users in the system.
We have $$U>S>G$$
One group can have maximum $M$ service points, but there is no restrictions on the number of ...
2
votes
2answers
95 views
How to deal with a decision variable in the objective function that depends on if-else conditions involving other decision variables?
I'm modeling an optimization problem in which a decision variable $x_1$ in the objective function depends on if-else conditions involving decision variables $x_2$ and $x_3$, as the following equation, ...
4
votes
1answer
311 views
Is there any automatic way to spot contradictory constraints in linear programming?
Let's have the following trivial linear program: \begin{align}\max&\quad z=20A+30B\\\text{s.t.}&\quad A\le60\\&\quad B\le50\\&\quad A+2B\ge220\\&\quad A,B\ge0\end{align}
It's easy ...
4
votes
1answer
59 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}$ ...
4
votes
3answers
206 views
Faster implementation of “or” constraints in ILP
I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...
0
votes
1answer
90 views
Mixed Integer Programming - How to model the dependency of two variables in an objective function
I have two variables $a$ and $b$, in which $a$ is the amount of goods and $b$ is the amount of boxes of the given sizes. So $b$ (box size + number) is dependent on a (goods quantity). If $a$ is ...
1
vote
0answers
64 views
LP instead of IP formulation of assignment problem
In the example files of GLPK, the assignment problem is written as a linear program. I don't understand why this isn't an integer programming problem. The problem formulation:
...
4
votes
3answers
108 views
warmstarting simplex algorithm- how much can problems differ from each other?
I'm working on an implementation of the simplex algorithm.
I want to solve problems in real time every 30 minutes. They could be interpreted as a classic transportation problem.
I couldn't really say ...
3
votes
2answers
308 views
If-then constraint with continuous variables
I was usually using if-then constraints with integer variables but ended up using continuous variables and got confused. I have variables $x_{ij}\in\mathbb{R}_{\geq 0}$, and would like to force the ...
1
vote
1answer
137 views
How to linearize the product of a binary and a continuous variable? [duplicate]
Suppose we have a binary variable $b \in \{0, 1\}$ and a continuous (possibly negative) variable $y \in \mathbb{R}$. How can we linearize the product $b \cdot y$?
3
votes
0answers
99 views
Two binding constraints - Linear Programming
I'm having some troubles to continue solving my system, I'm used to solve such systems but with "one" binding constraint, if someone could give me some helpful hints so I can solve it I will ...
2
votes
3answers
122 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.
...
1
vote
1answer
78 views
Job Shop Scheduling Problem: jobs are scheduled on the same machine at the same time
I want to solve a job shop scheduling problem. I got $n$ Jobs that have to be scheduled on $k$ Machines. A Job $i$ has 2 or 3 Tasks $j$, and there is a known sequence of the Tasks of a Job. One ...
